Counting Perfect Matchings in Graphs of Degree 3

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.