# Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

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.

• 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. – Michal R. Przybylek Dec 18 '13 at 21:09

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.)

• 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. – Mohammad Al-Turkistany Dec 18 '13 at 21:47
• @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. – Michal R. Przybylek Dec 18 '13 at 21:59
• @MichalR.Przybylek I edited the question to restrict the scope and make it answerable – Mohammad Al-Turkistany Dec 18 '13 at 22:33

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

I think the answer is 'no' (unless there is a bug in my code). The list of all classes categorized by their complexity status is given for each of Ham-path and Ham-cycle:

I tested everything Linear or Polynomial vs all other categories (GI-complete, NP-Hard, NP-Complete, Unknown to ISGCI).

Surprisingly (or not?) there are no classes that show up with a polynomial mismatch except when it is compared to the `Unknown' classification. But what is furthermore somewhat surprising is that in all these cases, it is Ham-Cycle which is known polytime, while Ham-Path is the unknown one.

The classes I found were:

• 66 (biconvex) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 67 (convex) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 407 (($$P_5$$,claw)-free) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 508 ((2$$K_2$$,claw)-free) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 645 (equiv to biconvex) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 1144 (claw-free locally connected) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 1146 ($$K_{1,4}$$-free, locally connected, almost claw-free) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 1234 (($$P_6$$,claw)-free) has linear HAM-cycle but Unknown to ISGCI HAM-path
• 644 (circular convex bipartite) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1058 (solid grid - you mentioned above) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1094 (locally connected and max deg 4) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1142 (2-connected $$\cap$$ linearly convex triangular grid graph) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1143 (locally connected $$\cap$$ triangular grid) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1197 (adjoint graphs) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1198 (quasi-adjoint graphs) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1199 (directed line graphs) has polynomial HAM-cycle but Unknown to ISGCI HAM-path
• 1201 (equiv to directed line) has polynomial HAM-cycle but Unknown to ISGCI HAM-path