Björklund, Andreas ;
Williams, Ryan
Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors
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^{nOmega(n/r)} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{nOmega(n/(r log r))} time, implicit in [Björklund, Husfeldt, and Lyckberg, IPL 2017]. For the permanent over the integers of a 0/1matrix with exactly d ones per row and column, we provide a deterministic 2^{nOmega(n/(d^{3/4)})} time algorithm. This improves on a 2^{nOmega(n/d)} time algorithm in [Cygan and Pilipczuk ICALP 2013]. We also show that the number of Hamiltonian cycles in an nvertex directed graph of average degree delta can be computed by a deterministic 2^{nOmega(n/(delta))} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{nOmega(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].
BibTeX  Entry
@InProceedings{bjrklund_et_al:LIPIcs:2019:10601,
author = {Andreas Bj{\"o}rklund and Ryan Williams},
title = {{Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {25:125:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10601},
URN = {urn:nbn:de:0030drops106018},
doi = {10.4230/LIPIcs.ICALP.2019.25},
annote = {Keywords: permanent, Hamiltonian cycle, orthogonal vectors}
}
2019
Keywords: 

permanent, Hamiltonian cycle, orthogonal vectors 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 