2h
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.
Nov
26
comment Algorithmic advantages of pathwidth over treewidth
There are problems that are easy on paths but NP-Hard on trees. These include minimum multicut and maximum integer multiflow.
Nov
6
comment Maximizing a submodular function with restricted values
(3) implies (4). If a monotone $f$ satisfies (3) then it is essentially the rank function of a matroid $M$ (we can suppress the elements $x$ with $f(x) = 0$). Maximizing $f$ subject to a cardinality constraint is the same as finding min of $k$ and the rank of $M$ which is poly-time solvable.
Oct
30
comment Theoretical results for random forests?
@D.W Write to the authors and see if they are willing to share a copy. I am aware of the results but haven't seen the paper myself.
Oct
28
comment Theoretical results for random forests?
There is a new paper in upcoming SODA'15 that may be relevant. See meetings.siam.org/sess/dsp_talk.cfm?p=68795
1 2 3 4 5