This question is related to the previous discussion [here](https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length).


Due to the [result](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377) 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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-4TX797W-1&_user=7761201&_coverDate=02%252F28%252F2009&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1430356488&_rerunOrigin=google&_acct=C000051951&_version=1&_urlVersion=0&_userid=7761201&md5=903daeb9157174e1d0630f4b232f46e0).


There is an open problem in the [result](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377): 



> 
> 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?
> 
> 
> 



Finding a subgraph with slightly large size in planar graphs
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.


