17
$\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.

$\endgroup$
  • 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 Dec 9 '13 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 Dec 10 '13 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 Dec 10 '13 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 Dec 10 '13 at 18:02
5
$\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)

$\endgroup$
  • $\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 Dec 10 '13 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 Dec 10 '13 at 14:52
  • $\begingroup$ Thanks Marzio, So, for this class, HC and HP have the same complexity. $\endgroup$ – Mohammad Al-Turkistany Dec 10 '13 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 Dec 10 '13 at 15:53
2
$\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.

$\endgroup$
  • $\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 Feb 4 '14 at 11:19
  • $\begingroup$ @MarzioDeBiasi Thanks for your valuable comment. I edited to reflect your suggestion. $\endgroup$ – Mohammad Al-Turkistany Feb 4 '14 at 11:41
  • $\begingroup$ Do I miss something? HC is polynomial time solvable in solid grid graphs. ieeexplore.ieee.org/document/646138 $\endgroup$ – Saeed Mar 15 '17 at 13:51

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.