<p>How about <strong>complete graphs</strong>? Since TSP can always be reduced to an instance on complete graphs (by adding proper distances between non-edges), it is still NP-hard to solve TSP on complete graphs. But any complete graphs is Hamiltonian.</p>

CC BY-SA 2.5
2010-12-07T12:36:07.127Z
Yes, of course, thank you! Forgot to exclude complete graphs, and for that matter all classes of graphs where HC is solvable trivially.
Standa Zivny
CC BY-SA 2.5
2010-12-07T12:48:00.277Z
@Standa Zivny: I am not sure if you are going to edit the question or not, but if you want to exclude “all classes of graphs where HC is solvable trivially,” you should edit the question.  However, I doubt that it is possible to formulate the distinction between the case where HC can be solved “easily” and the case where HC can be solved “trivially.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-07T13:03:12.860Z
@Tsuyoshi Ito: A good point, I've edited the question.
Standa Zivny
CC BY-SA 3.0
2014-08-07T05:16:29.390Z
@StandaZivny - Not all graphs which are trivial for HC are hard for TSP, e.g. path graphs.
R B
CC BY-SA 2.5
2010-12-07T11:34:27.740Z
2010-12-07T11:34:27.740Z
Hsien-Chih Chang 張顯之
<p>There are many infinite classes of graphs which are known to have hamiltonian circuits. Two especially interesting classes are the n-cubes and the Halin graphs. One way of thinking of the Halin graphs is to embed a tree with at least 3 vertices and which no vertices of valence two in the plane, and then pass a simple circuit through the 1-valent vertices of the tree.</p>

<p><a href="http://en.wikipedia.org/wiki/Halin_graph" rel="nofollow">http://en.wikipedia.org/wiki/Halin_graph</a></p>

<p>These graphs are known to have an HC and in fact they are either pancyclic (circuits of all lengths) or lack exactly one circuit length which must be of even length.</p>

CC BY-SA 2.5
2010-12-07T14:43:14.820Z
2010-12-07T14:43:14.820Z
Joseph Malkevitch
<p><a href="http://en.wikipedia.org/wiki/Cograph">Cographs</a> are not always Hamiltonian, have polynomial time tests for Hamiltonicity, and are NP-hard to solve the traveling salesman problem for.</p>

<p>More generally the Hamiltonian cycle problem can be solved in polynomial time (but is not fixed-parameter tractible) on graphs of bounded <a href="http://en.wikipedia.org/wiki/Clique-width">clique-width</a>; see, e.g., Fomin et al., "Clique-width: on the price of generality", SODA'09. But again because these graph families include the complete graphs, the TSP is hard on these graphs.</p>

CC BY-SA 2.5
2010-12-07T20:32:59.683Z
I'm curios about your last statement. Is that because the TSP tour would effectively identify the cliques by having all clique vertices be contiguous in the tour ?
Suresh Venkat
CC BY-SA 2.5
2010-12-07T21:03:30.363Z
No, I mean simply that TSP is hard even in a complete graph, and complete graphs are among the graphs with bounded clique-width. Complete graphs themselves don't provide a good answer to the question because Hamiltonicity is trivial for them, but superclasses of the cliques (such as the cographs) may have nontrivial but polynomial Hamiltonicity tests.
David Eppstein
CC BY-SA 2.5
2010-12-07T19:53:30.340Z
2010-12-07T21:35:35.457Z
2010-12-07T21:35:35.457Z
David Eppstein
<p>The <a href="http://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian Cycle Problem</a> (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">Travelling Salesman Problem</a> (TSP) consists in finding a cycle that goes through all vertices in a given edge-weighted graph and minimizes the total distance measured by the sum of the weights of the edges in the cycle. HC is a special case of TSP, and both are known to be NP-complete [Garey &amp; Johnson]. (See the links above for more details and variants of these problems.)</p>

<p>Are there any studied classes of graphs on which the <a href="http://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian Cycle Problem</a> is solvable in polynomial time via a <em>non-trivial</em> algorithm, but the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">Travelling Salesman Problem</a> is NP-hard? </p>

<p><em>Non-trivial</em> is to exclude classes such as the class of complete graphs, where a Hamiltonian cycle is guaranteed to exist and can be found easily, or generally classes of graphs where a HC is always guaranteed to exist.</p>

<cc.complexity-theory><np-hardness><hamiltonian-paths><tsp><graph-classes>
Classes of graphs with easy Hamiltonian cycle but NP-hard TSP
Standa Zivny
# Classes of graphs with easy Hamiltonian cycle but NP-hard TSP

(Asked by: username_0 on 2010-12-07)

The [Hamiltonian Cycle Problem](http://en.wikipedia.org/wiki/Hamiltonian_path) (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The [Travelling Salesman Problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem) (TSP) consists in finding a cycle that goes through all vertices in a given edge-weighted graph and minimizes the total distance measured by the sum of the weights of the edges in the cycle. HC is a special case of TSP, and both are known to be NP-complete [Garey & Johnson]. (See the links above for more details and variants of these problems.)

Are there any studied classes of graphs on which the [Hamiltonian Cycle Problem](http://en.wikipedia.org/wiki/Hamiltonian_path) is solvable in polynomial time via a *non-trivial* algorithm, but the [Travelling Salesman Problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem) is NP-hard?

*Non-trivial* is to exclude classes such as the class of complete graphs, where a Hamiltonian cycle is guaranteed to exist and can be found easily, or generally classes of graphs where a HC is always guaranteed to exist.

**Tags:** cc.complexity-theory, np-hardness, hamiltonian-paths, tsp, graph-classes

---

## 3 answers

### Answer by username_5 on 2010-12-07. Score: 20 | Accepted answer

[Cographs](http://en.wikipedia.org/wiki/Cograph) are not always Hamiltonian, have polynomial time tests for Hamiltonicity, and are NP-hard to solve the traveling salesman problem for.

More generally the Hamiltonian cycle problem can be solved in polynomial time (but is not fixed-parameter tractible) on graphs of bounded [clique-width](http://en.wikipedia.org/wiki/Clique-width); see, e.g., Fomin et al., "Clique-width: on the price of generality", SODA'09. But again because these graph families include the complete graphs, the TSP is hard on these graphs.

> **Comments:**
> **username_6**: I'm curios about your last statement. Is that because the TSP tour would effectively identify the cliques by having all clique vertices be contiguous in the tour ?  
> **username_5**: No, I mean simply that TSP is hard even in a complete graph, and complete graphs are among the graphs with bounded clique-width. Complete graphs themselves don't provide a good answer to the question because Hamiltonicity is trivial for them, but superclasses of the cliques (such as the cographs) may have nontrivial but polynomial Hamiltonicity tests.  

---

### Answer by username_1 on 2010-12-07. Score: 11

How about **complete graphs**? Since TSP can always be reduced to an instance on complete graphs (by adding proper distances between non-edges), it is still NP-hard to solve TSP on complete graphs. But any complete graphs is Hamiltonian.

> **Comments:**
> **username_0**: Yes, of course, thank you! Forgot to exclude complete graphs, and for that matter all classes of graphs where HC is solvable trivially.  
> **username_2**: @Standa Zivny: I am not sure if you are going to edit the question or not, but if you want to exclude “all classes of graphs where HC is solvable trivially,” you should edit the question.  However, I doubt that it is possible to formulate the distinction between the case where HC can be solved “easily” and the case where HC can be solved “trivially.”  
> **username_0**: @Tsuyoshi Ito: A good point, I've edited the question.  
> **username_3**: @StandaZivny - Not all graphs which are trivial for HC are hard for TSP, e.g. path graphs.  

---

### Answer by username_4 on 2010-12-07. Score: 3

There are many infinite classes of graphs which are known to have hamiltonian circuits. Two especially interesting classes are the n-cubes and the Halin graphs. One way of thinking of the Halin graphs is to embed a tree with at least 3 vertices and which no vertices of valence two in the plane, and then pass a simple circuit through the 1-valent vertices of the tree.

<http://en.wikipedia.org/wiki/Halin_graph>

These graphs are known to have an HC and in fact they are either pancyclic (circuits of all lengths) or lack exactly one circuit length which must be of even length.


---

