Matchings in Bipartite Graphs and the Kőnig-Egerváry Theorem via LP Duality
We discuss how we can compute Maximum Matchings in bipartite graphs, and why these are equal to Minimum Vertex Covers.
In this article, we will discuss a beautiful combinatorial result that relates maximum matchings to minimum vertex covers in bipartite graphs, and was proved in 1931 by Dénes Kőnig, and independently by Jenő Egerváry, whose proof also applies to weighted graphs. The result, formally stated below, is now known as Kőnig’s theorem or Kőnig-Egerváry theorem.
The Kőnig-Egerváry theorem
In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.
We will prove the above result by using a very strong and important tool, namely, Linear Programming Duality. This will also allow us to obtain a very simple algorithm for computing a maximum matching in a bipartite graph, or equivalently, a minimum vertex cover. Before diving into details, we introduce the terms that appear in the above statement; the reader that can fully understand and parse the above statement can skip the “terminology” subsection.
Some terminology
- Bipartite graph: a graph G = (V, E) where the vertex set can be partitioned into two non-empty sets V₁ and V₂, such that every edge connects a vertex of V₁ to a vertex of V₂. An example of a bipartite graph is given in the figure below.
- Matching: a subset M of edges of a graph, such that there are no two edges in M that share an endpoint.
- Vertex Cover: a subset C of vertices of a graph, such that for every edge, at least one of its endpoints is contained in C.
- Maximum Matching: a matching that contains the largest possible number of edges.
- Minimum Vertex Cover: a vertex cover that contains the smallest possible number of vertices.
Warm-up: general graphs
We start with an observation about vertex covers and matchings in general graphs. Suppose that we are given a graph G = (V, E) and a maximal matching Mof G. As a reminder, a matching M is maximal if we cannot add any more edges to it, while maintaining that it is a matching. Note that this does not imply that M is maximum. A simple example demonstrating this is the 3-path graph, which is depicted in the figure below.
Given a maximal matching M, we observe that any vertex cover must cover all edges of M, and thus, it must contain at least one endpoint of every edge of M. Moreover, every edge not contained in M shares an endpoint with at least one edge of M, since M is a maximal matching. Thus, if we define the set C to be the set of all endpoints of the edges contained in M, then we are guaranteed that C is a feasible vertex cover! Putting everything together, we conclude that
|M*| ≤ |C*| ≤ |C| = 2|M| ≤ 2|M*|,
where C* is a minimum vertex cover and M* is a maximum matching of G. (Although the above chain of inequalities is not the focus of this article, I would still recommend that you try to fully understand why each inequality holds.)
The above shows that in any graph, the maximum matching is smaller or equal than the minimum vertex cover, and moreover, the two quantities are within a factor of 2 from each other!
One can easily show that this factor of 2 is actually tight. A simple example that demonstrates this is given below.
We are now ready to discuss a proof of the Kőnig-Egerváry theorem, which shows that the two quantities are, in fact, equal, when we restrict ourselves to bipartite graphs.
A proof the Kőnig-Egerváry theorem via LP duality
Let G = (V, E) be a bipartite graph, where V is partitioned into two non-empty sets V₁ and V₂. We start by considering the Maximum Matching problem, for which we write the following natural integer linear program that describes it; from now on, we refer to it as (IP). We use the notation δ(u) to denote the set of edges whose one endpoint is vertex u.
(IP)
The above integer linear program is very easy to understand; the main constraint simply asks that for each vertex u, there is at most one edge of the matching that is adjacent to it.
For reasons that will become clear in a few moments, we now remove the integrality constraints in the above program, and simply ask that the variables x(e) be non-negative. More formally, we write the following linear program which, from now on, we refer to as (LP).
(LP)
First, we observe that due to the first set of constraints, each variable x(e) cannot be more than 1, and thus, any feasible solution of the above linear program satisfies 0≤ x(e) ≤ 1 for every edge e. This, in particular, implies that the feasible region of the above LP is contained in the [0,1]ᴱ hypercube.
The goal now is to show that the (IP) and (LP) programs written above are essentially equivalent, in that there always exists an optimal solution of (LP) that is integral. This will imply that the optimal values of the two programs are equal. For that, the crucial property that we need to exploit is what is known as Total Unimodularity, that is defined as follows.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. Equivalently, every square submatrix has determinant 0, +1 or −1.
Whey do we care about TU matrices?
TU matrices are extremely important in Combinatorial Optimization, since a linear program whose constraint matrix is TU describes an integral polytope, in the sense that every extreme point of the polytope is integral. More precisely, the following holds.
If A is TU and b is integral, then the LP {max cᵀx ∣ A x ≤ b} has integral optimum, for any c. Hence if A is totally unimodular and b is integral, every extreme point of the feasible region { x ∣ A x ≤ b } is integral and thus the feasible region is an integral polyhedron.
Thus, if we are able to show that the constraint matrix of the LP we wrote for Maximum Matching is TU, then we can conclude that the optimal value of the programs (IP) and (LP) are equal, or, in other words, that the (LP) we wrote above fully captures the Maximum Matching problem, despite the fact that we have dropped the integrality constraints on the variables.
Finally, in order to show that the constraint matrix of the (LP) is TU, we use the very useful Ghouila-Houri criterion, that states that:
A matrix is TU iff for every subset R of rows, there is an assignment s : R → ± 1 of signs to rows so that the signed sum Σ s(r) r (where the sum is taken over the rows in R and is a row vector of the same width as the matrix) has all its entries in {0 , ±1}.
Back to our proof
In order to use the above criterion, we write (LP) as
and observe that a row of the constraint matrix of (LP) has one of two possible forms:
- it is equal to the indicator vector of the edges adjacent to a vertex u, or
- it is equal to the minus of an indicator vector of a single edge.
It is easy to see that it suffices to apply the Ghouila-Houri criterion only to the submatrix containing the first class of constraints of the above LP. So, we focus on the rows of the first form. Let R be a subset of these rows. The set R directly corresponds to a set of vertices, which we partition into R₁ and R₂, where R₁ is the intersection of R and V₁ and R₂ is the intersection of R and V₂. We now define the assignment s as:
- s(r) = 1, if r is in R₁
- s(r) = -1, if r is in R₂.
We consider the signed sum over the rows of R and observe that every edge appears at most twice in the sum. If an edge appears at most once, then its entry is trivially equal to {0 , ±1}, while if it appears exactly twice, then, by construction of s, it must appear once with a “+” sign and once with a “-” sign, since the graph is bipartite, and so its entry in this case is equal to 0. We conclude that the entry corresponding to any edge in this signed sum is equal to {0 , ±1}. Thus, the Ghouila-Houri criterion shows that the constraint matrix is TU!
LP Duality and the Minimum Vertex Cover problem
So far, we have proved that (LP) is equal to the convex hull of the indicator vectors of feasible matchings of a bipartite graph. We now turn to a very powerful tool, Linear Programming Duality. We consider (LP) as a primal LP, and write its dual LP which, from now on, we refer to as (D-LP).
(D-LP)
By LP Duality, we immediately get that the optimal values of (LP) and (D-LP) are equal.
Let’s observe now what the above LP describes. First, it is easy to see that in an optimal solution of the above LP, every variable y(u) is at most 1; if it is larger than 1, then by reducing it and making it equal to 1, we get a cheaper solution that, clearly, is still feasible. Moreover, for each edge (u,v), the above LP asks that at least one of its endpoints is selected, and the goal is to minimize the total number of vertices selected. If this rings a bell, it is because this is exactly the task we have to solve in the Minimum Vertex Cover problem! Thus, we see that (D-LP) describes the fractional Minimum Vertex Cover problem; this is because the variables in the above LP are real numbers and are not restricted to be integers.
We are almost done! The only thing remaining to prove now is that (D-LP) always has an integral optimum. This will imply that its optimal solution is always a feasible (integral) Vertex Cover of our graph. Assuming that this is the case, and putting everything together, this will give
OPT(MATCHING) = OPT(LP) = OPT(D-LP)=OPT(VERTEX COVER).
In other words, this will finish the proof of the Kőnig-Egerváry theorem!
The Vertex Cover LP is integral in bipartite graphs
The only task left to do is show that (D-LP) always has an integral optimum. We can resort again to total unimodularity, but we decide here to provide a self-contained proof of the fact that the extreme points of (D-LP) are integral.
Let y be a feasible extreme point of (D-LP). Since y is an extreme point, this means that it cannot be written as a convex combination of other feasible and distinct points of (D-LP). If y has no fractional coordinates, we are done. Moreover, if y has a coordinate that is strictly larger than 1, then we can define two distinct solutions that only differ in that coordinate (by slightly increasing that coordinate in one of the solutions, and slightly decreasing it in the other solution) in such a way so that their average is exactly equal to y, which would lead to a contradiction (as y is an extreme point).
So, the only interesting case left to analyze is the case where every coordinate is between 0 and 1 and there exists at least one coordinate of y that is strictly fractional. Let S₁ be the set of vertices of V₁ whose y-coordinate is a value strictly between 0 and 1. Similarly, let S₂ be the set of vertices of V₂ whose y-coordinate is a value strictly between 0 and 1. We now define
In words, ε is equal to the minimum distance of any y-coordinate of the vertices in S₁ and S₂ to its closest integer value, i.e., to 0 or 1 (whichever is closer to it). Moreover, we define two vectors y₁ and y₂.
It is not hard to see that both y₁ and y₂ are feasible solutions of (D-LP). This is due to the fact that, given an edge (u,v), if u belongs to S₁, then v will necessarily belong to S₂. Furthermore, we assume that either S₁ or S₂ is non-empty, since otherwise the vector y is already integral. This implies that ε > 0, which further implies that y₁ and y₂ are distinct from y. To finish the proof, we observe that
y = 0.5 y₁ + 0.5 y₂.
This means that y is not an extreme point, and thus we get a contradiction!
Summary of proof
To recap, we first wrote the linear programming relaxation for Maximum Matching in bipartite graphs, and we showed, by using total unimodularity, that the relaxation is, in fact, integral. We then wrote the dual of this LP, which ended up being the fractional Minimum Vertex Cover problem. Finally, we showed that this dual LP is also integral. Thus, by LP duality, the value of the Maximum Matching in a bipartite graph is equal to the value of the Minimum Vertex Cover!
Conclusion
In this article, we discussed the Kőnig-Egerváry theorem that shows that the size of the maximum matching is always equal to the size of the minimum vertex cover, when the graph is bipartite. Using the LP duality proof, one can also generalize this result to weighted graphs. The above result immediately suggests an efficient algorithm for computing a Maximum Matching (or, equivalently, a Minimum Vertex Cover), in a bipartite graph.
Algorithm for Maximum Matching in bipartite graphs:
- Solve the LP relaxation and obtain an optimal extreme point solution.
As demonstrated above, the above theorem does not hold if the graph is not bipartite. Moreover, there is an interesting computational separation between Maximum Matching and Minimum Vertex Cover in general graphs. The Maximum Matching problem still admits efficient algorithms, even in general graphs, or in other words, it is in P, while the Minimum Vertex Cover problem is known to be NP-hard in general graphs.
