Subexponentially solvable hard graph problems

Question

In light of the recent result of Arora, Barak, and Steurer, Subexponential Algorithms for Unique Games and Related Problems, I'm interested in graph problems that have subexponential time algorithms but believed not to be polynomially solvable. A famous example is graph isomorphism which has subexponential algorithm of $2^{O(n^{1/2} \log n)}$ run-time. Another example is log-Clique problem which is solvable in quasi-polynomial time ($n^{O(\log n)}$).

I'm looking for interesting examples and preferably a reference to surveys of subexponential hard graph problems (not necessarily $NP$-complete). Also, Are there any $NP$-complete graph problems with subexponential time algorithms?

Impagliazzo, Paturi and Zane showed that the Exponential Time Hypothesis implies that Clique, k-Colorability, and Vertex Cover need $2^{\Omega(n)}$ time.

Answer 1

By the way the Max Clique problem, in full generality, can be solved in time $2^{\tilde O(\sqrt N)}$ where $N$ is the size of the input.

This is trivial if the graph is represented via an adjacency matrix, because then $N=|V|^2$, and a brute force search will take time $2^{O(|V|)}$.

But we can get the same bound even if the graph is represented by adjacency lists, via an algorithm of running time $2^{\tilde O(\sqrt{|V| + |E|})}$. To see how, let's get a $2^{\tilde O(\sqrt{|V| + |E|})}$-time algorithm for the NP-complete decision problem in which we are given a graph $G=(V,E)$ and $k$ and we want to know if there is a clique of size $\geq k$.

The algorithm simply removes all vertices of degree $< k$ and the edges incident on them, then does it again, and so on, until we are left with a vertex-induced subgraph over a subset $V'$ of vertices, each of degree $\geq k$, or with an empty graph. In the latter case, we know that no clique of size $\geq k$ can exist. In the former case, we do a brute-force search running in time roughly $|V'|^k$. Note that $|E| \geq k\cdot |V'| /2$ and $k\leq |V'|$, so that that $|E| \geq k^2/2$, and so a brute-force search running in time $|V'|^k$ is actually running in time $2^{O(\sqrt{|E|} \cdot \log |V|)}$.

Answer 2

Since every planar graph on $n$ vertices has treewidth $O(\sqrt{n})$, all problems which are solvable in $O^*(2^{O(k)})$ time for graphs of treewidth at most~$k$ (there are a LOT of such problems) have subexponential-time algorithms on planar graphs by computing a constant-factor approximation to the treewidth in polynomial-time (for example by computing the branchwidth with the ratcatcher algorithm) and then running the treewidth algorithm, resulting in runtimes of the form $O^*(2^{O(\sqrt{n})})$ for graphs on $n$ vertices. Examples are Planar Independent Set and Planar Dominating Set, which are NP-complete of course.

Answer 3

There is a close connection between sub-exponential time solvability (SUBEPT) and fixed parameter tractability (FPT). The link between them is provided in the following paper.

An isomorphism between subexponential and parameterized complexity theory, Yijia Chen and Martin Grohe, 2006.

In brief, they introduced a notion called miniaturization mapping, which maps a parameterized problem $(P,\nu)$ into another parameterized problem $(Q,\kappa)$. By viewing a normal problem as a problem parameterized by the input size, we have the following connection. (See theorem 16 in the paper)

Theorem. $(P,\nu)$ is in SUBEPT iff $(Q,\kappa)$ is in FPT.

Be careful of the definitions here. Normally we view $k$-clique problem as parameterized in $k$, so there is no sub-exponential time algorithm for it assuming Exponential time hypothesis. But here we let the problem be parameterized by the input size $O(m+n)$, thus the problem can be solved in $2^{O(\sqrt{m}\log m)}$, which is a sub-exponential time algorithm. And the theorem tells us that the $k$-clique problem is fixed parameter tractable under the some twist of the parameter $k$, which is reasonable.

In general, problems in SUBEPT under SERF-reductions (sub-exponential reduction families) can be transformed into problems in FPT under FPT-reductions. (Theorem 20 in the paper) Furthermore, the connections are even stronger since they provided an isomorphism theorem between a whole hierarchy of problems in exponential time complexity theory and parameterized complexity theory. (Theorem 25 and 47) Though the isomorphism is not complete (there are some missing links between them), it is still nice to have a clear picture about these problems, and we can study sub-exponential time algorithms via parameterized complexity.

See the survey by Jörg Flum and Martin Grohe, together with Jacobo Torán, the editor of the complexity column, for more information.

Answer 4

another example can be Cop and Robber game, which is NP-hard but solvable in time $2^{o(n)}$ on graphs with n vertices. BibTeX bibliographical record in XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Pursuing a fast robber on a graph. Theor. Comput. Sci. 411(7-9): 1167-1181 (2010)

Answer 5

The best approximation algorithm for clique gives an unbelievably bad approximation factor $n/\text{polylog } n$ (recall that approximation factor of $n$ is trivial).

There are hardness of approximation results under various hardness assumptions that don't quite match this, but still give hardness of $n^{1-o(1)}$. Personally, I believe that $n/\text{polylog } n$ approximation for clique is as good as polynomial-time algorithms would ever do.

But approximation of $n/\text{polylog } n$ for clique can easily be done in quasi-polynomial time.

---

An NP-hard problem is a problem that has a polynomial-time reduction from SAT. Even if SAT needs time $2^{\Omega(n)}$, this may translate to time $2^{\Omega(N^\epsilon)}$ for the problem we reduce to. If the latter has input size N, it may be the case that $N=n^{1/\epsilon}$ for a small constant $\epsilon$.