Andreas Björklund:
Determinant Sums for Undirected Hamiltonicity
Determining whether an undirected graph G has a Hamiltonian cycle is a well known NP-hard problem, and a special case of the classical travelling salesperson problem. It has long been known that on graphs with n vertices, the problem can be solved in time O*(2n) (the O* notation hides low order multiplicative factors), either by using dynamic programming, or by using the inclusion-exclusion principle (for the latter algorithm, polynomial space suffices). Breaking the O*(2n) barrier was a well known open question.
This paper breaks that barrier. It provides a randomized algorithm that finds a Hamiltonian cycle (if one exists) in expected time min[O*(2n-i), O*(1.657n)] and polynomial space, where i denotes the size of the maximum independent set. Moreover, using self reducibility, the algorithm also solves the TSP problem on instances with integer edge lengths, paying a multiplicative factor of w in the running time, where w is the sum of the edge lengths.
The algorithm is a tour de force in the use of algebraic techniques. It draws inspiration from algorithms developed for the k-path problem, which is a parameterized version of the Hamiltonian path problem, and also from earlier work of the author on other problems. It introduces several new ideas, such as reduction of Hamiltonicity to a labelled Hamiltonicity problem on a graph with fewer vertices, and counting (with cancelations) weighted cycle covers in this new graph, while using the determinant for this purpose. The paper is a testimony to the high level of sophistication achieved in the design of exact algorithms.