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$
1
  • $\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
3
$\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$
3
  • $\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
2
$\begingroup$

To answer your question:

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:

https://www.graphclasses.org/classes/problem_Hamiltonian_path.html https://www.graphclasses.org/classes/problem_Hamiltonian_cycle.html

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
$\endgroup$

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.