18
$\begingroup$

While searching The information System on Graph Classes and their Inclusions, I found 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 bipartite maximum degree 3 graphs, maximum degree 3 grid graphs, and 2-connected cubic planar graphs. Also this phenomena applies to circle graphs and triangular grid graphs.

Is there an update to the complexity of Hamiltonian path problem on those classes? Is there an explanation for this phenomena?

EDIT: 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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I wonder whether there is an interesting graph class for which HP is in $P$ but HC is $NP$-complete. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 9, 2013 at 21:28
  • $\begingroup$ In general, Is there any graph class for which one of the problems (HC and HP) is $NP$-complete and the other is in $P$ or in $NPI$? I'm looking for published results for HC and HP problems. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 10, 2013 at 9:23
  • $\begingroup$ For what it's worth (not much), Hamiltonian Path and Hamiltonian Cycle have different complexity on trees: cycle is trivial but path requires a linear scan to see if there's a vertex of degree more than two. $\endgroup$
    – David Richerby
    Commented Dec 10, 2013 at 15:51
  • $\begingroup$ It is unlikely that HP is in $P$ and HC is $NP$-complete for any graph class since there is a Cook reduction from HC to HP which makes at most $O(|E|)$ calls to HP's oracle. The real question is whether a Karp reduction exist ($HC<_P^m HP$). $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 10, 2013 at 18:02

3 Answers 3

Reset to default
6
$\begingroup$

The Hamiltonian path problem on grid graphs with maximum degree 3 is NP-complete. The proof is in C. H. Papadimitriou and U. V. Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231–246 (Theorem 2)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Marzio, Are they using the same definition used in the database for grid graphs? (since they are different definitions in the literature) $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 10, 2013 at 13:53
  • $\begingroup$ A grid graph is a finite, node-induced subgraph of $G^\infty$, the infinite graph whose vertex set consists of all points of the plane with integer coordinates and in which two vertices are connected if and only if the Euclidean distance between them is 1; so a grid graph can have "holes" and the theorem is proved for (restricted to) grid graphs in which vertices have maximum degree 3. $\endgroup$
    – Marzio De Biasi
    Commented Dec 10, 2013 at 14:52
  • $\begingroup$ Thanks Marzio, So, for this class, HC and HP have the same complexity. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 10, 2013 at 14:56
  • $\begingroup$ @MohammadAl-Turkistany: another note: grid graphs (and grid graphs with max degree 3) are also bipartite, so HP should be NP-complete for bipartite graphs with maximum degree 3, too. $\endgroup$
    – Marzio De Biasi
    Commented Dec 10, 2013 at 15:53
3
$\begingroup$

There has been an update to the information System on Graph Classes and their Inclusions. Now, the Hamiltonian cycle problem and Hamiltonian path problem are stated to be NP-complete on 2-connected cubic planar graphs.

However, the computational complexities of HC and HP problems are listed unknown for one problem and NP-complete for the other on circle graphs, triangular grid graphs, and solid grid graphs.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You say "... complexities of HC and HP problems are still different ..."; perhaps it's better to say that "for these classes of graphs HC is NPC, but HP has still unknown complexity" $\endgroup$
    – Marzio De Biasi
    Commented Feb 4, 2014 at 11:19
  • $\begingroup$ @MarzioDeBiasi Thanks for your valuable comment. I edited to reflect your suggestion. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 4, 2014 at 11:41
  • $\begingroup$ Do I miss something? HC is polynomial time solvable in solid grid graphs. ieeexplore.ieee.org/document/646138 $\endgroup$
    – Saeed
    Commented Mar 15, 2017 at 13:51
  • $\begingroup$ @MohammadAl-Turkistany Are there any known results on the complexity of counting Hamilton cycles in solid grid graphs? $\endgroup$
    – delete000
    Commented Apr 13, 2022 at 13:11
0
$\begingroup$

While you are looking for updates to the status of various Ham-Cycle or Ham-Path complexities, I've found a longer list of classes which have one of the problems characterized while the other is unknown.

I created this list by using ISGCI's lists of all classes categorized by their complexity status for particular problems: Ham-path and Ham-cycle:

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

I compared everything Linear or Polynomial vs all other categories (GI-complete, NP-Hard, NP-Complete, Unknown to ISGCI), just to see if there were any abnormalities of finding one of the problems hard and the other easy. (That is, I grouped the Linear and Polynomial cases into one category of polytime solvable)

There are no classes that show up with a complexity 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

It could be some of these unknown Ham-path complexities are trivial implications of the corresponding Ham-cycle algorithm, but no one has explicitly observed or mentioned it yet. And it could be that there are results out there that ISGCI is not aware of. But this seems like a list that could keep someone busy while learning about definitions of various kinds of graph classes (say, a student assistant), or writing a survey paper.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.