There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances.

What is the fastest algorithm for HC problem on cubic planar graphs? Is there a sub-exponential algorithm for this class of graphs?


Planar separators easily give an $n^{O(\sqrt{n})}$ algorithm. This can be improved to $2^{O(\sqrt{n})}$ which is optimal (up to the constant in the exponent) for general planar graphs assuming ETH. I am not sure if being cubic helps or not.

  • $\begingroup$ I found that the treewidth problem on cubic planar graphs is an open problem according to graph classes database. So, it may be possible to get faster algorithms for cubic planar graphs. $\endgroup$ Sep 6 '14 at 11:53
  • $\begingroup$ I think by "open" the graph classes database usually means it's open whether a polytime algorithm exists. Not that it's open to prove some bound or other. $\endgroup$ Sep 7 '14 at 15:12

Actually, you don't need to exploit the "Catalan structure" in planar graphs to get a $2^{O(\sqrt{n})}$ time bound as Saeed suggests. Cygan et al. show you how to detect a Hamiltonian Cycle in $\operatorname{poly}(n)4^{\operatorname{tw}(G)}$ time even in general graphs, and in the final version of the paper they also describe how this can be improved to $\operatorname{poly}(n)3^{\operatorname{tw}(G)}$ time in cubic graphs.

The above algorithm is randomized. If you insist on a deterministic one, this is also possible with a slightly larger base constant, see Bodlaender et al.

  • $\begingroup$ I think the paper you mentioned is based on isolation lemma, it's also a nice idea but it's randomized algorithm. BTW bw < 1.5 tw < 3l were l is a min{diameter in G, diameter in dual of G} so in planar graph l belongs to O (\sqrt {n}). $\endgroup$
    – Saeed
    Sep 6 '14 at 11:31
  • $\begingroup$ Is it an open problem to improve the treewidth bound on cubic planar graphs to $tw=o(\sqrt{n})$? $\endgroup$ Sep 6 '14 at 11:37
  • 2
    $\begingroup$ @MohammadAl-Turkistany, Wall is planar and almost cubic graph and its treewidth (and its dual tw) is $\theta(\sqrt{n})$. (P.S: just adding edge between some of vertices in its outer face makes it cubic, but does not decrease the treewidth and does not effect planarity). $\endgroup$
    – Saeed
    Sep 6 '14 at 13:02
  • $\begingroup$ +1 Thank you for your answer. I wish that I was able to accept more than one answer. $\endgroup$ Sep 7 '14 at 17:26

As mentioned, different methods such as branch decomposition (or tree decomposition) give subexponential algorithm which can improve simply by Catalan structure in planar graph to $2^{O(\sqrt{n})}$. Furthermore we can extend those results to graphs of bounded genus, that means even in graphs of bounded genus (and even on excluded minors) the problem is subexponential time solvable as described in Dynamic Programming for Graphs on surfaces.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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