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$
  • $\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$ – Tsuyoshi Ito Oct 23 '11 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 Oct 23 '11 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$ – Tsuyoshi Ito Oct 24 '11 at 13:00

Your Answer

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

Browse other questions tagged or ask your own question.