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.
No comments:
Post a Comment