7
$\begingroup$

optimization problem

Input: a 3-connected cubic planar graph

feasible solution: A simple path

measure to optimize: length of the simple path

Is there a constant approximation algorithm for this problem?

The Hamiltonian circuit problem on 3-connected cubic planar graphs is NP-Complete in this paper.

A relevant question about for cubic Hamiltonian graph shows that there is no constant approximation algorithm for longest path on cubic graphs.

I'm also interested in the version where the input is a maximal planar graph.

$\endgroup$
3
  • $\begingroup$ Out of curiosity, what is the motivation for this particular problem for this particular class of graphs? As a wild guess, is there any connection to the Hirsch conjecture? $\endgroup$ Commented Oct 23, 2011 at 21:46
  • $\begingroup$ I did not have Hirsch conjecture in mind. Consider the following problem: There is a planar embedding of a graph. One want to find a simple curve on the plane that maximizes the number of vertices visited without cross any edge twice. If there is a constant approximation for this problem, then there will be a constant approximation for the problem in the question. $\endgroup$
    – Chao Xu
    Commented Oct 23, 2011 at 22:35
  • $\begingroup$ Hmm, I have trouble understanding the motivation for your other problem (“find a simple curve on the plane that maximizes the number of vertices visited without cross any edge twice”), but thanks for the reply! $\endgroup$ Commented Oct 24, 2011 at 13:00

0

Your Answer

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