Matchings are perfect

One of my favorite object in graph theory are Matchings, especially Perfect Matchings (PMs). Let me restate the definition of a PM briefly:

Definition (Perfect Matching)

Given a graph $\mathcal{G} = (E,V)$, then a Perfect Matching $M$ is a set of pair-wise non-adjacent edges from $E$, such that every vertex in $V$ is touched by one edge in $M$.

Here is a little example for a two PMs in a graph:

Figure 1 - Top: The original graph $\mathcal{G}$; Below: The red lines indicate two example perfect matchings in $\mathcal{G}$

This post list some of the properties of PMs regarding finding and counting them in different graphs types. During writing this posts, i found that a similar listing can also be red in [6].

1. Finding a Perfect Matching in a Graph $\mathcal{G}$

The task, given a graph $\mathcal{G}$, to find a PM can be solved in polynomial time (hence it is in $\mathsf{P}$) using the algorithm of Edmonds' [1]. Its complexity is $\mathcal{O}(\sqrt{V}E)$ and could not only be used to find a PM but also to find a maximal matching in general graphs.

2.1) Counting Perfect Matchings in a Graph $\mathcal{G}$

Albeit finding a single Perfect Matchings is efficiently solvable, counting all possible PMs is hard since it is #$\mathsf{P}$-$\mathsf{complete}$. For bipartite graphs this problem is equivalent to compute the permanent of a $0/1$-matrix as already covered in one of my previous blogposts. In that case (i.e. bipartite) there exists a fully polynomial time randomized approximation scheme (FPRAS) [2,3], which is actually an amazing result. The FPRAS, given a $n \times n$ matrix $M$, outputs an approximation $A$ for the permanent of $M$ such that:

\begin{equation} \text{Pr}[\text{exp}(-\epsilon)A \leq \text{perm}(M) \leq \text{exp}(\epsilon)A] \geq 3/4 \end{equation}

The probability of $3/4$ can be increased by repeating the algorithm. The algorithm runs in time polynomial in $n$ and $1/\epsilon$.

2.2) Counting Perfect Matchings in a Planar Graph $\mathcal{G}$

Whenever we can draw the graph on a paper $\mathcal{G}$ such that no lines cross each other, the problem to count PMs becomes easy. I.e., if $\mathcal{G}$ is planar, the algorithm of Fisher, Kasteleyn, and Temperley (FKT-algorithm) does the job in polynomial time. The algorithm finds a Pfaffian orientation in $\mathcal{G}$, which results in an $(-1,0,1)$ adjacency matrix $B$. The number of PMs is then equal to the square root of the determinant of $B$. Note that a graph is planar if and only if it does not contain the graphs $K_{3,3}$ or $K_5$ as a minor.

2.3) Counting Perfect Matchings in a $K_{3,3}$-free Graph $\mathcal{G}$

The result that PMs can be counted efficiently in planar graphs, i.e. in $K_{3,3}$ and $K_5$ free graphs, is well known. However, even in the case that the graph is not planar but only $K_{3,3}$-free, counting can be done in polynomial time, due to Vazirani [4]. Note that whenever $\mathcal{G}$ is not planar but $K_{3,3}$-free it must have $K_5$ as a minor. Vazirani used the result of Little [8], who shows how to find a Pfaffian orientation in a $K_{3,3}$-free graph given a $K_5$ minor, together with the result of Hall[13], that every triconnected component of a $K_{3,3}$-free graph $\mathcal{G}$ is either planar or exactly the $K_5$ graph.

2.4) Counting Perfect Matchings in a $K_5$-free Graph $\mathcal{G}$

The next result is that not only $K_{3,3}$-free graphs allow counting of PMs in polynomial time, but also $K_5$-free graphs. On contrast to the previous cases, this proof is only a few years old [7]. The same approach as in the $K_{3,3}$-free case does not work, since $K_5$-free graphs might not have a Pfaffian orientation. The authors used the result that the decomposition of a $K_5$-free graph in triconnected components yields either the Möbius ladder $M_8$ or the their 4-connected decomposition yields only planar components. The main obstacle is to put all partial results together to compute the right number of PMs.

2.5) Counting Perfect Matchings in a $\mathcal{H}$-free Graph $\mathcal{G}$ whereof $\mathcal{H}$ is single-crossing

This is a generalization of 2.3) and 2.4) and was published in [9]. Radu Curticapean shows that as long as the graph excludes a fixed minor that is single crossing, i.e., it can be drawn plane with only one crossing of two lines (e.g. $K_5$, $K_{3,3}$), one could find PMs in $\mathcal{O}(n^4)$.

2.5.1) Minor Testing

In this context an interesting question is, what is the complexity to test if a given graph $\mathcal{G}$ is $\mathcal{H}$-free or not. For arbitrary graphs $\mathcal{G}$ and $\mathcal{H}$ this problem is $\mathsf{NP}-\mathsf{complete}$. Just imaging, that you could pick $H$ such that it a circle graph with the same number of nodes as $\mathcal{G}$. Then the question if $\mathcal{G}$ has $\mathcal{H}$ as a minor is identical to test if $\mathcal{G}$ has a Hamiltonian cycle. But if you fix the graph $\mathcal{H}$, the problem becomes polynomial, because the exponential term, that came from $\mathcal{H}$ is now constant and even vanishes in the $\mathcal{O}$-notation (Problem conversation like this are called: fixed-parameter tractable).

2.6) Counting Perfect Matchings in Bounded Genus Graph $\mathcal{G}$

The genus $g$ of a graph $\mathcal{G}$ is the minimum integer $g$, such that the graph can be embedded without crossings on a surface of genus $g$. The genus of a surface is just the number of holes that it contains. Determining the genus of a graph is $\mathsf{NP}-\mathsf{Hard}$ whereof testing if a graph can be embedded into a genus $g$ is polynomial time solvable.

Figure 2 - Different surfaces with increasing genus. Left to right: 0,1,2,3.

A planar graph can be embedded on a surface of genus $0$. Figure 3 illustrates how the non planar graph $K_{3,3}$ can be embedded on a surface of genus $1$. The hole allows to escape from an inner face to the outside of the graph.

Figure 3 - On the left the graph $K_{3,3}$ is shown. It can not be embedded on a surface of genus 0, but if you increase the genus of the surface by drilling a hole in it, the line crossing can be removed by connecting the two vertices through that hole.

It was shown in [9,10,11] that the number of perfect matchings can be computed in $\mathcal{O}(4^gn^3)$ when the graph has a bounded genus.

Related Posts:

• A strange recursion - Sum of Divisors

• An explicit formula for Discrete Logarithms

• The Diffie-Hellman Oracle

• Backdooring Diffie-Hellman

[1] Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467
[2] Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, and Eric Vigoda, SIAM J. Comput., 37(5), 1429–1454. (26 pages), Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
[3] M.R. Jerrum, A. Sinclair and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the Association for Computing Machinery, 51(4):671-697, 2004
[4] Vijay V. Vazirani, NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems, Information and Computation, Volume 80, Issue 2, February 1989, Pages 152-164
[5] Radu Curticapean. Counting perfect matchings in graphs that exclude a single-crossing minor. CoRR, abs/1406.4056, 2014
[6] Radu Curticapean, Mingji Xia: Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. FOCS 2015: 994-1009
[7] Simon Straub, Thomas Thierauf and Fabian Wagner, Counting the Number of Perfect Matchings in K5-Free Graphs, Theory of Computing Systems, October 2016, Volume 59, Issue 3, pp 416–439
[8] C. H. C. Little. An extension of Kasteleyn's method of enumerating the l-factors of planar graphs. Combinatorial Mathematics, Proc. Second Australian Conference, Ed.: D. Holton, Lecture Notes in Math. 403, Springer-Verlag Berlin (1974), 63-72.
[9] Radu Curticapean, Counting perfect matchings in graphs that exclude a single-crossing minor. CoRR abs/1406.4056 (2014)
[10] Anna Galluccio and Martin Loebl. On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Electronic Journal of Combinatorics, 6, 1999
[11] Tullio Regge and Riccardo Zecchina. Combinatorial and topological approach to the 3d ising model, Journal of Physics A: Mathematical and General, 33(4):741–761, 2000.
[12] Glenn Tesler. Matchings in graphs on non-orientable surfaces. J. Comb. Theory, Ser. B, 78(2):198–231, 2000
[13] Hall, D.W., A note on primitive skew curves, Bull. Amer. Math. Sot. 49, 935-937