Counting perfect matchings in graphs of degree 3

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Counting perfect matchings is an interesting and challenging combinatorial task. It has important applications in statistical physics. As the general problem is #P complete, it is usually tackled by randomized heuristics and approximation schemes. The trivial running times for exact algorithms are O*((n-1)!!)=O *(n!!)=O *((n/2)! 2 n/2) for general graphs and O *((n/2)!) for bipartite graphs. Ryser's old algorithm uses the inclusion exclusion principle to handle the bipartite case in time O*(2 n/2). It is still the fastest known algorithm handling arbitrary bipartite graphs. For graphs with n vertices and m edges, we present a very simple argument for an algorithm running in time O *(1.4656 m-n ). For graphs of average degree 3 this is O*(1.2106 n ), improving on the previously fastest algorithm of Björklund and Husfeldt. We also present an algorithm running in time O*(1.4205 m-n ) or O*(1.1918 n ) for average degree 3 graphs. The purpose of these simple algorithms is to exhibit the power of the m-n measure. Here, we don't investigate the further improvements possible for larger average degrees by applying the measure-and-conquer method.

Original languageEnglish (US)
Title of host publicationFun with Algorithms - 6th International Conference, FUN 2012, Proceedings
Number of pages9
StatePublished - 2012
Event6th International Conference on Fun with Algorithms, FUN 2012 - Venice, Italy
Duration: Jun 4 2012Jun 6 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Conference on Fun with Algorithms, FUN 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Counting perfect matchings in graphs of degree 3'. Together they form a unique fingerprint.

Cite this