From Augmenting Paths to an Algorithm
A matching is a set of edges no two of which share a vertex. An augmenting path for a matching \(M\) is a path whose edges alternate between edges outside \(M\) and edges in \(M\), beginning and ending with edges outside \(M\), with both endpoints unmatched by \(M\). The edge-flipping operation replaces the matching edges on this path by its nonmatching edges. It produces a matching with one more edge.
The algorithm repeatedly searches for such a path and flips it. For bipartite graphs, a breadth-first search can find an augmenting path, if one exists, in time proportional to the number of vertices and edges. The key is to direct the search according to which edges currently belong to the matching.
All graphs in this tutorial are finite and simple. A vertex is matched if it is incident with an edge of \(M\), and unmatched otherwise. In the search, a left vertex can be followed to its neighbors along edges outside \(M\); a right vertex can be followed only along its matching edge, if it has one. Thus every directed search path alternates between edges outside and inside \(M\).
The Repeated-Search Algorithm
Set \(M=\varnothing\). Store the graph by adjacency lists and choose an order for vertices and neighbors so that the search is reproducible.
Run breadth-first search in the directed search graph, using all currently unmatched vertices of \(L\) as starting vertices. Store a predecessor for each vertex reached.
If the search reaches an unmatched vertex of \(R\), follow predecessor links to recover the path and flip its edges: remove its edges in \(M\), and add its edges outside \(M\). Return to Step 2. If no unmatched vertex of \(R\) is reached, return \(M\).
When several unmatched starting vertices are used, breadth-first search places all of them in its initial queue. This is a multi-source search. A predecessor link for a starting vertex is marked as a source; every other predecessor records the previous vertex along the directed search. If a free right vertex is reached, following those links backwards recovers a simple path from some unmatched left vertex.
If an augmenting path has \(2j+1\) edges, then it has \(j+1\) edges outside \(M\) and \(j\) edges in \(M\). Flipping removes \(j\) matching edges and adds \(j+1\), so the matching size increases by exactly one. No vertex on the path is left incident with two selected edges: each internal vertex loses its path edge in \(M\) and gains the other path edge, while each endpoint gains one edge. Vertices off the path are unchanged. Thus the flipped set really is a matching.
Worked Example: Rerouting to Match Every Vertex
Let \(G=(L\cup R,E)\), where \(L=\{a,b,c\}\), \(R=\{1,2,3\}\), and \(E=\{a1,a2,b1,c2,c3\}\). Start with \(M=\varnothing\). Search vertices in the listed order and stop a search as soon as it finds a free right vertex.
Search 1. The initial queue is \([a,b,c]\). The first vertex removed is \(a\); its first neighbor is \(1\), which is unmatched. The path \(a,1\) is augmenting. Flipping gives \(M=\{a1\}\), of size \(1\).
Search 2. The unmatched left vertices are \(b,c\), so the queue starts as \([b,c]\). From \(b\), the nonmatching edge \(b1\) reaches \(1\), which is matched to \(a\). The search records the predecessor links \(1\leftarrow b\) and \(a\leftarrow 1\). It then removes \(c\) from the queue; the edge \(c2\) reaches the unmatched vertex \(2\). The recovered path is \(c,2\). Flipping gives \(M=\{a1,c2\}\), of size \(2\).
Search 3. The only unmatched left vertex is \(b\). The edge \(b1\) reaches \(1\), and the matching edge \(1a\) reaches \(a\). From \(a\), the nonmatching edge \(a2\) reaches \(2\), which is matched to \(c\). The matching edge \(2c\) reaches \(c\), and the nonmatching edge \(c3\) reaches the unmatched vertex \(3\). The recovered path is \(b,1,a,2,c,3\). Flipping removes \(a1\) and \(c2\), then adds \(b1,a2,c3\), giving \(M=\{b1,a2,c3\}\), of size \(3\).
Check: The three edges \(b1,a2,c3\) have pairwise distinct endpoints and belong to \(E\), so they form a matching. Since \(L\) has three vertices, no matching can have more than three edges. Thus this matching is maximum.
Why Stopping Gives a Maximum Matching
The search itself detects whether an augmenting path exists. To justify the stopping rule, we use the following characterization. The symmetric difference \(M\mathbin{\triangle}N\) of two edge sets consists of edges that belong to exactly one of them.
Proof. If \(M\) has an augmenting path, flipping its edges produces a matching with \(|M|+1\) edges. Therefore \(M\) is not maximum.
For the converse, suppose \(M\) is not maximum. There is a matching \(N\) with \(|N|>|M|\). Consider the graph whose edge set is \(M\mathbin{\triangle}N\). At each vertex, at most one incident edge belongs to \(M\) and at most one belongs to \(N\), so the degree in this graph is at most two. Whenever a vertex has degree two, one incident edge is in \(M\) and the other is in \(N\). Consequently each nonempty connected component is a path or a cycle with edges alternating between \(M\) and \(N\): a finite connected graph of maximum degree two is a path or cycle, and at a degree-two vertex the two edge types differ.
An alternating cycle has the same number of edges from \(M\) and \(N\). An alternating path has either equal numbers, or one more edge from one of the matchings. Since \(|N|>|M|\), at least one component must have one more \(N\)-edge than \(M\)-edge. That component is an alternating path whose first and last edges belong to \(N\). Its endpoints have no incident edge from \(M\): each endpoint has only its one path edge in the symmetric difference, and any \(M\)-edge incident there would either be that edge or add a second edge in the symmetric difference. The path is therefore an augmenting path for \(M\). This proves the converse. \(\square\)
By the search characterization, when a search fails to reach an unmatched vertex of \(R\), no augmenting path exists. The theorem then says that the current matching is maximum. This argument also handles an empty part: there are no edges, \(M=\varnothing\) is maximum, and there is no augmenting path.
Worked Example: A Search That Cannot Reach a Free Right Vertex
Let \(L=\{p,q,r\}\), \(R=\{x,y\}\), and \(E=\{px,qx\}\). Initially the queue is \([p,q,r]\). Removing \(p\) reaches the unmatched vertex \(x\), so the first augmenting path is \(p,x\). The new matching is \(M=\{px\}\).
On the next search the queue is \([q,r]\). Removing \(q\) follows the nonmatching edge \(qx\) to \(x\). Since \(x\) is matched, the search follows its matching edge to \(p\). Removing \(r\) finds no neighbors. Removing \(p\) finds only the already matched edge \(px\), which cannot be followed from \(L\) in the directed search graph. The queue is exhausted without reaching an unmatched right vertex, so the algorithm stops.
Check: The only edges are \(px\) and \(qx\), and both share \(x\). Hence every matching contains at most one edge. The output \(\{px\}\) has one edge and is maximum, in agreement with the stopping rule.
Running Time and Storage
Write \(n=|V(G)|\), \(m=|E(G)|\), and let \(\ell=|L|\), \(r=|R|\). One search takes \(O(n+m)\) time. Each vertex is placed in the queue at most once. When a left vertex is processed, its adjacency list is scanned, and the total number of such scans is at most \(m\). A right vertex has at most one outgoing search edge: its matching edge, if it has one. Processing right vertices therefore takes at most \(O(n)\) additional time. Initializing the queue and search records also takes \(O(n)\) time.
There are at most \(\min(\ell,r)\) augmentations, since each augmentation increases the size of the matching by one, while every matching uses distinct vertices in both parts. The algorithm performs at most one additional unsuccessful search before stopping. Including adjacency-list setup, the total running time is therefore
In particular, this is \(O(n(n+m))\). The matching, adjacency lists, queue, visited marks and predecessor records together require \(O(n+m)\) storage. These bounds apply to this repeated breadth-first-search algorithm; they do not claim that it is the fastest possible algorithm for bipartite matching.
Worked Example: A Disconnected Graph with Isolated Vertices
Let \(L=\{s,t,z\}\), \(R=\{1,2,3\}\), and \(E=\{s1,t2\}\). Vertices \(z\) and \(3\) are isolated. The first search starts with queue \([s,t,z]\). Removing \(s\) reaches free vertex \(1\), so augment along \(s,1\) and obtain \(M=\{s1\}\).
The next search starts with \([t,z]\). Removing \(t\) reaches free vertex \(2\), so augment along \(t,2\) and obtain \(M=\{s1,t2\}\). On the next search, the only unmatched left vertex is \(z\). It has no neighbors, so the queue empties and the algorithm stops. The unmatched right vertex \(3\) does not prevent termination: an augmenting path must connect an unmatched left vertex to an unmatched right vertex.
Check: The output has two edges, and both edges are in \(E\) with distinct endpoints. Because \(E\) contains only two edges, any matching has at most two edges. Thus the output is maximum. Here \(\ell=3\), \(r=3\), \(n=6\), and \(m=2\), so the general bound gives \(O((\min(3,3)+1)(6+2))=O(32)\) as an asymptotic expression’s underlying product. The small graph requires only the three searches described above.
Common Pitfalls
Do not follow every edge in both directions. Search direction depends on membership in the current matching: unmatched edges go from \(L\) to \(R\), and matched edges go from \(R\) to \(L\). Reversing this rule can produce paths that do not alternate correctly, so they need not be augmenting paths.
A failed search is a certificate; one successful search is not the end. The algorithm stops only after an unsuccessful search. A matching that cannot be enlarged by an obvious local change may still have an augmenting path that reroutes several existing matched edges, as in the first example.
Count the final search in the running time. With \(k\) successful augmentations, the algorithm may perform \(k+1\) searches: one successful search per augmentation and a final search that certifies termination. Each is \(O(n+m)\), and \(k\leq\min(\ell,r)\).
Check Your Understanding
For each question, use the search orientation and stopping argument developed above.
- In the directed search graph, which direction is assigned to an edge in the current matching, and which direction to an edge outside it?
- Why does flipping an augmenting path increase the matching size by exactly one?
- For \(L=\{a,b\}\), \(R=\{1,2\}\), and \(E=\{a1,b1\}\), describe what happens after the algorithm finds one edge.
- If the algorithm makes \(k\) augmentations, how many searches may it perform, including the final unsuccessful search?
- Why does an isolated unmatched vertex in \(L\) not by itself imply that the current matching is not maximum?