Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Below All Subsets for Some Permutational Counting Problems

Björklund, Andreas LU (2016) 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
host publication
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
article number
17
pages
1 - 17
conference name
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
conference location
Reykjavik, Iceland
conference dates
2016-06-22 - 2016-06-24
external identifiers
  • scopus:85011949857
ISBN
978-3-95977-011-8
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
2022-04-08 22:21:42
@inproceedings{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}},
  booktitle    = {{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}},
  isbn         = {{978-3-95977-011-8}},
  language     = {{eng}},
  pages        = {{1--17}},
  title        = {{Below All Subsets for Some Permutational Counting Problems}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.17}},
  doi          = {{10.4230/LIPIcs.SWAT.2016.17}},
  year         = {{2016}},
}