1
$\begingroup$

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class, listed in the above database of graph classes, where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class, listed in the above database of graph classes, where one of the two problems is known to be polynomial-time solvable while the other is known to be $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.

$\endgroup$
  • $\begingroup$ Take the class of graphs that have at least one vertex of degree 1. The complexity of HC is constant on this class, whereas HP is NPC. $\endgroup$ – Michal R. Przybylek Dec 18 '13 at 21:09
1
$\begingroup$

There are silly examples. Consider the class "graphs that have a degree $1$ vertex". These can never have a Hamiltonian cycle, so the cycle problem is in $P$. If $G$ is $H$ with one extra vertex $u$ neighboring the vertex $v$ of $H$, then $G$ has a Hamiltonian path if and only if $H$ has a Hamiltonian path starting in $v$, and that's NP-complete. (If we had a polynomial time algorithm for testing whether a graph with $n$ vertices had a Hamiltonian path starting at a particular vertex, then running this algorithm $n$ times would be a polynomial time algorithm for whether the graph had a Hamiltonian path.)

$\endgroup$
  • $\begingroup$ I'm looking for non-silly classes :). I'm interested in interesting graph classes (similar to the ones in my post) with infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs. The same applies to the Hamiltonian path property. $\endgroup$ – Mohammad Al-Turkistany Dec 18 '13 at 21:47
  • $\begingroup$ @MohammadAl-Turkistany, I don't think you've asked a research-level question and I doubt it's possible to provide a research-level answer. Here is another great observation --- take the very interesting class of graphs that have at least one vertex of degree 1 and merge it with the very interesting class of graphs consisting of a single cycle. $\endgroup$ – Michal R. Przybylek Dec 18 '13 at 21:59
  • $\begingroup$ @MichalR.Przybylek I edited the question to restrict the scope and make it answerable $\endgroup$ – Mohammad Al-Turkistany Dec 18 '13 at 22:33

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.