Theoretical Computer Science
cc.complexity-theory np-hardness hamiltonian-paths tsp graph-classes
Updated Wed, 08 Jun 2022 20:20:45 GMT

# Classes of graphs with easy Hamiltonian cycle but NP-hard TSP

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.

## Solution

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.