Below All Subsets for Some Permutational Counting Problems
(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:
https://lup.lub.lu.se/record/eab0c0e5-0561-40ec-9269-eb93f444b820
- author
- Björklund, Andreas LU
- organization
- publishing date
- 2016
- 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}}, }