Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

Björklund, Andreas LU and Williams, Ryan (2019) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 In Leibniz International Proceedings in Informatics (LIPIcs) 132. p.1-25
Abstract

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... (More)

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].

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Hamiltonian cycle, Orthogonal vectors, Permanent
host publication
46th International Colloquium on Automata, Languages, and Programming : ICALP 2019 - ICALP 2019
series title
Leibniz International Proceedings in Informatics (LIPIcs)
editor
Chatzigiannakis, Ioannis ; Baier, Christel ; Leonardi, Stefano and Flocchini, Paola
volume
132
article number
25
pages
14 pages
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
conference location
Patras, Greece
conference dates
2019-07-09 - 2019-07-12
external identifiers
  • scopus:85069147718
ISSN
1868-8969
ISBN
9783959771092
DOI
10.4230/LIPIcs.ICALP.2019.25
language
English
LU publication?
yes
id
63c162ea-fee8-48c4-af92-ddeea8373c02
date added to LUP
2019-07-26 11:36:58
date last changed
2022-04-10 20:10:18
@inproceedings{63c162ea-fee8-48c4-af92-ddeea8373c02,
  abstract     = {{<p>We show that the permanent of an n × n matrix over any finite ring of r ≤ n elements can be computed with a deterministic 2<sup>n</sup>−<sup>Ω(nr )</sup> time algorithm. This improves on a Las Vegas algorithm running in expected 2<sup>n</sup>−Ω(n/(r log r<sup>))</sup> 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<sup>n</sup>−<sup>Ω(</sup>d<sup>3 n /4)</sup> time algorithm. This improves on a 2<sup>n</sup>−<sup>Ω(nd )</sup> 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 2<sup>n</sup>−<sup>Ω(nδ )</sup> time algorithm. This improves on a Las Vegas algorithm running in expected 2<sup>n</sup>−<sup>Ω(poly(n δ))</sup> 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].</p>}},
  author       = {{Björklund, Andreas and Williams, Ryan}},
  booktitle    = {{46th International Colloquium on Automata, Languages, and Programming : ICALP 2019}},
  editor       = {{Chatzigiannakis, Ioannis and Baier, Christel and Leonardi, Stefano and Flocchini, Paola}},
  isbn         = {{9783959771092}},
  issn         = {{1868-8969}},
  keywords     = {{Hamiltonian cycle; Orthogonal vectors; Permanent}},
  language     = {{eng}},
  pages        = {{1--25}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics (LIPIcs)}},
  title        = {{Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.25}},
  doi          = {{10.4230/LIPIcs.ICALP.2019.25}},
  volume       = {{132}},
  year         = {{2019}},
}