Question

This question is related to the previous discussion here.

Due to the result of Noga Alon et al., there is an $O((2k)^kn)$ algorithm for deciding whether a planar graph $G$ contains a fixed subgraph $H$ of size $k$, and the time complexity is reduced to $O(2^kn)$ if the graph $H$ is of bounded treewidth. Take $k = O(\log n)$ yields a polynomial time algorithm for the latter case, say the $k$-path problem mentioned by Ryan Williams in this paper.

There is an open problem in the result:

If we want to solve $k$-path problem in a planar graph with slightly larger $k$, say $k = O(\log^2 n)$, is there a polynomial time solution at this point? If so, what is the best time complexity at present?

Answer 1

I remember thinking about this a while ago, and stopped because it seemed unlikely that $log^2 n$ paths can be found in polynomial time. This was my argument, if I remember correctly.

The best known algorithm for Hamiltonian path is $O^*(2^n)$. I think improving this to sub-exponential time, like $O(2^{o(n)})$ would violate the exponential time hypothesis (ETH).

Now if we had a polynomial time algorithm for finding a path of length k, where $k=O(\log^2 n)$, then we could solve Hamiltonian path on a graph with k vertices in time polynomial in n. Since $k=O(\log^2 n)$, polynomial time in n translates to time $O(2^{\sqrt{k}})$ in terms of k. This is a sub-exponential time algorithm for Hamiltonian path, which violates the ETH.

If this reasoning is correct, then it's quite unlikely that $\log^2 n$ length paths can be found in polynomial time on general graphs. As for planar graphs, I think ETH gives a lower bound of $\Omega(2^{\sqrt{n}})$, so maybe $\log^2 n$ graphs can still be found, but not any larger, like $\log^{2.1} n$ paths.

Answer 2

It seems very plausible to me that the $k$-path problem is in $2^{O(\sqrt{k})}poly(n)$ time on planar graphs. Other parameterized subgraph problems (e.g. $k$-vertex cover) are known to exhibit such algorithms, so why not? But I don't know of any further progress in this direction.

For general directed graphs, solving the $\omega(\log^2 n)$-path problem in polynomial time is known to be "ETH-hard", meaning that such an algorithm would imply that 3SAT is in subexponential time. This was proved by Bjorklund, Husfeldt, and Kanna, and the paper can be found here: http://repository.upenn.edu/cis_papers/205/

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna: Approximating Longest Directed Paths and Cycles. ICALP 2004: 222-233

In the case of general undirected graphs, this is open (as far as I know). A recent algorithm of Gabow and Nie has the property that if there is an $\ell$-cycle in a given undirected graph, then the algorithm can find a cycle of length $\exp(\Omega(\sqrt{\log \ell}))$ in polynomial time. So for general Hamiltonian graphs, you can find $\log^2 n$ length paths efficiently.

Harold N. Gabow, Shuxin Nie: Finding Long Paths, Cycles and Circuits. ISAAC 2008:752-763

I don't know what bearing this has on the planar case, but it certainly seems relevant.

Answer 3

It seems to me that the following paper solves the $k$-path problem for $k = O(\log^2 n)$ in polynomial time:

Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender and Fedor V. Fomin: Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions. ESA 2005

The paper solved the $k$-cycle problem in time $O^*(c^{\sqrt{k}})$, which the $k$-path problem can be reduced to. Is my understanding correct?