Maximum Matching in General Graphs
Blossom algorithm
The blossom algorithm solves the maximum cardinality matching problem in general graphs. Jack Edmonds proposed it in 1961. With some modifications it also solves the maximum weight matching problem in general graphs. It was the first algorithm to prove that maximum matching can be solved in polynomial time.
Matching in a general graph differs from bipartite matching in that the graph may contain odd cycles.
Take this graph as an example. If we simply flip the path (swap its matching and non-matching edges), the resulting \(M\) is not a valid matching: some vertices end up on two matching edges. The odd cycle is what causes the trouble.
Now consider how to augment in a general graph. We start as in the bipartite case. Take each unmatched vertex in turn, make it the root and label it "o", then label the vertices alternately "o" and "i". Every edge from an "i" vertex to an "o" vertex is a matching edge.
Let \(v\) be the current vertex and \(u\) one of its neighbors. There are two cases:
- \(u\) has not been visited. If it is unmatched, we have found an augmenting path; otherwise we go on searching from the mate of \(u\).
- \(u\) has been visited. If it is labeled "o", we have to contract a blossom; otherwise we have met an even cycle, and we skip it.
An even cycle is handled exactly as in a bipartite graph, so it can be ignored. After contracting the blossom, we continue to look for an augmenting path in the new graph.
Let \(G\) be the original graph and \(G'\) the graph after contracting the blossom. We only need to prove two things:
- If \(G\) has an augmenting path, so does \(G'\).
- If \(G'\) has an augmenting path, so does \(G\).
Let \((u,v)\) be the non-tree edge (the edge that closes the cycle), and define the base of the blossom as \(h=LCA(u,v)\). The odd cycle alternates everywhere except at \(h\), the only vertex whose two cycle edges have the same type: both are non-matching edges. So the tree edge that enters \(h\) must be a matching edge, and every edge that leaves the cycle from a vertex other than \(h\) is a non-matching edge.
There are two ways to leave the cycle through one of these outside edges: clockwise or counterclockwise.
So contracting the blossom and not contracting it are equally correct.
In an implementation there is no need to actually contract a blossom once we find it: an array can record, for each vertex, the base of the blossom that contains it.
Complexity analysis
Each search for an augmenting path traverses all the edges and, whenever it meets a blossom, updates the vertices on that blossom: \(O(|E|^2)\).
Searching for an augmenting path from every unmatched vertex gives \(O(|V||E|^2)\) in total.
Reference code
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | |
UOJ #79. Maximum Matching in General Graphs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 | |
Matching in general graphs by Gaussian elimination
Hint
Before reading on, you may want to read the pages on matrices in the linear algebra section:
- Matrices
- Determinants
- Gaussian elimination
This section presents a matching algorithm for general graphs that is based on Gaussian elimination. Compared with the classical blossom algorithm, it is easier to understand and to code, and it adapts well to problems such as finding the vertices that every maximum matching must cover. Its drawback is a large constant factor: Gaussian elimination really does use its full \(O(n^3)\), whereas the blossom algorithm rarely reaches its worst case.
Prerequisites: the Tutte matrix
Definition: For an undirected graph \(G = (V, E)\) with \(n\) vertices, the Tutte matrix \(\tilde{A}(G)\) is the \(n \times n\) matrix with entries
Each \(x_{i, j}\) is a variable, so \(\tilde{A}(G)\) contains \(|E|\) variables in all.
Where no confusion can arise, we write \(\tilde{A}\) for \(\tilde{A}(G)\).
Theorem (Tutte's theorem): \(G\) has a perfect matching if and only if \(\det \tilde{A} \ne 0\).
Proof
We need the notion of an even cycle cover: an even cycle cover of an undirected graph \(G\) is a set of even cycles (2-cycles included) that covers every vertex exactly once.
It is easy to show that \(G\) has a perfect matching if and only if it has an even cycle cover.
- If \(G\) has an even cycle cover, taking every other edge of each cycle gives a perfect matching.
- If \(G\) has a perfect matching, the 2-cycles that correspond to its matching edges form an even cycle cover.
Next we prove that \(G\) has an even cycle cover if and only if \(\tilde{A} \ne 0\).
Consider the definition of the determinant
where \(\pi\) ranges over all permutations, and \((-1)^{\pi}\) is \(-1\) if \(\pi\) has an odd number of inversions and \(1\) otherwise.
Every permutation can be viewed as a cycle cover of \(G\). If this cycle cover contains an odd cycle, its term and the term obtained by reversing that cycle sum to \(0\). So only even cycle covers can make the determinant different from \(0\), which completes the proof.
Theorem: \(\operatorname{rank}\tilde{A}\) is always even, and the size of a maximum matching of \(G\) is half of \(\operatorname{rank}\tilde{A}\).
Proof
The rank of a skew-symmetric matrix is always even. The second claim is left to the reader.
In practice we cannot compute with \(|E|\) variables. Instead we choose a number field, for example the residue system \(\mathcal{Z}_p\) of some prime \(p\), replace each variable by a random element of \(\mathcal{Z}_p\), and compute with those. For convenience, where no confusion can arise, \(\tilde{A}\) from now on denotes the matrix after this substitution.
Theorem: \(\operatorname{rank}\tilde{A}\) is at most twice the size of a maximum matching of \(G\), and the two are equal with probability at least \(1 - \frac n p\).
In maximum matching problems on general graphs \(n\) hardly ever exceeds \(10^3\), so in practice a prime \(p\) of the order of \(10^9\) is enough.
By this theorem, if you need only the size of a maximum matching and not the matching itself, a single Gaussian elimination that computes \(\operatorname{rank}\tilde{A}\) is enough, which is far simpler than the blossom algorithm. Reconstructing a solution is a little more complicated and needs the algorithm described below.
Constructing a perfect matching
By Tutte's theorem and the theorem above, if \(G\) has a perfect matching, then \(\tilde{A}\) has full rank with high probability. For convenience we leave out "with high probability" from here on.
Let \(v_i\) be the vertex of \(G\) numbered \(i\). The following theorem goes one step further:
Theorem: \(\tilde{A}^{-1}_{j,i} \ne 0 \iff G - \{v_i, v_j\}\) has a perfect matching.
Inverse and adjugate matrices
For any square matrix \(A\) of order \(n\), the adjugate matrix is defined by \(A^*_{i, j} = (-1)^{i + j} M_{j, i}\), where \(M_{j, i}\) is the minor obtained by deleting row \(j\) and column \(i\). In other words, if \(M\) is the cofactor matrix of \(A\), then \(A^* = M^T\).
Theorem: If \(A\) is invertible, then \(A^{-1} = \frac 1 {\det A} A^*\).
So here \(A^{-1}_{j, i} \ne 0 \iff M_{i, j} \ne 0\), that is, what is left of \(A\) after deleting row \(i\) and column \(j\) has full rank.
In other words, if \((v_i, v_j) \in E\) and \(\tilde{A}^{-1}_{j, i} \ne 0\), then some perfect matching contains the edge \((v_i, v_j)\). We call such an edge an allowed edge.
For an undirected graph \(G\) that has a perfect matching, this theorem gives a fairly obvious brute-force algorithm for finding one. Repeatedly enumerate \(i, j\); if \((v_i, v_j)\) is an allowed edge (the edge exists and \(\tilde{A}^{-1}_{j, i} \ne 0\)), add \((v_i, v_j)\) to the matching, delete both vertices from \(G\), and recompute \(\tilde{A}^{-1}\).
There are \(\frac n 2\) rounds of \(O(n^3)\) each, so the total is \(O(n ^ 4)\), which is rather slow. But we do not have to invert the matrix by Gaussian elimination every time we recompute \(\tilde{A}^{-1}\). We can use the following theorem instead:
Theorem (elimination theorem): Let
with \(\hat a_{1, 1} \ne 0\). Then
The theorem is stated for eliminating the first row and the first column, but it clearly generalizes to any row and any column. So we compute \(\tilde{A}^{-1}\) only once, at the start of the algorithm, and each time two vertices are deleted we run the \(O(n^2)\) elimination twice.
This is rather abstract; the C++ code may help
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
There are \(\frac n 2\) rounds of \(O(n^2)\) each, so the algorithm finds a perfect matching in \(O(n^3)\) time.
Constructing a maximum matching
We now know how to construct a perfect matching, but problems usually ask for a maximum matching.
As noted earlier, the size of a maximum matching of \(G\) is half of \(\operatorname{rank}\tilde{A}\). If we can find a largest full-rank square submatrix of \(\tilde{A}\), then a perfect matching of the induced subgraph that corresponds to it is a maximum matching of \(G\).
Look at it from another angle. If \(G\) has a perfect matching, then \(\tilde{A}\) has full rank; in other words, \(\tilde{A}\) is linearly independent. So when \(\tilde{A}\) does not have full rank, we can find a basis of \(\tilde{A}\) and keep only the rows and columns that correspond to it. This gives a largest full-rank square submatrix of \(\tilde{A}\).
Once we have this submatrix, the algorithm above finds a perfect matching of the induced subgraph, which is a maximum matching of the original graph. Gaussian elimination may swap rows, so take care to keep track of the vertex numbers in your implementation.
UOJ #79. Maximum Matching in General Graphs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | |
Practice problems
References
- Mucha M, Sankowski P. Maximum matchings via Gaussian elimination
- Zixin Zhou, Jiaqi Yang. Matching in General Graphs Based on Linear Algebra (in Chinese)
- ZYQN, A Matching Algorithm for General Graphs Based on Linear Algebra (in Chinese)
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: H-J-Granger, accelsao, Ir1d, Early0v0, Henry-ZHR, HeliumOI, AntiLeaf, ShizuhaAki, pukui, Xeonacid, Enter-tainer, 24OI-bot, ksyx, Tiphereth-A, yusancky, CCXXXI (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.