May
20
answered Multidimensional knapsack STRONGLY NP-complete
May
19
comment Approximate distance preserving sparse graph representation that are not necessarily subgraphs
Julia Chuzhoy has a paper on sparsifiers that exploit the fact that Steiner nodes can help. See arxiv.org/abs/1204.2844
May
19
comment Multidimensional knapsack STRONGLY NP-complete
Multidimensional knapsack is essentially the same as what are called packing integer programs (PIPs) which captures max independent set as a special case, as you observe.
May
18
comment Set cover approximation ratio as a function of m (number of sets)
See this note by Jelani Nelson. eccc.hpi-web.de/eccc-reports/2007/TR07-105/revisn01.pdf
May
18
comment The maximum of a submodular function which has no restrictions
Your claim that $f(S) \le \sum_{j \in S} f(j)$ is false if $f$ can be negative.
May
5
awarded Civic Duty
May
5
comment Complexity of max problem
What is known in terms of upper bounds for approximation?
Apr
27
awarded Revival
Apr
25
answered What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?
Apr
6
comment How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?
Isn't this a home work problem in my course?
Apr
2
comment Hardness of approximately counting independent sets with a PRAS, rather than FPRAS
It is relatively easy to argue via amplification that if you have a poly(n)-factor polynomial-time approximation for these counting problems then you can get all the way to a FPRAS. Thus, having a PTAS would imply FPRAS because PTAS already implies a constant factor approximation.
Mar
30
comment Are there sparsifiers that approximate vertices rather than edges?
Cut sparsifiers for edge-cuts work by using weights on the sparse graph. It is not clear how this can be done for vertex-cuts. Looking at Julia Chuzhoy's vertex cut sparsifier paper may be useful. arxiv.org/abs/1204.2844
Mar
26
comment Are there subexponential algorithms for PLANAR SAT known?
More generally it is well-known that if the incidence graph of a SAT formulat has treewidth at most $k$ then one can check satisfiability in $2^{O(k)} poly(|\phi|)$ time. Planar graphs with $n$ vertices are guaranteed to have treewidth $O(\sqrt{n})$ due to the planar separator theorem. More generally graphs that exclude any fixed graph $H$ has a minor have treewidth $O(\sqrt{n})$ where the constant depends on size of $H$.
Mar
12
awarded Nice Answer
Mar
12
comment Is the Cheeger constant $\mathsf{NP}$-hard?
@MohammadAl-Turkistany: Take two connected bridgeless cubic graphs that are expanders, one with 2n vertices and the other with n vertices and connect them with three edges by adding some 3 new vertices on each side via sub-dividing 3 edges. Now the min-bisection is going to be large ($\Omega(n)$) because you have to cut off a good chunk of the larger expander but the expansion is small because you can split the two expanders by cutting just 3 edges.
Mar
12
comment Is the Cheeger constant $\mathsf{NP}$-hard?
It is natural to pose the edge expansion problem as a decision problem. Given $G$ and $\alpha$, is edge expansion of $G$ at least $\alpha$? This is a co-NP complete problem.
Mar
12
comment Is the Cheeger constant $\mathsf{NP}$-hard?
My paper which uses the edge expansion hardness is the one below onlinelibrary.wiley.com/doi/10.1002/net.20165/abstract. We refer to the Leighton-Rao paper and that of Garey, Johnson, Stockmeyer for hardness of edge expansion.
Mar
12
answered Is the Cheeger constant $\mathsf{NP}$-hard?
Jan
28
revised Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?
deleted 19 characters in body
Jan
27
answered Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?
1 2 3 4 5