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.

Improve this question
$\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
    Commented Dec 18, 2013 at 21:09

2 Answers 2

Reset to default
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.)

Improve this answer
$\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
    Commented Dec 18, 2013 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
    Commented Dec 18, 2013 at 21:59
  • $\begingroup$ @MichalR.Przybylek I edited the question to restrict the scope and make it answerable $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 18, 2013 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
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .