Maximum Bipartite Matching via Flow

A matching in a bipartite graph can be found by reduction to maximum flow. This is one of the cleanest applications of network flow theory and appears frequently on Tripos papers.

Bipartite Matching

A bipartite graph $G = (V, E)$ has $V = L \cup R$ with $L \cap R = \emptyset$ and every edge crossing between $L$ and $R$: $E \subseteq L \times R$.

A matching $M \subseteq E$ is a set of edges such that no vertex is incident to more than one edge in $M$. A vertex is matched if some edge in $M$ is incident on it; otherwise it is unmatched.

A maximum matching is a matching of maximum cardinality. A maximal matching is one that cannot be extended (not necessarily maximum).

Flow Network Construction

Given a bipartite graph $(L \cup R, E)$, construct a flow network $G'$:

1. Add source $s$ and sink $t$
2. For each $u \in L$, add directed edge $(s, u)$ with capacity 1
3. For each $v \in R$, add directed edge $(v, t)$ with capacity 1
4. For each $(u, v) \in E$ (with $u \in L$, $v \in R$), direct from $L$ to $R$ with capacity 1

Why This Works

Run Ford-Fulkerson or Edmonds-Karp on $G'$. All capacities are 1 and integral, so the maximum flow assigns 0 or 1 to every edge. By the Integrality Theorem, there exists an integral maximum flow (all edge flows are integers). Since each vertex in $L$ receives at most 1 unit from $s$, each $u \in L$ sends flow to at most one $v \in R$. Symmetrically, each $v \in R$ receives at most 1 unit. The edges with flow 1 form a valid matching.

The size of the maximum matching equals the value of the maximum flow: $|M| = |f|$.

Running Time

Maximum flow value is at most $|L| \le |V|/2$, so at most $|V|/2$ augmentations. Each BFS finds an augmenting path in $O(|E|)$ time. Total: $O(|V| \cdot |E|)$.

Alternating Paths View

An alternating path (with respect to matching $M$) alternates between edges not in $M$ and edges in $M$. An augmenting path is an alternating path starting and ending at unmatched vertices. Augmenting along such a path (toggling matched/unmatched status of each edge) increases matching size by 1.

The flow-based BFS on the residual network corresponds exactly to finding augmenting paths in the alternating-paths view:

• Forward edge ($L \to R$, not in matching) corresponds to residual forward capacity
• Backward edge ($R \to L$, in matching) corresponds to residual reverse capacity (flow cancellation)

Worked Example

Bipartite graph: $L = \{a, b, c\}$, $R = \{x, y, z\}$.

Edges: $(a, x)$, $(a, y)$, $(b, y)$, $(b, z)$, $(c, x)$.

Flow network: $s \to a, b, c$ (all capacity 1), $a \to x, y$, $b \to y, z$, $c \to x$ (all capacity 1), $x, y, z \to t$ (all capacity 1).

Run Edmonds-Karp:

1. Path $s \to a \to x \to t$: match $(a, x)$
2. Path $s \to b \to y \to t$: match $(b, y)$
3. Path $s \to c \to x \to a \to y \to b \to z \to t$? No, residual: $x \to t$ is saturated, so $x \to a$ exists (reverse). Path $s \to c \to x$ then reverse $x \to a$ (not valid, $a$ has no outgoing residual to $t$ directly…).

Actually: $s \to c \to x \to a$ (reverse, cancels existing match) $\to y \to t$. This is the augmenting path: unmatch $(a, x)$, match $(c, x)$ and $(a, y)$. Now matching: $(c, x)$, $(a, y)$, $(b, ?)$.

4. Path $s \to b \to z \to t$: match $(b, z)$.

Maximum matching: $(c, x)$, $(a, y)$, $(b, z)$ with size 3. This is a perfect matching (all vertices matched).

Beyond BFS: Hopcroft-Karp

Hopcroft-Karp finds multiple vertex-disjoint shortest augmenting paths per BFS round using a layered graph and DFS. Running time improves to $O(|E| \cdot \sqrt{|V|})$. This is examinable but less commonly examined than the basic reduction.

Summary

Concept	Detail
Reduction	$L \cup R$ bipartite $\to$ flow network with $s$, $t$, unit capacities
Matching size	$= \lvert f \rvert$
FF/EK running time	$O(\lvert V \rvert \cdot \lvert E \rvert)$
Hopcroft-Karp	$O(\lvert E \rvert \cdot \sqrt{\lvert V \rvert})$
Integrality	Unit capacities + FF integral input $\implies$ integral output

Past Tripos: y2024p1q9, y2023p2q7.