Graph matching

Introduction

A matching, or independent edge set, is a set of edges in a graph that have no common endpoints. Graph matching algorithms are commonly used in informatics competitions and can be broadly divided into maximum matching and maximum-weight matching. Because matching in a bipartite graph is equivalent to a network-flow problem and has well-behaved properties, making it relatively easy to handle, this article first introduces the two types of algorithms for bipartite graphs and then discusses algorithms for general graphs.

Graph matching

Let $G=(V,E)$ be an undirected graph, where $V$ is the vertex set and $E$ is the edge set. If a set of edges $M\subseteq E$ contains no self-loops and no two of its edges share a vertex, then the edge set $M$ is called a matching (or independent edge set) of graph $G$. An edge $e\in E$ is called a matched edge if it appears in matching $M$, and an unmatched edge otherwise. Correspondingly, a vertex $v\in V$ is called a matched vertex if it is an endpoint of a matched edge, and an unmatched vertex otherwise.

The size of matching $M$ is the number of edges it contains. For matchings in (weighted) undirected graphs, the following concepts are often considered:

• Maximal matching: a matching to which no more matched edges can be added. A maximal matching is not necessarily a maximum matching.

  

• Maximum matching (or maximum cardinality matching): a matching with the largest number of matched edges. There may be more than one maximum matching, but the number of edges in a maximum matching is fixed, and it cannot exceed half the number of vertices in the graph.

  

• Maximum-weight matching: a matching in a weighted graph whose sum of edge weights is largest.

  

• Maximum-weight maximum-cardinality matching: among matchings with the largest possible cardinality, one whose sum of edge weights is largest; that is, the maximum-weight matching among all maximum matchings.

  

• Perfect matching: a matching in which every vertex is matched. A perfect matching is necessarily a maximum matching. A complete graph with an even number of vertices necessarily has a perfect matching.

• Near-perfect matching: a matching with exactly one unmatched vertex. This can happen only when the graph has an odd number of vertices. A near-perfect matching is also necessarily a maximum matching. A complete graph with an odd number of vertices necessarily has a near-perfect matching.

The graph matching problems encountered in algorithmic competitions mainly refer to maximum matching and maximum-weight matching.

Augmenting paths

In graph matching algorithms, an augmenting path is the core structure used to improve a matching.

Definition

For a graph $G=(V,E)$ and one of its matchings $M$, the following two types of (simple) paths can be defined:

• An alternating path is a path made up of matching edges and non-matching edges in alternation;
• An augmenting path is an alternating path that starts at an unmatched vertex and ends at an unmatched vertex.

Because an augmenting path contains $1$ more non-matching edge than matching edge, the number of its edges is necessarily odd. If the matching and non-matching edges on an augmenting path are swapped, it remains an alternating path, and the number of matched edges increases by $1$. The process of finding an augmenting path and swapping its edges to increase the size of a matching is called augmentation. In mathematical terms, augmentation takes the symmetric difference of matching $M$ and augmenting path $P$, yielding a new matching $M\oplus P$.

The figure below shows how one augmentation increases the number of matched edges from $2$ to $3$.

Berge's lemma

Berge's lemma states that improving a matching by using augmenting paths is sufficient. In other words, when no augmenting path can be found, the matching obtained is maximum.

Berge's lemma

For a graph $G=(V,E)$ and one of its matchings $M$, matching $M$ is a maximum matching if and only if there is no augmenting path with respect to matching $M$.

Proof

As explained above, if an augmenting path $P$ exists, then matching $M\oplus P$ is a larger matching than $M$, so $M$ cannot be a maximum matching.

Conversely, we need to show that if there is a matching larger than matching $M$, denoted by $M'$, then, with respect to $M$, there must be an augmenting path $P$. Consider the symmetric difference $M\oplus M'$. Every vertex in graph $(V,M\oplus M')$ has degree $0$, $1$, or $2$; therefore, every connected component of this graph must be a path, a cycle, or an isolated vertex. Moreover, the two edges incident to a vertex of degree $2$ must come from different matchings, so each such cycle contains the same number of edges from $M$ and $M'$. Since $M'$ is larger than $M$, at least one path contains more edges from $M'$ than from $M$; call this path $P$. The two endpoints of $P$ are unmatched vertices of $M$, and $P$ is an alternating path with respect to $M$, so $P$ must be an augmenting path with respect to $M$. This completes the proof.

This theorem gives the central idea for finding a maximum matching:

• Enumerate all unmatched vertices and find augmenting paths until no augmenting path can be found.

In fact, after each augmentation, it is unnecessary to traverse all unmatched vertices again. During the entire process of finding a maximum matching, each vertex needs to be traversed only once.

Proof

It suffices to show that if, when the enumeration reaches vertex $v$, there is no augmenting path starting at $v$, then after any number of augmentations there is still no augmenting path starting at $v$. This shows that even though augmentation changes the matching, previously enumerated unmatched vertices need not be checked again.

Suppose otherwise. That is, suppose $v$ is an unmatched vertex that has already been enumerated, and after augmenting along an augmenting path from $u$ to $w$, denoted by $P$ in some round, a new augmenting path starting at $v$, denoted by $P'$ appears. Then $P'$ must share an edge with $P$; otherwise, augmenting along $P$ would not change the matching status of any edge in $P'$, so $P'$ could not have appeared as a result of this augmentation.

(In the figure, black denotes non-matching edges, while red and blue denote different matching states.)

Let $x$ be the first vertex reached from $v$ along $P'$, and let it be a vertex on $P$. Since an alternating path from $v$ to $x$ already existed before this augmentation, $x$ must have been a matched vertex, so it cannot be either $u$ or $w$. Therefore, on augmenting path $P$, the two edges adjacent to $x$ have opposite matching states. This means that regardless of the matching state of the edge, an alternating path from $v$ to $x$ can be extended along $P$ to one of $u$ and $w$. Thus, an augmenting path starting at $v$ already existed before the augmentation, contradicting the assumption.

Alternating trees

Another concept closely related to augmenting paths is the alternating tree. It is a tree produced while performing DFS or BFS from an unmatched vertex $r$ to search for an augmenting path.

For a graph $G=(V,E)$ and one of its matchings $M$, if a subgraph $H\subseteq G$ is a tree rooted at an unmatched vertex $r$, and the path connecting $r$ to any $v\in H$ is an alternating path, then $H$ is called an alternating tree. A vertex at even depth in the tree is called an even vertex, and a vertex at odd depth is called an odd vertex.

The figure below shows an alternating tree that may be obtained by starting BFS from unmatched vertex $1$. (In the figure, red edges are matching edges and black edges are non-matching edges; dark vertices are matched vertices and light vertices are unmatched vertices.)

Existence of perfect matchings

In graph matching theory, there are two important existence theorems that can be used to determine whether a perfect matching exists in a bipartite graph or a general graph.

Hall's theorem

Suppose $G=(X,Y,E)$ is a bipartite graph and $|X|\le |Y|$. For graph $G$, let $M$ be a matching; if every vertex in $X$ is matched, then $M$ is called an $X$-perfect matching, sometimes simply a perfect matching (of bipartite graph $G$). This is the largest matching that can be achieved in a bipartite graph. Hall's theorem gives a necessary and sufficient condition for such a matching to exist.

Hall's theorem says that for every subset of $X$, there are enough vertices in $Y$ to match it, and therefore an $X$-perfect matching exists.

Hall's theorem

Suppose $G=(X,Y,E)$ is a bipartite graph and $|X|\le |Y|$. For any $W\subseteq X$, let $N_G(W)$ be the set of all vertices in graph $G$ adjacent to vertices in $W$. Then an $X$-perfect matching exists if and only if $|W|\le |N_G(W)|$ holds for every $W\subseteq X$.

Proof

The condition is clearly necessary. Suppose an $X$-perfect matching $M$ exists. Every vertex in $X$ is matched to a different vertex in $Y$. The set $N_G(W)$ contains at least the vertices matched to vertices in $W$, so its size is at least $|W|$.

The condition is also sufficient. Suppose no $X$-perfect matching exists. Then there must be a maximum matching $M$ in which a vertex $v\in X$ remains unmatched. Let $Z$ be the set of all vertices reachable from $v$ by alternating paths, and let $S=Z\cap X$ and $T=Z\cap Y$. Every vertex in $S\setminus\{v\}$ must be matched; otherwise, an odd cycle would arise, contradicting the fact that $G$ is bipartite. Every vertex in $T$ must also be matched; otherwise, there would be an augmenting path, which by Berge's lemma would contradict the maximality of $M$. Since all these vertices are matched, and matching can occur only between $X$ and $Y$, the vertices in $S\setminus\{v\}$ correspond one-to-one to the vertices in $T$, so $|T|=|S|-1$. At the same time, every vertex in $T$ is matched to a vertex in $S$, so at least $T\subseteq N_G(S)$. But $N_G(S)$ contains no unmatched vertex $u$: if it were adjacent to a vertex in $S$, namely $v'$, the alternating path reaching $v'$ could necessarily be extended to an alternating path reaching $u$. Thus $T=N_G(S)$. These arguments show that $|N_G(S)|<|S|$, contradicting the condition of Hall's theorem. Therefore an $X$-perfect matching exists.

Corollary

Every regular bipartite graph has a perfect matching.

Proof

In a regular bipartite graph, all vertices have the same degree, say $k$. First verify that Hall's condition holds: for every $W\subseteq X$, we have $|N_G(W)|\ge |W|$. The number of edges incident to vertices in $W$ is $k|W|$, while each vertex in $N_G(W)$ can be incident to at most $k$ of these edges, so necessarily $k|W|\le k|N_G(W)|$, that is, $|W|\le |N_G(W)|$. In particular, $|X|\le |Y|$; since $X$ and $Y$ are symmetric, $|X|=|Y|$. Therefore, in a regular bipartite graph, an $X$-perfect matching is also a perfect matching. Since Hall's theorem guarantees the existence of an $X$-perfect matching, a perfect matching must exist as well.

Tutte's theorem

Tutte's theorem gives a necessary and sufficient condition for the existence of a perfect matching in a general graph. This condition follows from a direct observation: a graph with an odd number of vertices cannot have a perfect matching.

Tutte's theorem

A graph $G=(V,E)$ has a perfect matching if and only if for every $U\subseteq V$, $\operatorname{odd}(G-U)\le |U|$, where $G-U$ is the subgraph obtained by deleting from graph $G$ the vertices in $U$ and the edges incident to them, and $\operatorname{odd}(G-U)$ is the number of connected components of subgraph $G-U$ that have an odd number of vertices.

Proof

It suffices to consider simple graphs, because multiple edges and self-loops do not affect Tutte's condition or the existence of a perfect matching.

The necessity of the condition is relatively easy. Suppose a perfect matching $M$ exists. For any $U\subseteq V$, after deleting from graph $G$ the vertices in $U$, every connected component with an odd number of vertices has at least one vertex that cannot be matched with a vertex in the same connected component; these vertices can only seek matches with vertices in $U$. The existence of such a matching requires at least $\operatorname{odd}(G-U)\le |U|$. This is Tutte's condition.

The sufficiency of the condition is more complicated. Suppose $G$ satisfies Tutte's condition but has no perfect matching. Since adding any edge to $G$ preserves Tutte's condition, without loss of generality assume that $G$ is a maximal graph with this property: $G$ has no perfect matching, but adding to graph $G$ any edge $e$ that is not already present makes $G+e$ have a perfect matching. Let $U\subseteq V$ be the set of all vertices of degree $|V|-1$. It can be proved that every connected component of $G-U$ is a complete graph. We can then construct a perfect matching of $G$: first take a maximum matching in each connected component of $G-U$; this leaves an unmatched vertex only when the component has an odd number of vertices. Match these unmatched vertices to vertices in $U$. Since $G$ has an even number of vertices (by taking $U=\varnothing$ in Tutte's condition), the number of as-yet-unmatched vertices remaining in $U$ is also even, so pair them up. This contradiction shows that there is no graph $G$ satisfying Tutte's condition but lacking a perfect matching.

The key is to prove that every connected component of $G-U$ is a complete graph. Suppose otherwise. Without loss of generality, let vertices $x,y,z$ belong to such a connected component, with $(x,y)\in E$, $(y,z)\in E$, and $(x,z)\notin E$. Moreover, since $y\notin U$, there must be some $w\in V\setminus U$ such that $(y,w)\notin E$. By the maximality of $G$, graphs $G+(x,z)$ and $G+(y,w)$ have perfect matchings $M_1$ and $M_2$, respectively. Consider their symmetric difference $M_1\oplus M_2$. Every vertex in graph $(V,M_1\oplus M_2)$ has degree either $0$ or $2$, so $M_1\oplus M_2$ is in fact a disjoint union of several even cycles, each consisting of alternating matching edges from $M_1$ and $M_2$.

As shown in the figure, there are two cases:

• $(x,z)$ and $(y,w)$ lie on different cycles (as shown on the left): let the cycle containing $(y,w)$ be $C$. Then the edge set $M_2\oplus C$ is a perfect matching of graph $G$;
• $(x,z)$ and $(y,w)$ lie on the same cycle (as shown on the right): by symmetry, assume the cycle passes through $x,y,w,z$ in that order. Thus, take the path on the cycle from $y$ through $w$ to $z$ and denote it by $P$, and let $\{(y,z)\}\cup P$ be the cycle $C$. Then the edge set $M_2\oplus C$ is likewise a perfect matching of graph $G$.

In either case, this contradicts the choice of $G$. The contradiction proves that every connected component of $G-U$ is a complete graph.

Corollary

Every bridgeless 3-regular graph has a perfect matching.

Proof

To verify Tutte's condition, take any $U\subseteq V$ and prove that $\operatorname{odd}(G-U)\le |U|$. Let $G_1,\cdots,G_n$ be all connected components of $G-U$ with an odd number of vertices. Let $m_i$ be the number of edges connecting vertices in $G_i$ to vertices in $U$. Simple counting gives

$$3|V(G_i)| = \sum_{v\in V(G_i)} d(v) = 2|E(G_i)| + m_i.$$

Thus $m_i$ must be odd. Since $G$ has no bridge (that is, no cut edge), $m_i\ge 3$. Therefore

$$\operatorname{odd}(G-U) = n \le \dfrac{1}{3}\sum_{i=1}^n m_i \le \dfrac{1}{3}\sum_{v\in U} d(v) = |U|.$$

Thus Tutte's condition holds, and graph $G$ necessarily has a perfect matching.

Common algorithms

A basic problem in combinatorial optimization is to find a maximum matching and a maximum-weight matching of a graph.

Maximum matching in bipartite graphs

See the Maximum matching in bipartite graphs page for details.

In an unweighted bipartite graph, the Kuhn algorithm solves the problem in $O(|V||E|)$ time, while the Hopcroft–Karp algorithm solves it in $O(|V|^{1/2}|E|)$ time.

Maximum-weight matching in bipartite graphs

See the Maximum-weight matching in bipartite graphs page for details.

In a weighted bipartite graph, the Hungarian algorithm can be used. If the Bellman–Ford algorithm is used when finding shortest paths, the time complexity is $O(|V|^2|E|)$; with Dijkstra's algorithm or a Fibonacci heap, the problem can be solved in $O(|V|^{2}\log {|V|}+|V||E|)$ time.

Maximum matching in general graphs

See the Maximum matching in general graphs page for details.

In an unweighted general graph, Edmonds' blossom algorithm solves the problem in $O(|V|^2|E|)$ time.

Maximum-weight matching in general graphs

See the Maximum-weight matching in general graphs page for details.

In a weighted general graph, Edmonds' blossom algorithm solves the problem in $O(|V|^2|E|)$ time.

Related problems

Maximum (weight) matching is closely related to other graph-theoretic problems. This section discusses only general graphs; for results concerning bipartite graphs, see the Maximum matching in bipartite graphs page.

Maximum-weight maximum-cardinality matching

The maximum-weight maximum-cardinality matching problem and the maximum-weight matching problem can be reduced to each other. One significant difference between them is that negative-weight edges may occur in maximum-weight maximum-cardinality matching, whereas maximum-weight matching never uses negative-weight edges.

First, the maximum-weight matching problem can be reduced to the maximum-weight maximum-cardinality matching problem. First, set the weights of all negative-weight edges in graph $G$ to $0$; then, by adding several edges of weight $0$, extend the graph to a complete graph $G'$. Notice that in a complete graph with nonnegative edge weights, maximum-weight maximum-cardinality matching and maximum-weight matching coincide. Therefore, it suffices to compute the maximum-weight maximum-cardinality matching of $G'$, denoted by $M'$, then delete all zero-weight edges from $M'$; the resulting edge set $M$ is a maximum-weight matching of graph $G$.¹

Conversely, the maximum-weight maximum-cardinality matching problem can also be reduced to the maximum-weight matching problem. Add to every edge of graph $G$ a sufficiently large positive number $K$. This ensures that a maximum-weight matching of the resulting graph $G'$ is also a maximum matching, and hence necessarily a maximum-weight maximum-cardinality matching. This is because finding a maximum-weight matching of graph $G'$ is equivalent to maximizing over all matchings of graph $G$:

$$K|M| + \sum_{e\in M}w(e).$$

When $K$ is sufficiently large, the gain $K$ from matching one additional edge exceeds the change in the weight sum of the latter term. Therefore, the algorithm first matches as many edges as possible and only then maximizes the sum of the weights of matched edges. The choice of constant $K$ only needs to ensure that it is strictly greater than the difference between the values of any two possible matchings. An obvious choice is

$$K = \sum_{e\in E}|w(e)| + 1.$$

Minimum (weight) edge cover

Another problem closely related to maximum (weight) matching is minimum (weight) edge cover. The relationship between edge cover and matching (also called an independent edge set) is similar to the relationship between vertex cover and independent set.

In graph $G=(V,E)$, a set of edges $C\subseteq E$, if every vertex $v\in V$ is an endpoint of an edge in $C$, then $C$ is called an edge cover of graph $G$. When discussing edge covers, we always assume that graph $G$ has no isolated vertices.

For an unweighted graph, the minimum edge cover problem is almost exactly the maximum matching problem. For graph $G$, take any maximum matching $M$, adding one incident edge for every unmatched vertex yields a minimum edge cover $C$. Their sizes satisfy the simple relation $|M|+|C|=|V|$. The figure below shows some examples of minimum edge covers:

For a weighted graph, the minimum-weight edge cover problem can be reduced to a minimum-weight perfect matching problem. First, copy graph $G=(V,E)$ to obtain $\tilde G=(\tilde V,\tilde E)$, with the same edge weights; then connect every vertex $v\in V$ to its copy $\tilde v\in\tilde V$, assigning it the minimum weight among the edges incident in graph $G$ to $v$. Denote the resulting graph by $G'=(V',E')$. If graph $G$ is bipartite or sparse, then graph $G'$ is likewise bipartite or sparse, respectively. Moreover, the minimum-weight edge cover problem of graph $G$ reduces to the minimum-weight perfect matching problem of graph $G'$²: for graph $G'$, let $M'$ be a minimum-weight perfect matching; keep only the edges in $E$, and replace every matched $(v,v')$ with an edge of minimum weight in graph $G$ incident to $v$; the result is a minimum-weight edge cover of graph $G$.

References

1. Wikiwand - Matching (graph theory)
2. Wikiwand - Blossom algorithm
3. 2015, "A Brief Discussion of Graph Matching Algorithms and Their Applications" — Chen Yinbo
4. Algorithm Notes - Matching
5. the-tourist/algo
6. Bill Yang's Blog - Study Notes on the Blossom Algorithm
7. Maximum matching, perfect matching, and the Hungarian algorithm in bipartite graphs
8. Wikiwand - Hopcroft–Karp algorithm
9. Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty. Graph theory with applications. Vol. 290. London: Macmillan, 1976.

Footnotes

1. Of course, this is not the only way to perform the reduction. For graph $G=(V,E)$, one can instead connect a copy $\tilde G=(\tilde V,\tilde E)$ point by point to the original graph and set the weights of all edges newly added with respect to the original graph $G$ (including edges in the copy) to $0$, obtaining graph $G'=(V',E')$. In other words, the vertex set of new graph $G'$ is $V\cup V'$, and its edge set contains, in addition to the edges of graph $G$, zero-weight edges connecting every vertex $v\in V$ to its copy $\tilde v\in V$, and, for every edge $(u,v)\in E$, zero-weight edges connecting $\tilde u$ and $\tilde v$. Every matching in graph $G$, denoted by $M$, corresponds to a perfect matching of the same total weight in graph $G'$: simply match the unmatched vertices of graph $G$: each vertex $v$ with its copy $\tilde v$, and for every matched edge $(u,v)$, match $\tilde u$ with $\tilde v$. Thus, the maximum-weight maximum-cardinality matching in graph $G'$, which is also a maximum-weight perfect matching, restricted to $E$, yields a maximum-weight matching in graph $G$. The advantage of this reduction is that if graph $G$ is bipartite or sparse, the expanded graph $G'$ is also bipartite or sparse, respectively. ↩

2. For graph $G'$, every perfect matching $M'$ can be used in the manner described here to obtain an edge cover of graph $G$, denoted by $C$, whose total weight is half that of the former; conversely, reversing this construction, for every edge cover of graph $G$, denoted by $C$, one can construct a perfect matching of graph $G'$, denoted by $M'$, whose total weight is no more than twice that of the former. This shows that the reduction is valid. ↩