Kőnig Bipartite Cover Duality

Theory

A bipartite graph consists of two disjoint sets of vertices, L (left) and R (right). A matching is a set of edges without common vertices. A vertex cover is a set of vertices that includes at least one endpoint of every edge. Kőnig's theorem states that for bipartite graphs, the cardinality of a maximum matching equals the cardinality of a minimum vertex cover.

Given a maximum matching, the minimum vertex cover can be constructed by exploring alternating paths:

• Find all unmatched left vertices.
• Trace paths alternating between unmatched and matched edges. Since the matching is maximum, there are no augmenting paths (paths ending at an unmatched right vertex).
• Let Z_L be the set of reachable left vertices and Z_R the set of reachable right vertices.
• The minimum vertex cover is formed by taking the unreached left vertices (L ∖ Z_L) and the reached right vertices (Z_R).

Worked Example

Consider a bipartite graph with edges L0-R0, L1-R0, and L2-R1. Let us find the maximum matching and the minimum vertex cover step-by-step.

1. First, we find a maximum matching. The edges L0-R0 and L2-R1 form a matching of size 2. No matching can be larger. Therefore, the maximum matching size is 2.
2. Next, we identify the unmatched left vertices. Here, L1 is not matched. We initialize the reachable set Z_L with {L1}.
3. From L1, we follow the unmatched edge to R0. So, R0 is added to Z_R.
4. From R0, we follow the matched edge back to L0. So, L0 is added to Z_L.
5. From L0, there are no new unmatched edges to follow. The reachability process ends. We have Z_L = {L0, L1} and Z_R = {R0}.
6. The minimum vertex cover is formed by the unreached left vertices and reached right vertices. The unreached left vertices are L ∖ Z_L = {L0, L1, L2} ∖ {L0, L1} = {L2}. The reached right vertices are Z_R = {R0}. Thus, the minimum cover is {L2, R0}.
7. The size of the minimum cover is 1 + 1 = 2. As expected, this matches the maximum matching size of 2.

Experiment

Interact with the Kőnig Bipartite Cover Duality module to visualize this process on different graph configurations.

1. Open the Kőnig Bipartite Cover Duality module.
2. Use the Graph dropdown to select the "Deficient" preset.
3. Observe that the maximum matching consists of the edges L0-R0 and L2-R1, and the unmatched vertex L1 initiates the reachability trace.
4. Switch to the "Perfect" preset and notice that because every vertex is matched, there are no unreached left vertices, and the cover simply consists of all left vertices.

Limitations

Kőnig's theorem applies strictly to bipartite graphs. In general non-bipartite graphs, the maximum matching size provides a lower bound for the minimum vertex cover, but the exact equality does not hold. For example, a triangle has a maximum matching of size 1, but its minimum vertex cover has size 2. Finding a minimum vertex cover in general graphs is NP-hard.

References

More information about bipartite matching and Kőnig's theorem can be found in the Sedgewick & Wayne documentation for algorithm implementations.

• Bipartite Matching (Sedgewick & Wayne)