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?
$\begingroup$
$\endgroup$
asked Sep 5, 2014 at 13:33
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Sep 5, 2014 at 15:48
-
$\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$ Commented Sep 6, 2014 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$ Commented Sep 7, 2014 at 15:12
$\begingroup$
$\endgroup$
4
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.
answered Sep 6, 2014 at 6:57
-
$\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$– SaeedCommented Sep 6, 2014 at 11:31
-
$\begingroup$ Is it an open problem to improve the treewidth bound on cubic planar graphs to $tw=o(\sqrt{n})$? $\endgroup$ Commented Sep 6, 2014 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$– SaeedCommented Sep 6, 2014 at 13:02
-
$\begingroup$ +1 Thank you for your answer. I wish that I was able to accept more than one answer. $\endgroup$ Commented Sep 7, 2014 at 17:26
$\begingroup$
$\endgroup$
0
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.
