Determinant Sums for Undirected Hamiltonicity
(2014) In SIAM Journal on Computing 43(1). p.280299 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. 6163], [M. Held and R. M. Karp, J. Soc. Indust. Appl. Math., 10 (1962), pp. 196210]. ($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 NPhard 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. 6163], [M. Held and R. M. Karp, J. Soc. Indust. Appl. Math., 10 (1962), pp. 196210]. ($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 NPhard 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:
http://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
 SIAM Publications
 external identifiers

 wos:000333538300015
 scopus:84896995984
 ISSN
 00975397
 DOI
 10.1137/110839229
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 92db10298df3491d9233a31f8bf4c773 (old id 4318275)
 date added to LUP
 20140225 10:02:57
 date last changed
 20170924 04:14:57
@article{92db10298df3491d9233a31f8bf4c773, 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. 6163], [M. Held and R. M. Karp, J. Soc. Indust. Appl. Math., 10 (1962), pp. 196210]. ($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 NPhard 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 = {00975397}, language = {eng}, number = {1}, pages = {280299}, 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}, }