Determinant Sums for Undirected Hamiltonicity
(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:
https://lup.lub.lu.se/record/4318275
- author
- Björklund, Andreas LU
- organization
- publishing date
- 2014
- type
- Contribution to journal
- publication status
- published
- subject
- in
- SIAM Journal on Computing
- volume
- 43
- issue
- 1
- pages
- 280 - 299
- publisher
- Society for Industrial and Applied Mathematics
- 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
- 2016-04-01 14:59:49
- date last changed
- 2022-04-22 06:14:59
@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 = {{Society for Industrial and Applied Mathematics}}, series = {{SIAM Journal on Computing}}, title = {{Determinant Sums for Undirected Hamiltonicity}}, url = {{http://dx.doi.org/10.1137/110839229}}, doi = {{10.1137/110839229}}, volume = {{43}}, year = {{2014}}, }