Document Open Access Logo

Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors

Authors Andreas Björklund, Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.25.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Björklund
  • Department of Computer Science, Lund University, Sweden
Ryan Williams
  • Department of Electrical Engineering and Computer Science & CSAIL, MIT, Cambridge, MA, USA

Funding

  • Björklund, Andreas: The Swedish Research Council grant VR 2016-03855 "Algebraic Graph Algorithms".
  • Williams, Ryan: The U.S. National Science Foundation grant CCF-1741615 "CAREER: Common Links in Algorithms and Complexity".

Cite As Get BibTex

Andreas Björklund and Ryan Williams. Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.25

Abstract

We show that the permanent of an n x n matrix over any finite ring of r <= n elements can be computed with a deterministic 2^{n-Omega(n/r)} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{n-Omega(n/(r log r))} time, implicit in [Björklund, Husfeldt, and Lyckberg, IPL 2017]. For the permanent over the integers of a 0/1-matrix with exactly d ones per row and column, we provide a deterministic 2^{n-Omega(n/(d^{3/4)})} time algorithm. This improves on a 2^{n-Omega(n/d)} time algorithm in [Cygan and Pilipczuk ICALP 2013]. We also show that the number of Hamiltonian cycles in an n-vertex directed graph of average degree delta can be computed by a deterministic 2^{n-Omega(n/(delta))} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{n-Omega(n/poly(delta))} time in [Björklund, Kaski, and Koutis, ICALP 2017].
A key tool in our approach is a reduction from computing the permanent to listing pairs of dissimilar vectors from two sets of vectors, i.e., vectors over a finite set that differ in each coordinate, building on an observation of [Bax and Franklin, Algorithmica 2002]. We propose algorithms that can be used both to derandomise the construction of Bax and Franklin, and efficiently list dissimilar pairs using several algorithmic tools. We also give a simple randomised algorithm resulting in Monte Carlo algorithms within the same time bounds.
Our new fast algorithms for listing dissimilar vector pairs from two sets of vectors are inspired by recent algorithms for detecting and counting orthogonal vectors by [Abboud, Williams, and Yu, SODA 2015] and [Chan and Williams, SODA 2016].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • permanent
  • Hamiltonian cycle
  • orthogonal vectors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Ryan Williams, and Huacheng Yu. More Applications of the Polynomial Method to Algorithm Design. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pages 218-230, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. Google Scholar
  2. Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 51-58, New York, NY, USA, 2015. ACM. Google Scholar
  3. Bax and Franklin. A Permanent Algorithm with exp[Ω (N^1/3/2 ln N)] Expected Speedup for 0-1 Matrices. Algorithmica, 32(1):157-162, January 2002. Google Scholar
  4. Andreas Björklund. Determinant Sums for Undirected Hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. URL: http://dx.doi.org/10.1137/110839229.
  5. Andreas Björklund and Thore Husfeldt. The Parity of Directed Hamiltonian Cycles. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 727-735, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.83.
  6. Andreas Björklund, Thore Husfeldt, and Isak Lyckberg. Computing the permanent modulo a prime power. Inf. Process. Lett., 125:20-25, 2017. URL: http://dx.doi.org/10.1016/j.ipl.2017.04.015.
  7. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. CoRR, abs/1607.04002, 2016. URL: http://arxiv.org/abs/1607.04002.
  8. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 91:1-91:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.91.
  9. Andreas Björklund, Petteri Kaski, and Ryan Williams. Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica, September 2018. Google Scholar
  10. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. Inf. Comput., 243(C):86-111, August 2015. Google Scholar
  11. Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-smolensky. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1246-1255, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. Google Scholar
  12. Don Coppersmith. Rapid Multiplication of Rectangular Matrices. SIAM J. Comput., 11(3):467-471, 1982. URL: http://dx.doi.org/10.1137/0211037.
  13. Marek Cygan and Marcin Pilipczuk. Faster Exponential-time Algorithms in Graphs of Bounded Average Degree. Inf. Comput., 243(C):75-85, August 2015. Google Scholar
  14. Taisuke Izumi and Tadashi Wadayama. A New Direction for Counting Perfect Matchings. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS '12, pages 591-598, Washington, DC, USA, 2012. IEEE Computer Society. Google Scholar
  15. Kasper Green Larsen and Ryan Williams. Faster Online Matrix-vector Multiplication. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 2182-2189, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. Google Scholar
  16. Maciej Liśkiewicz, Mitsunori Ogihara, and Seinosuke Toda. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoretical Computer Science, 304(1):129-156, 2003. Google Scholar
  17. Prabhakar Raghavan. Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs. J. Comput. Syst. Sci., 37(2):130-143, October 1988. Google Scholar
  18. Herbert John Ryser. Combinatorial Mathematics. Mathematical Association of America, 1963. Google Scholar
  19. Rocco A. Servedio and Andrew Wan. Computing sparse permanents faster. Information Processing Letters, 96(3):89-92, 2005. Google Scholar
  20. W. T. Tutte. The dissection of equilateral triangles into equilateral triangles. Mathematical Proceedings of the Cambridge Philosophical Society, 44(4):463-482, 1948. Google Scholar
  21. Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8:410-421, 1979. Google Scholar
  22. L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact