The Traveling Salesman Problem for Cubic Graphs
Vol. 11, no. 1, pp. 61-81, 2007. Regular paper.
Abstract We show how to find a Hamiltonian cycle in a graph of degree at most three with
n vertices, in time
O(2
n/3) ≈ 1.260
n and linear space. Our algorithm can find the minimum weight Hamiltonian cycle (traveling salesman problem), in the same time bound.
We can also count or list all Hamiltonian cycles in a degree three graph
in time
O(2
3n/8) ≈ 1.297
n.
We also solve the traveling salesman problem in graphs of degree at most four, by randomized and deterministic algorithms with runtime
O((27/4)
n/3) ≈ 1.890
n and
O((27/4+ϵ)
n/3) respectively. Our algorithms allow the input to specify a set of forced edges which must be part of any generated cycle.
Our cycle listing algorithm shows that every degree three graph has
O(2
3n/8) Hamiltonian cycles; we also exhibit a family of graphs with 2
n/3 Hamiltonian cycles per graph.