License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.17
URN: urn:nbn:de:0030-drops-60399
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6039/
Go to the corresponding LIPIcs Volume Portal


Björklund, Andreas

Below All Subsets for Some Permutational Counting Problems

pdf-format:
LIPIcs-SWAT-2016-17.pdf (0.4 MB)


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
Seminar: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 21.06.2016


DROPS-Home | Fulltext Search | Imprint Published by LZI