Advanced

Below All Subsets for Some Permutational Counting Problems

Björklund, Andreas LU (2016) 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) p.1-17
Abstract
We show that the two problems of computing the permanent of an n*n matrix of poly(n)-bit integers and counting the number of Hamiltonian cycles in a directed n-vertex multigraph with exp(poly(n)) edges can be reduced to relatively few smaller instances of themselves. In effect we derive the first deterministic algorithms for these two problems that run in o(2^n) time in the worst case. Classic poly(n)2^n time algorithms for the two problems have been known since the early 1960's. Our algorithms run in 2^{n-Omega(sqrt{n/log(n)})} time.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
pages
1 - 17
conference name
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
DOI
10.4230/LIPIcs.SWAT.2016.17
language
English
LU publication?
yes
id
eab0c0e5-0561-40ec-9269-eb93f444b820
date added to LUP
2016-07-28 12:51:15
date last changed
2016-08-23 12:39:30
@misc{eab0c0e5-0561-40ec-9269-eb93f444b820,
  abstract     = {We show that the two problems of computing the permanent of an n*n matrix of poly(n)-bit integers and counting the number of Hamiltonian cycles in a directed n-vertex multigraph with exp(poly(n)) edges can be reduced to relatively few smaller instances of themselves. In effect we derive the first deterministic algorithms for these two problems that run in o(2^n) time in the worst case. Classic poly(n)2^n time algorithms for the two problems have been known since the early 1960's. Our algorithms run in 2^{n-Omega(sqrt{n/log(n)})} time. },
  author       = {Björklund, Andreas},
  language     = {eng},
  pages        = {1--17},
  series       = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  title        = {Below All Subsets for Some Permutational Counting Problems},
  url          = {http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.17},
  year         = {2016},
}