Advanced

Determinant Sums for Undirected Hamiltonicity

Björklund, Andreas LU (2014) In SIAM Journal on Computing 43(1). p.280-299
Abstract
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.... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
SIAM Journal on Computing
volume
43
issue
1
pages
280 - 299
publisher
SIAM Publications
external identifiers
  • wos:000333538300015
  • scopus:84896995984
ISSN
0097-5397
DOI
10.1137/110839229
project
Exact algorithms
language
English
LU publication?
yes
id
92db1029-8df3-491d-9233-a31f8bf4c773 (old id 4318275)
date added to LUP
2014-02-25 10:02:57
date last changed
2017-09-24 04:14:57
@article{92db1029-8df3-491d-9233-a31f8bf4c773,
  abstract     = {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       = {Björklund, Andreas},
  issn         = {0097-5397},
  language     = {eng},
  number       = {1},
  pages        = {280--299},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {Determinant Sums for Undirected Hamiltonicity},
  url          = {http://dx.doi.org/10.1137/110839229},
  volume       = {43},
  year         = {2014},
}