Finding a subgraph with slightly large size in planar graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:54:27Z http://mathoverflow.net/feeds/question/35560 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs Finding a subgraph with slightly large size in planar graphs Hsien-Chih Chang 2010-08-14T05:44:00Z 2010-08-24T11:10:12Z <p>This question is related to the previous discussion <a href="http://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length" rel="nofollow">here</a>.</p> <p>Due to the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377" rel="nofollow">result</a> 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 <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V0F-4TX797W-1&amp;_user=7761201&amp;_coverDate=02%252F28%252F2009&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1430356488&amp;_rerunOrigin=google&amp;_acct=C000051951&amp;_version=1&amp;_urlVersion=0&amp;_userid=7761201&amp;md5=903daeb9157174e1d0630f4b232f46e0" rel="nofollow">this paper</a>.</p> <p>There is an open problem in the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377" rel="nofollow">result</a>: </p> <blockquote> <p>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?</p> </blockquote> http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs/36415#36415 Answer by Robin Kothari for Finding a subgraph with slightly large size in planar graphs Robin Kothari 2010-08-22T23:00:14Z 2010-08-22T23:00:14Z <p>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. </p> <p>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).</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs/36426#36426 Answer by Ryan Williams for Finding a subgraph with slightly large size in planar graphs Ryan Williams 2010-08-23T05:28:00Z 2010-08-23T05:28:00Z <p>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.</p> <p>For general <em>directed</em> 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: <a href="http://repository.upenn.edu/cis_papers/205/" rel="nofollow">http://repository.upenn.edu/cis_papers/205/</a></p> <blockquote> <p>Andreas Björklund, Thore Husfeldt, Sanjeev Khanna: Approximating Longest Directed Paths and Cycles. ICALP 2004: 222-233</p> </blockquote> <p>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. </p> <blockquote> <p>Harold N. Gabow, Shuxin Nie: Finding Long Paths, Cycles and Circuits. ISAAC 2008:752-763</p> </blockquote> <p>I don't know what bearing this has on the planar case, but it certainly seems relevant.</p> http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs/36543#36543 Answer by Hsien-Chih Chang for Finding a subgraph with slightly large size in planar graphs Hsien-Chih Chang 2010-08-24T11:10:12Z 2010-08-24T11:10:12Z <p>It seems to me that the following paper solves the $k$-path problem for $k = O(\log^2 n)$ in polynomial time:</p> <blockquote> <p>Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender and Fedor V. Fomin: <a href="http://www.springerlink.com/content/33kja2k4b1ghh12c/" rel="nofollow">Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions</a>. ESA 2005</p> </blockquote> <p>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?</p>