Meny

Javascript is not activated in your browser. This website needs javascript activated to work properly.
Du är här

Counting perfect matchings as fast as Ryser

Författare:
Publiceringsår: 2012
Språk: Engelska
Sidor: 914-921
Dokumenttyp: Konferensbidrag
Förlag: SIAM

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • Mathematics and Statistics

Övriga

ACM-SIAM Symposium on Discrete Algorithms
2012-01-17/2012-01-19
Kyoto, Japan
  • VR
Published
  • Exact algorithms
Yes
  • Algorithms

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen