Counting perfect matchings as fast as Ryser
(2012) ACMSIAM Symposium on Discrete Algorithms In [Host publication title missing] p.914921 Abstract
 We show that there is a polynomial space algorithm that counts the number of perfect matchings in an nvertex 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 nvertex 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:
http://lup.lub.lu.se/record/2223231
 author
 Björklund, Andreas ^{LU}
 organization
 publishing date
 2012
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 [Host publication title missing]
 pages
 914  921
 publisher
 SIAM
 conference name
 ACMSIAM Symposium on Discrete Algorithms
 external identifiers

 Scopus:84860209831
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 c08e8405886842439a490bbc90cca5f9 (old id 2223231)
 alternative location
 http://siam.omnibooksonline.com/2012SODA/data/papers/009.pdf
 date added to LUP
 20111205 13:14:02
 date last changed
 20161013 04:50:57
@misc{c08e8405886842439a490bbc90cca5f9, abstract = {We show that there is a polynomial space algorithm that counts the number of perfect matchings in an nvertex 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 > 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.}, author = {Björklund, Andreas}, language = {eng}, pages = {914921}, publisher = {ARRAY(0x8209a10)}, series = {[Host publication title missing]}, title = {Counting perfect matchings as fast as Ryser}, year = {2012}, }