<p>The <em>Hamiltonian path problem on grid graphs with maximum degree 3</em> is NP-complete. The proof is in <a href="http://www.sciencedirect.com/science/article/pii/0196677484900294">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</a> (Theorem 2)</p>

CC BY-SA 3.0
2013-12-10T13:53:33.473Z
Thanks Marzio, Are they using the same definition used in the database for grid graphs? (since they are different definitions in the literature)
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-10T14:52:11.953Z
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.
Marzio De Biasi
CC BY-SA 3.0
2013-12-10T14:56:24.670Z
Thanks Marzio, So, for this class, HC and HP have the same complexity.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-10T15:53:56.763Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2013-12-10T13:45:10.283Z
2013-12-10T13:45:10.283Z
Marzio De Biasi
<p>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.</p>

<p>However, the computational complexities of HC and HP problems are listed unknown for one problem and NP-complete for the other on <a href="http://www.graphclasses.org/classes/gc_132.html" rel="nofollow">circle graphs</a>, <a href="http://www.graphclasses.org/classes/gc_1118.html" rel="nofollow">triangular grid graphs</a>, and <a href="http://www.graphclasses.org/classes/gc_1058.html" rel="nofollow">solid grid graphs</a>.</p>

CC BY-SA 3.0
2014-02-04T11:19:50.887Z
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"
Marzio De Biasi
CC BY-SA 3.0
2014-02-04T11:41:52.533Z
@MarzioDeBiasi Thanks for your valuable comment. I edited to reflect your suggestion.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-03-15T13:51:58.470Z
Do I miss something? HC is polynomial time solvable in solid grid graphs. http://ieeexplore.ieee.org/document/646138/
Saeed
CC BY-SA 4.0
2022-04-13T13:11:22.833Z
@MohammadAl-Turkistany Are there any known results on the complexity of *counting* Hamilton cycles in solid grid graphs?
delete000
CC BY-SA 3.0
2014-02-04T10:44:37.947Z
2014-02-04T11:40:38.450Z
2014-02-04T11:40:38.450Z
Mohammad Al-Turkistany
<p>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.</p>
<p>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:</p>
<p><a href="https://www.graphclasses.org/classes/problem_Hamiltonian_path.html" rel="nofollow noreferrer">https://www.graphclasses.org/classes/problem_Hamiltonian_path.html</a>
<a href="https://www.graphclasses.org/classes/problem_Hamiltonian_cycle.html" rel="nofollow noreferrer">https://www.graphclasses.org/classes/problem_Hamiltonian_cycle.html</a></p>
<p>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)</p>
<p>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.</p>
<p>The classes I found were:</p>
<ul>
<li>66 (biconvex) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>67 (convex) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>407 ((<span class="math-container">$P_5$</span>,claw)-free) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>508 ((2<span class="math-container">$K_2$</span>,claw)-free) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>645 (equiv to biconvex) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1144 (claw-free locally connected) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1146 (<span class="math-container">$K_{1,4}$</span>-free, locally connected, almost claw-free) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1234 ((<span class="math-container">$P_6$</span>,claw)-free) has linear HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>644 (circular convex bipartite) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1058 (solid grid - you mentioned above) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1094 (locally connected and max deg 4) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1142 (2-connected <span class="math-container">$\cap$</span> linearly convex triangular grid graph) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1143 (locally connected <span class="math-container">$\cap$</span> triangular grid) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1197 (adjoint graphs) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1198 (quasi-adjoint graphs) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1199 (directed line graphs) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
<li>1201 (equiv to directed line) has polynomial HAM-cycle but Unknown to ISGCI HAM-path</li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2020-09-14T18:25:13.730Z
2020-09-14T18:25:13.730Z
JimN
<p>While searching <a href="http://www.graphclasses.org/index.html">The information System on Graph Classes and their Inclusions</a>, I found several graph classes for which  the Hamiltonian Cycle problem is NP-complete while the complexity of Hamiltonian Path problems is <strong>NOT</strong> 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.</p>

<blockquote>
  <p>Is there an update to the complexity of Hamiltonian path problem on those classes? Is there an explanation for this phenomena?</p>
</blockquote>

<p><strong>EDIT</strong>: I found in the graph classes database a weird case of <a href="http://www.graphclasses.org/classes/gc_1058.html">solid grid graphs</a> where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of <strong>unknown</strong> complexity.</p>

CC BY-SA 3.0
2013-12-09T21:28:49.253Z
I wonder whether there is an interesting graph class for which HP is in $P$ but HC is $NP$-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-10T09:23:02.300Z
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.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-10T15:51:00.527Z
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.
David Richerby
CC BY-SA 3.0
2013-12-10T18:02:11.430Z
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$).
Mohammad Al-Turkistany
<cc.complexity-theory><graph-theory>
Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
Mohammad Al-Turkistany
# Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

(Asked by: username_0 on 2013-12-09)

While searching [The information System on Graph Classes and their Inclusions](http://www.graphclasses.org/index.html), 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](http://www.graphclasses.org/classes/gc_1058.html) where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of **unknown** complexity.

**Tags:** cc.complexity-theory, graph-theory
> **Comments:**
> **username_0**: I wonder whether there is an interesting graph class for which HP is in $P$ but HC is $NP$-complete.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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$).  

---

## 3 answers

### Answer by username_2 on 2013-12-10. Score: 6

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](http://www.sciencedirect.com/science/article/pii/0196677484900294) (Theorem 2)

> **Comments:**
> **username_0**: Thanks Marzio, Are they using the same definition used in the database for grid graphs? (since they are different definitions in the literature)  
> **username_2**: 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.  
> **username_0**: Thanks Marzio, So, for this class, HC and HP have the same complexity.  
> **username_2**: @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.  

---

### Answer by username_0 on 2014-02-04. Score: 3

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](http://www.graphclasses.org/classes/gc_132.html), [triangular grid graphs](http://www.graphclasses.org/classes/gc_1118.html), and [solid grid graphs](http://www.graphclasses.org/classes/gc_1058.html).

> **Comments:**
> **username_2**: 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"  
> **username_0**: @MarzioDeBiasi Thanks for your valuable comment. I edited to reflect your suggestion.  
> **username_3**: Do I miss something? HC is polynomial time solvable in solid grid graphs. http://ieeexplore.ieee.org/document/646138/  
> **username_4**: @MohammadAl-Turkistany Are there any known results on the complexity of *counting* Hamilton cycles in solid grid graphs?  

---

### Answer by username_5 on 2020-09-14. Score: 0

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.


---

