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.
BibTeX - Entry
@InProceedings{bjrklund:LIPIcs:2016:6039,
author = {Andreas Bj{\"o}rklund},
title = {{Below All Subsets for Some Permutational Counting Problems }},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {17:1--17:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-011-8},
ISSN = {1868-8969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6039},
URN = {urn:nbn:de:0030-drops-60399},
doi = {10.4230/LIPIcs.SWAT.2016.17},
annote = {Keywords: Matrix Permanent, Hamiltonian Cycles, Asymmetric TSP}
}
|
Keywords: |
|
Matrix Permanent, Hamiltonian Cycles, Asymmetric TSP |
|
Collection: |
|
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
22.06.2016 |
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)