Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Counting perfect matchings as fast as Ryser

Björklund, Andreas LU (2012) ACM-SIAM Symposium on Discrete Algorithms p.914-921
Abstract
We show that there is a polynomial space algorithm that counts the number of perfect matchings in an n-vertex graph in O*(2n/2) ⊂ O(1.415n) time. (O*(f(n)) suppresses functions polylogarithmic in f(n)). The previously fastest algorithms for the problem was the exponential space O*(((1 + √5)/2)n) ⊂ O(1.619n) time algorithm by Koivisto, and for polynomial space, the O(1.942n) time algorithm by Nederlof. Our new algorithm's runtime matches up to polynomial factors that of Ryser's 1963 algorithm for bipartite graphs. We present our algorithm in the more general setting of computing the hafnian over an arbitrary ring, analogously to Ryser's algorithm for permanent computation.



We also give a simple argument why the general... (More)
We show that there is a polynomial space algorithm that counts the number of perfect matchings in an n-vertex graph in O*(2n/2) ⊂ O(1.415n) time. (O*(f(n)) suppresses functions polylogarithmic in f(n)). The previously fastest algorithms for the problem was the exponential space O*(((1 + √5)/2)n) ⊂ O(1.619n) time algorithm by Koivisto, and for polynomial space, the O(1.942n) time algorithm by Nederlof. Our new algorithm's runtime matches up to polynomial factors that of Ryser's 1963 algorithm for bipartite graphs. We present our algorithm in the more general setting of computing the hafnian over an arbitrary ring, analogously to Ryser's algorithm for permanent computation.



We also give a simple argument why the general exact set cover counting problem over a slightly superpolynomial sized family of subsets of an n element ground set cannot be solved in O*(2(1−ε1)n) time for any ε1 > 0 unless there are O*(2(1−ε2)n) time algorithms for computing an n x n 0/1 matrix permanent, for some ε2 > 0 depending only on ε1. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
[Host publication title missing]
pages
914 - 921
publisher
Society for Industrial and Applied Mathematics
conference name
ACM-SIAM Symposium on Discrete Algorithms
conference location
Kyoto, Japan
conference dates
2012-01-17 - 2012-01-19
external identifiers
  • scopus:84860209831
project
Exact algorithms
language
English
LU publication?
yes
id
c08e8405-8868-4243-9a49-0bbc90cca5f9 (old id 2223231)
alternative location
http://siam.omnibooksonline.com/2012SODA/data/papers/009.pdf
date added to LUP
2016-04-04 12:20:07
date last changed
2022-04-24 02:01:01
@inproceedings{c08e8405-8868-4243-9a49-0bbc90cca5f9,
  abstract     = {{We show that there is a polynomial space algorithm that counts the number of perfect matchings in an n-vertex graph in O*(2n/2) ⊂ O(1.415n) time. (O*(f(n)) suppresses functions polylogarithmic in f(n)). The previously fastest algorithms for the problem was the exponential space O*(((1 + √5)/2)n) ⊂ O(1.619n) time algorithm by Koivisto, and for polynomial space, the O(1.942n) time algorithm by Nederlof. Our new algorithm's runtime matches up to polynomial factors that of Ryser's 1963 algorithm for bipartite graphs. We present our algorithm in the more general setting of computing the hafnian over an arbitrary ring, analogously to Ryser's algorithm for permanent computation.<br/><br>
<br/><br>
We also give a simple argument why the general exact set cover counting problem over a slightly superpolynomial sized family of subsets of an n element ground set cannot be solved in O*(2(1−ε1)n) time for any ε1 &gt; 0 unless there are O*(2(1−ε2)n) time algorithms for computing an n x n 0/1 matrix permanent, for some ε2 &gt; 0 depending only on ε1.}},
  author       = {{Björklund, Andreas}},
  booktitle    = {{[Host publication title missing]}},
  language     = {{eng}},
  pages        = {{914--921}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  title        = {{Counting perfect matchings as fast as Ryser}},
  url          = {{http://siam.omnibooksonline.com/2012SODA/data/papers/009.pdf}},
  year         = {{2012}},
}