1d
answered What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?
Apr
23
comment Longest path on a general weighted graph
Have you tried searching on google scholar?
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?
Jan
23
comment What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?
See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507
Dec
27
comment Approximation Algorithm for TSP-like problem
Orienteering refers to the problem where one wants a walk with a given budget instead of a simple path - a node is allowed to be visited more than once but the merit/profit is only counted once. If distances satisfy triangle inequality then asking for a simple path is equivalent to asking for a walk. However, if you insist on a simple path then what you are looking for is closely related to the longest path problem. For longest paths check Gabow's paper and pointers: epubs.siam.org/doi/abs/10.1137/…
Dec
27
comment Hamiltonian cycle on a subset of 2D points, constrained by maximum total length
The journal version of the above mentioned $(2+\epsilon)$-approximation is available at the link below. It has additional results. web.engr.illinois.edu/~chekuri/papers/orienteering-journal.pdf
Dec
12
comment Minimal cumulative set sum
I would also recommend the following paper for improved bounds, special cases, and hardness results for the scheduling problem. people.idsia.ch/~monaldo/papers/MOR-schedprec-11.pdf. See also the paper on 2-\epsilon hardness under a variant of unique games by Bansal and Khot win.tue.nl/~nikhil/pubs/focs-09-version.pdf.
Dec
3
comment Modifying Hopcroft-Karp algorithm to get approximate bipartite matching
@DavidEppstein I think stopping the augmenting path algorithm after paths reach $\Omega(1/\epsilon)$ should give a $(1-\epsilon)$-approximation, no?
Nov
27
revised Books/Lecture Notes on Parametrized Complexity
added 303 characters in body
Nov
26
comment Algorithmic advantages of pathwidth over treewidth
This is again not a clean answer to the original question. The flow-cut gap in pathwidth k graphs is known to be bounded by f(k) for some function f via a result of Lee and Sidiropoulos. It is an important open problem whether such a result holds for treewidth. The case k=3 is open for treewidth.
1 2 3 4 5