Counting perfect matchings in grids and planar graphs

Planar graphs are an interesting class of graphs, since many of problems which are complicated, hard or intractable on general graphs, have elegant and computable solutions on planar graphs. In this article we will look at one of such problems, namely calculating the number of perfect matchings in a graph.

This article is expanded version of my two-part series which was printed (in Polish) in a popular science magazine Delta published by University of Warsaw.

Counting perfect matchings is hard

Recall that a matching in a graph is a subset of edges in which every vertex is adjacent to at most one edge from the subset. A perfect matching (also called 1-factor) is a matching in which every node is matched, thus its size is exactly number of vertices divided by two. We know polynomial-time algorithms to find perfect matchings in graphs. They are somewhat easier for bipartite graphs (like Hopcroft–Karp algorithm), but still doable for general graphs (like Edmonds's blossom algorithm). What about the problem of counting perfect matchings?

Let's try some simple examples. First of all, the graph has to have an even number of vertices. For instance it is very easy to see that a line graph (a path) of even length has exactly one perfect matching, and each cycle graph of even length has exactly two. It is also easy for trees: each leaf must be in matching with its only neighbour, so we can prove inductively, that each tree has at most one perfect matching. Testing whether this matching indeed exists can be done with a simple greedy algorithm.

Since finding matchings is easier for bipartite graphs, let's generalize above examples by investigating this case. If we want to have at least one perfect matching in a bipartite graph, it is necessary that both sides of this graph have the same number of vertices – denote it by $N$.

Such graph can be described as a zero-one biadjacency matrix $A = (a_{i,j})$ of size $N \times N$, in which $a_{i,j}=1$ if and only if there is an edge which connects the $i$-th vertex from the left side with the $j$-th vertex from the right side.

Hover to show permutation $\pi = \big({1 \atop 3}\ {2 \atop 1}\ {3 \atop 2} \big)$

A perfect matching in such a graph can be described with a permutation $\pi$ of set $\{1,\ldots,N\}$ which for the $i$-th vertex from the left side assigns the $\pi(i)$-th vertex from the right side. These vertices are connected by an edge only if $a_{i,\pi(i)} = 1$, thus the assignment corresponds to a perfect matching if the product $a_{1,\pi(1)} a_{2,\pi(2)} \cdots a_{N,\pi(N)}$ is equal to one. Therefore the number of perfect matchings is the value called a permanent of matrix $A$, which sums these products over all permutations $\pi$:

$\mathrm{perm}(A) = \sum_{\pi} a_{1,\pi(1)} a_{2,\pi(2)} \cdots a_{N,\pi(N)}$

However, calculating permanent directly from this definition needs time $O(n! \cdot n)$. It can be speeded-up using inclusion-exclusion principle and dynamic programming over subsets, to gain faster $O(2^n n)$ time, but still exponential. Unfortunately, this is the best we know so far, and since calculating the permanent of a matrix is #P-complete (as stated by Valiant theorem) it is not likely that we will every get a polynomial algorithm. Therefore finding the numbers of perfect matchings is #P-complete even for bipartite graphs.

Surprisingly though, finding the parity of the number of perfect matchings in a bipartite graph is doable in polynomial time. This is because the formula for the permanent is very similar to the permutational definition of a determinant of matrix:

$\mathrm{det}(A) = \sum_{\pi} \mathrm{sgn}(\pi) \cdot a_{1,\pi(1)} a_{2,\pi(2)} \cdots a_{N,\pi(N)}$

The difference is only in value $\mathrm{sgn}(\pi)$ which is called the sign of the permutation, and for now we only need to know that it is equal either $1$ or $-1$. But if we want to calculate the parity, we must take the whole formula modulo $2$, and since $1 \equiv -1 \pmod 2$, then the permutation sign vanishes. Thus the parity of the determinant is the same as the parity of the permanent. And we know that the determinant can be calculated in polynomial time (for instance in $O(N^3)$ using Gaussian elimination).

Counting perfect matchings in grids

But maybe we can find some other simple (but not trivial) class of graphs, for which calculating the number of perfect matchings will be doable in polynomial time? We can, and in this section we will show that grid graphs are such a class.

Formally a grid graph of size $m \times n$ is a Cartesian product of two paths of $m$ and $n$ vertices, but it just means that we can draw it on a plane in such a way that vertices are arranged in a grid of $m$ rows and $n$ columns and each vertex has at most four edges going to the closest neighbours in four cardinal directions.

The problem of finding perfect matchings in such a graph has a nice physical interpretation. A grid graph of size $m \times n$ can be a model of a checkerboard of the same size, and we need to cover this checkerboard using $N = mn/2$ domino pieces, where each piece can cover two adjacent fields of the checkerboard. (It turns out that this model has some important significance in physics, but I do not know what exactly.)

The checkerboard interpretation is a particularly nice one, because it shows that grid graphs are in fact bipartite. Indeed, every vertex which corresponds to a white field on the checkerboard is adjacent only to vertices which corresponds to black fields, thus sets of such “white” and “black” vertices are bi-partition of the grid graph. Therefore we can use methods described above, and represent it as a biadjacency matrix. The number of perfect matchings will be calculated by the permanent.

We assume that the number of columns $n$ is even (at least one of numbers $n$ or $m$ must be even), and we number the vertices row by row, as shown in the following picture with the grid of size $3 \times 4$ and two sample perfect matchings on that grid:

Hover to show permutation $\pi_1 = \big({1 \atop 3}\ {2 \atop 2}\ {3 \atop 1}\ {4 \atop 6}\ {5 \atop 5}\ {6 \atop 4} \big)$
or permutation $\pi_2 = \big({1 \atop 3}\ {2 \atop 1}\ {3 \atop 4}\ {4 \atop 2}\ {5 \atop 5}\ {6 \atop 6} \big)$

We will try once again to get some help from the determinant. Therefore we need to take a closer look at what exactly is the sign of a permutation. To define it we would need a notion of a cycle of permutation. A cycle of length $s$ is a sequence of indices $(i_1\ i_2\ \ldots\ i_s)$ such that $\pi(i_1) = i_2, \pi(i_2) = i_3, \ldots, \pi(i_s) = i_1$. Each permutation can be described as a set of disjoint cycles. Permutation $\pi$ is even, and its sign is equal to $\mathrm{sgn}(\pi)=1$, if in its partition cycle there is even number of cycles of even length. Otherwise the permutation is odd, and its sign is $\mathrm{sgn}(\pi)=-1$.

If in the graph we highlight edges of perfect matching corresponding to a permutation $\pi$, as well as all edges connecting vertices of different colors, but the same numbers, then every vertex will be adjacent to exactly two edges from the highlighted set, thus this set will be a cycle cover of the graph (i.e. such a set of disjoint cycles that each vertex lies on exactly one cycle). But we allow that some edges will be highlighted twice, which corresponds to trivial cycles. It should not be surprising that every cycle of length $s$ from permutation $\pi$ determines some cycle of length $2s$ in the cycle cover.

Now we are ready to show a brilliant idea which will allow us to use algorithm for calculating a determinant to calculate permanent of matrix $A$. The idea is to modify non-zero elements of matrix $A$ in such a way that for every permutation $\pi$ which corresponds to a perfect matching the product $\prod a_{i,\pi(i)}$ is equal to $1$, if the permutation is even, and $-1$ if it is odd. It turns out that we can obtain this goal by replacing ones in cells of matrix $A$ which correspond to vertical edges of the grid by a complex number $i = \sqrt{-1}$. Let's denote the matrix after this modification by $A'$. The picture below shows this for the $3 \times 4$ grid (the value $i$ was replaced by asterisks for better readability):

Hover to show permutation $\pi_1 = \big({1 \atop 3}\ {2 \atop 2}\ {3 \atop 1}\ {4 \atop 6}\ {5 \atop 5}\ {6 \atop 4} \big)$ with cycles $(1\ 3)\ (2)\ (4\ 6)\ (5)$ and even sign $\mathrm{sgn}(\pi_1) = 1$
or permutation $\pi_2 = \big({1 \atop 3}\ {2 \atop 1}\ {3 \atop 4}\ {4 \atop 2}\ {5 \atop 5}\ {6 \atop 6} \big)$ with cycles $(1\ 3\ 4\ 2)\ (5)\ (6)$ and odd sign $\mathrm{sgn}(\pi_2) = -1$

Let's fix one cycle of a permutation $\pi$ corresponding to some perfect matching and let's see what contribution bring the edges of the cycle to the product $\prod a'_{i,\pi(i)}$. We have three types of edges in the graph: horizontal edges from the matching (we denote their number in the cycle by $e_H$), horizontal edges joining vertices of the same numbers (not in the matching; we denote their number by $e_B$), and vertical edges (always from the matching; we denote their number by $e_V$). In the product we only iterate over edges from the matching, horizontal edges have weight $1$, and vertical edges have weight $i$, thus the contribution from the cycle is $1^{e_H} \cdot i^{e_V} = (-1)^{e_V/2}$. Note that if the cycle has length $1$, then it corresponds to one horizontal edge, and the contribution is equal to $1$. From now on we assume that the cycle is not trivial.

In order to go along the cycle in the graph and return to the origin, the number of vertical edges we will pass going downwards must be equal to the number of edges we go upwards. Therefore $e_V$ is an even number. Symmetrical reasoning shows that $e_H + e_B$ is even. Moreover, due to arrangement of edges which are not in the matching, every pass between two consecutive edges either changes the number of column by $2$ (when we go between edges $e_B$ and $e_H$) or changes the parity of the column, but only within a pair of columns, i.e $j = (j \bmod 2) + 1$ (when we go between edges $e_B$ and $e_V$). Thus there is an even number of both types of passes and both numbers $e_H$ and $e_V$ are even. In consequence number $e_B$ is even, thus in the cycle cover all non-trivial cycles correspond to even cycles in the permutation.

By examining the directions in which we pass the cycle along horizontal lines, we conclude that in rows of the same parity we will travel in the same direction. Moreover, the first and the last row of the cycle must be traversed in different directions, which shows that number $e_V/2$ is odd.

That means that the contribution from each even cycle in the permutation is equal to $(-1)^{e_V/2} = -1$. Therefore the product $\prod a'_{i,\pi(i)}$ will be equal to $1$ if and only if the number of such cycles will be even, thus it will be equal to the sign of the permutation. That shows equality $\mathrm{perm}(A) = \mathrm{det}(A')$.

Therefore the number of perfect matchings in the grid is determinant of matrix $A'$. What is the time complexity of such algorithm? The size of matrix $A'$ is $N \times N$, thus the standard Gaussian elimination will run in time $O(N^3)$. For simplicity assume that $n=m$, then $N=O(n^2)$, thus the total runtime is $O(n^6)$ operations on complex numbers of magnitude $O(2^n)$. Thus if we want to calculate the number of perfect matchings modulo some integer $M$ which fits in int, then the time complexity is $O(n^6)$.

To be continued…