Determinant Sums for Undirected Hamiltonicity

Summary, in English

We present a Monte Carlo algorithm for Hamiltonicity detection in an $n$-vertex undirected graph running in $O(1.657^{n})$ time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the $O^*(2^n)$ bound established for the traveling salesman problem (TSP) over 50 years ago [R. Bellman, J. Assoc. Comput. Mach., 9 (1962), pp. 61--63], [M. Held and R. M. Karp, J. Soc. Indust. Appl. Math., 10 (1962), pp. 196--210]. ($O^*(f(n))$ suppresses polylogarithmic functions in $f(n)$). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems. For bipartite graphs, we improve the bound to $O^*(\sqrt{2}^n)\subset O(1.415^{n})$ time. Both the bipartite and the general algorithm can be implemented to use space polynomial in $n$. We combine several recently resurrected ideas to get the results. Our main technical contribution is a new algebraic characterization of Hamiltonian graphs. We introduce an extension of Hamiltonicity called Labeled Hamiltonicity and relate it to a Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. The Labeled Cycle Cover Sum can be evaluated efficiently via determinants.

• Author: Andreas Björklund
• Department/s: Department of Computer Science; Parallel Systems
• Publishing year: 2014
• Language: English
• Pages: 280-299
• Publication/Series: SIAM Journal on Computing
• Volume: 43
• Issue: 1
• Links: http://dx.doi.org/10.1137/110839229
• Document type: Journal article
• Publisher: Society for Industrial and Applied Mathematics
• Topic: Computer Science
• Status: Published
• Project: Exact algorithms
• Research group: Algorithms
• ISBN/ISSN/Other: ISSN: 0097-5397