Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
© Andreas Björklund and Ryan Williams; licensed under Creative Commons License CC-BY We show that the permanent of an n × n matrix over any finite ring of r ≤ n elements can be computed with a deterministic 2n−Ω(nr ) time algorithm. This improves on a Las Vegas algorithm running in expected 2n−Ω(n/(...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137488 |
| _version_ | 1826211679567872000 |
|---|---|
| author | Williams, Richard Ryan Björklund, Andreas |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Williams, Richard Ryan Björklund, Andreas |
| author_sort | Williams, Richard Ryan |
| collection | MIT |
| description | © Andreas Björklund and Ryan Williams; licensed under Creative Commons License CC-BY We show that the permanent of an n × n matrix over any finite ring of r ≤ n elements can be computed with a deterministic 2n−Ω(nr ) time algorithm. This improves on a Las Vegas algorithm running in expected 2n−Ω(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 2n−Ω(d3 n /4) time algorithm. This improves on a 2n−Ω(nd ) 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 δ can be computed by a deterministic 2n−Ω(nδ ) time algorithm. This improves on a Las Vegas algorithm running in expected 2n−Ω(poly(n δ)) 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]. |
| first_indexed | 2024-09-23T15:09:48Z |
| format | Article |
| id | mit-1721.1/137488 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:09:48Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1374882023-02-14T20:09:38Z Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors Williams, Richard Ryan Björklund, Andreas Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Andreas Björklund and Ryan Williams; licensed under Creative Commons License CC-BY We show that the permanent of an n × n matrix over any finite ring of r ≤ n elements can be computed with a deterministic 2n−Ω(nr ) time algorithm. This improves on a Las Vegas algorithm running in expected 2n−Ω(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 2n−Ω(d3 n /4) time algorithm. This improves on a 2n−Ω(nd ) 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 δ can be computed by a deterministic 2n−Ω(nδ ) time algorithm. This improves on a Las Vegas algorithm running in expected 2n−Ω(poly(n δ)) 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]. 2021-11-05T14:48:48Z 2021-11-05T14:48:48Z 2019 2021-03-25T11:50:36Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137488 Williams, Richard Ryan and Björklund, Andreas. 2019. "Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors." Leibniz International Proceedings in Informatics, LIPIcs, 132. en 10.4230/LIPIcs.ICALP.2019.25 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Williams, Richard Ryan Björklund, Andreas Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors |
| title | Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors |
| title_full | Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors |
| title_fullStr | Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors |
| title_full_unstemmed | Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors |
| title_short | Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors |
| title_sort | computing permanents and counting hamiltonian cycles by listing dissimilar vectors |
| url | https://hdl.handle.net/1721.1/137488 |
| work_keys_str_mv | AT williamsrichardryan computingpermanentsandcountinghamiltoniancyclesbylistingdissimilarvectors AT bjorklundandreas computingpermanentsandcountinghamiltoniancyclesbylistingdissimilarvectors |