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.
Comments (2)
- +0 – 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 ? — Dec 07, 2010 at 20:32
- +1 – 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. — Dec 07, 2010 at 21:03
External Links
External links referenced by this document: