research-article

Counting perfect matchings as fast as Ryser

Author:

Andreas BjörklundAuthors Info & Claims

SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Pages 914 - 921

Published: 17 January 2012 Publication History

Abstract

We show that there is a polynomial space algorithm that counts the number of perfect matchings in an n-vertex graph in O*(2^n/2) ⊂ O(1.415ⁿ) 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)ⁿ) ⊂ O(1.619ⁿ) time algorithm by Koivisto, and for polynomial space, the O(1.942ⁿ) 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−ε₁)n) time for any ε₁ > 0 unless there are O*(2^(1−ε₂)n) time algorithms for computing an n x n 0/1 matrix permanent, for some ε₂ > 0 depending only on ε₁.

References

[1]

O. Amini, F. V. Fomin, and S. Saurabh. Counting Subgraphs via Homomorphisms. In proceedings of the 36th ICALP, pp. 71--82, 2009.

Digital Library

[2]

E. Bax and J. Franklin. A Permanent Algorithm with exp{(n ^1/3/2ln(n))} Expected Speedup for 0--1 Matrices. Algorithmica, Volume 32, Number 1, 157--162, 2002.

[3]

A. Björklund and T. Husfeldt. Exact algorithms for Exact Satisfiability and Number of Perfect Matchings. Algorithmica 52, pp. 226--249, 2008.

Digital Library

[4]

A. Björklund, T. Husfeldt, and M. Koivisto. Set partitioning via inclusion--exclusion. SIAM Journal on Computing, Volume 39, Issue 2, pp. 546--563, 2009.

Digital Library

[5]

A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets Möbius: Fast Subset Convolution. In proceedings of the 39th ACM symposium on theory of computing (STOC), pp. 67--74, 2007.

Digital Library

[6]

H. Dell, T. Husfeldt, and M. Wahlen. Exponential Time Compexity od the permanent and the Tutte polynomial. In proceedings of the 37th ICALP, pp. 426--437, 2010.

Digital Library

[7]

R. Impagliazzo, R. Paturi, F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512--530, 2001.

Digital Library

[8]

M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM 5, pp. 671--697, 2004.

Digital Library

[9]

R. M. Karp. Dynamic programming meets the principle of inclusion and exclusion, Oper. Res. Lett. 1, no. 2, pp. 49--51, 1982.

[10]

M. Koivisto. Partitioning into sets of bounded cardinality. 4th International Workshop on Parameterized and Exact Computation (IWPEC), LNCS 5917, pp. 258--263, Springer, 2009.

Digital Library

[11]

D. Lokshtanov and J. Nederlof. Saving space by algebraization. In proceedings of the 42nd ACM symposium on theory of computing (STOC), pp. 321--330, 2010.

Digital Library

[12]

J. Nederlof. Inclusion exclusion for hard problems. Masters thesis, Utrecht University, August 2008.

[13]

J. Nederlof. Fast polynomial-space algorithms using Mobius inversion: Improving on Steiner Tree and related problems. Submitted, available at http://folk.uib.no/jne061/Steinerfull.pdf, 2010.

[14]

H. J. Ryser. Combinatorial Mathematics, The Carus mathematical monographs, The Mathematical Association of America, 1963.

[15]

P. Sankowski. Alternative algorithms for counting all matchings in a graph. In proceedings of the 20th STACS, pp. 427--438, 2003.

Digital Library

[16]

R. A. Servedio and A. Wan. Computing sparse permanents faster. Information Processing Letters, Volume 96 Issue 3, 15 November 2005.

Digital Library

[17]

L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci. 8, pp. 189--201, 1979.

[18]

F. Yates, The Design and Analysis of Factorial Experiments, Technical Communication No. 35, Commonwealth Bureau of Soil Science, Harpenden, UK, 1937.

Cited By

Björklund AGupt BQuesada N(2019)A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a SupercomputerACM Journal of Experimental Algorithmics10.1145/332511124(1-17)Online publication date: 11-Jun-2019
https://dl.acm.org/doi/10.1145/3325111
Perepechko S(2019)Counting Near-Perfect Matchings on Cm × Cn Tori of Odd Order in the Maple SystemProgramming and Computing Software10.1134/S036176881902007545:2(65-72)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1134/S0361768819020075
Brand CDell HRoth M(2019)Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSPAlgorithmica10.1007/s00453-018-0472-z81:2(541-556)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0472-z
Show More Cited By

Index Terms

Counting perfect matchings as fast as Ryser
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
      2. Enumeration
  2. Mathematical analysis
    1. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms

By now, we have a good understanding of how NP-hard problems become easier on graphs of bounded treewidth and bounded cliquewidth: for various problems, matching upper bounds and conditional lower bounds describe exactly how the running time has to ...
Perfect Matchings in Total Domination Critical Graphs

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination ...
A pair of forbidden subgraphs and perfect matchings

In this paper, we study the relationship between forbidden subgraphs and the existence of a matching. Let H be a set of connected graphs, each of which has three or more vertices. A graph G is said to be H-free if no graph in H is an induced subgraph of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

January 2012

1764 pages

Sponsors

Kyoto University: Kyoto University

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 17 January 2012

Check for updates

Qualifiers

Research-article

Conference

SODA '12

Sponsor:

Kyoto University

SODA '12: ACM-SIAM Symposium on Discrete Algorithms

January 17 - 19, 2012

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)3

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Björklund AGupt BQuesada N(2019)A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a SupercomputerACM Journal of Experimental Algorithmics10.1145/332511124(1-17)Online publication date: 11-Jun-2019
https://dl.acm.org/doi/10.1145/3325111
Perepechko S(2019)Counting Near-Perfect Matchings on Cm × Cn Tori of Odd Order in the Maple SystemProgramming and Computing Software10.1134/S036176881902007545:2(65-72)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1134/S0361768819020075
Brand CDell HRoth M(2019)Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSPAlgorithmica10.1007/s00453-018-0472-z81:2(541-556)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0472-z
Hirai HNamba H(2018)Shortest $$(A+B)$$(A+B)-Path Packing Via HafnianAlgorithmica10.1007/s00453-017-0334-080:8(2478-2491)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s00453-017-0334-0
Fürer MYu H(2017)Space Saving by Dynamic Algebraization Based on Tree-DepthTheory of Computing Systems10.1007/s00224-017-9751-361:2(283-304)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00224-017-9751-3
Golovnev AKulikov AMihajlin I(2016)Families with InfantsACM Transactions on Algorithms10.1145/284741912:3(1-17)Online publication date: 25-Apr-2016
https://dl.acm.org/doi/10.1145/2847419
Fürer M(2012)Counting perfect matchings in graphs of degree 3Proceedings of the 6th international conference on Fun with Algorithms10.1007/978-3-642-30347-0_20(189-197)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30347-0_20

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents