1d
comment Maximal Clique partition of vertices with smallest number of cut edges
Following up on David Eppstein's question, is it clear that the decision version of the problem is poly-time solvable? That is, can we decide whether G can be partitioned into p maximal cliques? It is probably hard by appropriate modification from the standard clique cover/coloring hardness reduction.
Apr
23
comment Reference request on dynamic flows combined with network coding
You may find some relevant literature if you search for the terms "network coding" and "delay".
Apr
22
revised Max-sum graph-partition for maximizing intra-edge weights?
added 450 characters in body
Apr
20
answered Max-sum graph-partition for maximizing intra-edge weights?
Apr
20
comment Max-sum graph-partition for maximizing intra-edge weights?
The problem is NP-Hard via a reduction from minimum k-way cut. In min k-way cut we want to partition the graph into k parts to minimize the sum of the edges across the cut. Your problem is the complement.
Apr
14
comment Parametrized complexity of the 2-Long Paths Problem
Have you tried using the color coding technique that shows that longest path problem is in FPT?
Mar
29
awarded Nice Answer
Mar
14
comment Does k-PATH admit a constant approximation?
There is also a paper on hardness for the longest path problem in directed graphs. link.springer.com/chapter/10.1007/978-3-540-27836-8_21#page-1
Mar
14
comment Does k-PATH admit a constant approximation?
Gabow's paper on finding long paths of super poly-logarithmic length is interesting and relevant. epubs.siam.org/doi/abs/10.1137/S0097539704445366
Mar
14
comment Does k-PATH admit a constant approximation?
@RickyDemer The hardness reduction should work for the length as well.
Mar
4
comment Maximizing a monotone supermodular function s.t. cardinality
Seems correct. Nice.
Mar
3
comment Maximizing a monotone supermodular function s.t. cardinality
Densest k-subgraph is considered likely to be hard. There is some evidence for that. However, as you said, a formal proof for the general setting of supermodular functions has not been shown and it may in fact be easier to do.
Feb
6
comment The relationship between degree of vertex and size of dominating set
Yes, that is correct. The bound should be $n H_{d+1}/(d+1)$ where $H_k$ is the $k$'th harmonic number. $H_{d+1}$ is at most $1 + \ln (d+1)$. Hence this bound matches what Florent posted in the answer below.
Feb
4
comment The relationship between degree of vertex and size of dominating set
Another way to see the bound is by observing that if you can obtain a fractional solution to the dominating set by setting a value of $1/(d+1)$ on each vertex where $d$ is the minimum degree. The total value of this fractional solution is $n/(d+1)$ and it is easy to see that it is feasible. Now by randomized rounding or known integrality gap results there is an integral solution of value $n\ln n/(d+1)$.
Feb
4
comment The relationship between degree of vertex and size of dominating set
Is there any reason to believe that the log n factor can be removed? I suspect that it may be necessary.
Jan
31
comment Minimizing a monotone submodular function under a cardinality constraint
There is a strong lower bound for this problem even in the monotone case. See arxiv.org/abs/0805.1071
Jan
29
comment Set Cover variant- improvement over log(n) approximation?
You can add dummy elements and essentially make all set sizes be roughly the same. Then you will be back to the difficult case of set cover with unit weights.
Jan
29
comment Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$
What do you get if you try $f(n) = 2f(n - \log n)$? It appears that you will get a lower bound of $2^{\Omega(n/\log n)}$.
Jan
21
comment Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
Take a closer look.
Jan
20
answered Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
1 2 3 4 5