4
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 14, 2010 at 16:15
  • $\begingroup$ Thank you for the correction, knowing that this is indeed an open problem still helps me a lot, thanks very much!! $\endgroup$ Aug 15, 2010 at 19:35
  • $\begingroup$ The link to Ryan Williams' paper at sciencedirect.com is broken. Perhaps it is meant to point to this one—? Williams, Ryan, Finding paths of length $k$ in $O^{*}(2^k)$ time, Inf. Process. Lett. 109, No. 6, 315–318 (2009). Zbl 1191.68857. $\endgroup$ Sep 10, 2022 at 9:36

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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}}$. $\endgroup$ Aug 23, 2010 at 5:12
  • 1
    $\begingroup$ 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)? $\endgroup$ Aug 23, 2010 at 6:10
  • $\begingroup$ Looks OK. Doesn't this also show: finding an $\omega(\log n)$-path in polytime in an undirected graph implies subexponential 3SAT? $\endgroup$ Aug 24, 2010 at 5:50
  • $\begingroup$ Seems correct!! $\endgroup$ Aug 24, 2010 at 8:48
  • $\begingroup$ @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. $\endgroup$ Aug 24, 2010 at 18:35
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Let me check out the papers, to get some ideas from them. After that I'll post some comments... $\endgroup$ Aug 23, 2010 at 15:59
1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$ Aug 24, 2010 at 16:13
  • $\begingroup$ That is really a problem, maybe I'll try to use the method directly. Thank you for all your help!! $\endgroup$ Aug 24, 2010 at 16:58
  • $\begingroup$ The link to the paper at springerlink.com is broken, but the article can be found at doi:10.1007/11561071_11. $\endgroup$ Sep 10, 2022 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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