05 Matchings in Bipartite Graphs

Lecture from: 04.03.2025 | Video: Homelab

Recap: Hall’s Marriage Theorem

In the previous lecture, we introduced Hall’s Marriage Theorem, a fundamental result in bipartite matching theory. Let’s briefly recap its statement and significance.

Hall’s Marriage Theorem: For a bipartite graph $G=(A\cup B,E)$, there exists a matching $M$ that saturates $A$ (i.e., $|M|=|A|$) if and only if Hall’s condition holds:

Hall’s Condition: For every subset $X\subseteq A$, the size of its neighborhood $N(X)={\bigcup }_{x\in X}N(x)$ is at least as large as the size of $X$:

$|X|\le |N(X)|\forall X\subseteq A$

This theorem provides a necessary and sufficient condition for the existence of a complete matching from set $A$ to set $B$. It’s a powerful tool for determining whether a perfect matching is possible in a bipartite graph, especially when dealing with constraints on vertex neighborhoods.

For the proof of Hall’s Theorem, look at the video at the end of the previous lecture note…

Frobenius Theorem

A direct consequence of Hall’s Marriage Theorem is a result known as Frobenius’ Theorem, particularly relevant for regular bipartite graphs.

Corollary (Frobenius): For any positive integer $k$, every $k$-regular bipartite graph contains a perfect matching.

Explanation: A $k$-regular bipartite graph is one where every vertex in both partitions $A$ and $B$ has a degree of exactly $k$. In such a graph, $|A|=|B|$ must hold because the sum of degrees in $A$ must equal the sum of degrees in $B$ (Handshaking Lemma for bipartite graphs: ${\sum }_{a\in A}deg(a)={\sum }_{b\in B}deg(b)⟹k|A|=k|B|⟹|A|=|B|$).

To see why Frobenius’ Theorem follows from Hall’s Theorem, consider a $k$-regular bipartite graph $G=(A\cup B,E)$. For any subset $X\subseteq A$, let $E(X,N(X))$ be the set of edges between $X$ and $N(X)$. By regularity, the number of edges leaving $X$ is $k|X|$. These edges must all land in $N(X)$. The sum of degrees of vertices in $N(X)$ is at most $k|N(X)|$. Since all edges from $X$ must go to $N(X)$:

$k|X|=|E(X,N(X))|\le {\sum }_{v\in N(X)}deg(v)=k|N(X)|$

Dividing by $k$ (since $k>0$), we get $|X|\le |N(X)|$. This holds for all $X\subseteq A$, so Hall’s condition is satisfied. By Hall’s Marriage Theorem, there exists a matching that saturates $A$. Since $|A|=|B|$, a matching saturating $A$ in a balanced bipartite graph is a perfect matching.

Important Note: The bipartiteness condition is crucial for both Hall’s Marriage Theorem and Frobenius’ Theorem. Regular graphs in general (non-bipartite) do not necessarily have perfect matchings.

Algorithms for Finding Maximum Matchings in Bipartite Graphs

While Hall’s theorem gives a condition for the existence of a matching, we now turn our attention to algorithms that can actually find maximum matchings, especially in bipartite graphs.

There are different kinds of matching algorithms:

Augmenting Paths: Revisited

As discussed previously, the concept of augmenting paths is central to finding maximum matchings.

Definition of $M$-Augmenting Path: Given a matching $M$, an $M$-augmenting path is a path that:

1. Alternates between edges not in $M$ and edges in $M$.
2. Starts and ends at vertices that are unmatched by $M$.

Key Algorithm Idea

1. Start with an initial matching (possibly empty).
2. Repeatedly search for an augmenting path.
3. If an augmenting path is found, augment the matching along this path, increasing the matching size by one.
4. Continue until no more augmenting paths can be found. At this point, the matching is guaranteed to be maximum (by Berge’s Theorem).

Breadth-First Search (BFS) for Finding Augmenting Paths in Bipartite Graphs

In bipartite graphs, we can efficiently use Breadth-First Search (BFS) to find augmenting paths. Let $G=(A\cup B,E)$ be a bipartite graph and $M$ be a current matching.

BFS Algorithm for Alternating Paths

1. Initialization:

   • $L_0$: Set of all unmatched vertices in $A$. These are the starting points for our search.
   • Mark all vertices in $L_0$ as visited.
   • Initialize level $i=1$.

2. Iterative Level Expansion: Repeat the following steps until no new vertices can be added to the current level:

   • If $i$ is odd (edges from $L_{i-1}$ to $L_i$ are not in $M$):

     • $L_i$: Collect all unvisited neighbors of vertices in $L_{i-1}$ that are reached via edges not in the matching $M$ (i.e., edges in $E\setminus M$).

   • Else if $i$ is even (edges from $L_{i-1}$ to $L_i$ are in $M$):

     • $L_i$: Collect all unvisited neighbors of vertices in $L_{i-1}$ that are reached via edges in the matching $M$.

   • Mark all vertices in $L_i$ as visited.

   • Increment $i$.

3. Augmenting Path Detection: During the BFS, if we reach an unmatched vertex $v\in B$ in some level $L_i$, we have found an augmenting path. We can reconstruct the path by backtracking from $v$ to a vertex in $L_0$ using the predecessor information maintained during BFS. Return the found augmenting path.

4. No Augmenting Path: If the BFS completes and no unmatched vertex in $B$ is reached, then there are no augmenting paths starting from the current set of unmatched vertices in $A$. In this case, the current matching $M$ is a maximum matching. Return that no augmenting path is found.

Level Interpretation: In this BFS, $L_i$ represents the set of vertices reachable from the initial unmatched vertices in $A$ via an alternating path of length $i$. Specifically, $L_i$ is the set of vertices $v$ such that the shortest alternating path from an unmatched vertex in $A$ to $v$ has length $i$.

Time Complexity of BFS Augmenting Path Search

In a bipartite graph, each BFS to find an augmenting path takes $O(|V|+|E|)$ time, as we explore vertices and edges in a breadth-first manner.

Hopcroft-Karp Algorithm: Efficient Maximum Matching in Bipartite Graphs

The Hopcroft-Karp algorithm is a more advanced and efficient algorithm for finding maximum matchings in bipartite graphs. It improves upon the basic augmenting path algorithm by finding a maximal set of shortest augmenting paths in each iteration, rather than just a single augmenting path.

We’ll discuss this algorithm in depth next time…