14
$\begingroup$

The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The 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 is solvable in polynomial time via a non-trivial algorithm, but the 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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
20
$\begingroup$

Cographs 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; 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Dec 7, 2010 at 20:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Dec 7, 2010 at 21:03
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, of course, thank you! Forgot to exclude complete graphs, and for that matter all classes of graphs where HC is solvable trivially. $\endgroup$
    – Standa Zivny
    Dec 7, 2010 at 12:36
  • 3
    $\begingroup$ @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.” $\endgroup$
    – Tsuyoshi Ito
    Dec 7, 2010 at 12:48
  • $\begingroup$ @Tsuyoshi Ito: A good point, I've edited the question. $\endgroup$
    – Standa Zivny
    Dec 7, 2010 at 13:03
  • $\begingroup$ @StandaZivny - Not all graphs which are trivial for HC are hard for TSP, e.g. path graphs. $\endgroup$
    – R B
    Aug 7, 2014 at 5:16
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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