Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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

Details

Authors
Organisations
External organisations
  • Massachusetts Institute of Technology
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Control Engineering

Keywords

  • Hamiltonian cycle, Orthogonal vectors, Permanent
Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming
Subtitle of host publicationICALP 2019
EditorsIoannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages25:1–25:14
Number of pages14
Volume132
ISBN (Electronic)9783959771092
Publication statusPublished - 2019 Jul
Publication categoryResearch
Peer-reviewedYes
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: 2019 Jul 92019 Jul 12

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period2019/07/092019/07/12