Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
Just a small correction: color coding, while a very nice technique, is slower than you state for arbitrary bounded-size subgraphs H: it is more aimed at the case when H has a special form such as a path or a cycle. For arbitrary H it takes $O(n^{\sqrt k})$. For better linear time algorithms see my own paper arxiv.org/abs/cs.DS/9911003 or Dorn's improvement arxiv.org/abs/0909.4692 This doesn't answer your question about paths, though. I'm not sure open problems make good MO questions, and I don't think there has been much progress on your question since Alon et al. –  David Eppstein Aug 14 '10 at 16:15
    
Thank you for the correction, knowing that this is indeed an open problem still helps me a lot, thanks very much!! –  Hsien-Chih Chang 張顯之 Aug 15 '10 at 19:35

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
This argument is not quite formal: just because $(log^2 n)$-path can be found in polytime, that doesn't mean $k$-path is in $2^{\sqrt{k}}$. –  Ryan Williams Aug 23 '10 at 5:12
1  
The reduction I had in mind would take the graph in which you wish to find a k-path, and add extra isolated vertices to make the total number of vertices $2^\sqrt{k}$. Now we use the algorithm for finding $\log^2 n$ paths on this graph, which runs in time polynomial in $2^\sqrt{k}$, which is $2^{c\sqrt{k}}$ (for some constant c), which is sub-exponential in k. This solves Hamiltonian path in $2^{c\sqrt{n}}$. Have I made an error in this reduction (or in some other part of my informal argument)? –  Robin Kothari Aug 23 '10 at 6:10
    
Looks OK. Doesn't this also show: finding an $\omega(\log n)$-path in polytime in an undirected graph implies subexponential 3SAT? –  Ryan Williams Aug 24 '10 at 5:50
    
Seems correct!! –  Hsien-Chih Chang 張顯之 Aug 24 '10 at 8:48
    
@Ryan: Yes, it also implies that $\omega(\log n)$-path finding in polytime in an undirected graph implies sub-exponential time algorithms for 3SAT. (I believe this is why I stopped thinking about this problem.) But for the planar case there seems to be a gap between the best known algorithm and ETH-hardness result. I agree with you that it seems very plausible that the algorithm can be improved for planar graphs. –  Robin Kothari Aug 24 '10 at 18:35

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.

share|improve this answer
    
Let me check out the papers, to get some ideas from them. After that I'll post some comments... –  Hsien-Chih Chang 張顯之 Aug 23 '10 at 15:59

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?

share|improve this answer
1  
While it is easy to reduce $k$-path to $k$-cycle for general graphs, one needs to be careful to get this to work on planar graphs. (What if the two endpoints of your path are not on the same face?) At any rate it looks like you have found the right reference. Theirs looks like a generic method that can be applied directly to $k$-path (rather than via a reduction). –  Ryan Williams Aug 24 '10 at 16:13
    
That is really a problem, maybe I'll try to use the method directly. Thank you for all your help!! –  Hsien-Chih Chang 張顯之 Aug 24 '10 at 16:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.