We start the search for a deeper understanding,

with the idea of the augmenting path. Recall that in our original

treatment of the max flow problem, we were given a flow over some graph,

and we defined the residual network, which captured the ways in which we

were allowed to modify this flow. This included adding backwards edges

that went in the opposite direction from edges in the original. Augmenting paths then were paths

over this residual network that went from the source to the sync,

and augmented the flow. In a network that arises from

a bipartite matching problem, there are few special phenomena

that are worth noting. First observe that all intermediate

flows found by Ford-Fulkerson correspond to matchings as well. If there is flow across an internal

edge, then it belongs in the matching. Also because flows along

edges are either zero or one there are no anti-parallel

edges in the residual network. That is to say either

the original edge is there or the reverse edge is there, never both. Moreover the matched edges are the ones

that have their edges reversed. Also, only unmatched vertices have

an edge from the source to them, or from them to the sync. Matched vertices have

their edges reversed. The result of all this is that

any augmenting path must start at an unmatched vertex, and

then follow an unmatched edge, followed by a matched edge,

followed by an unmatched edge, until eventually it reaches an unmatched

vertex on the right hand side, and then it can follow

that edge to the sync. This realization allows us to strip away

much of the complexity of flow networks and define an augmenting path for bipartite matching in

more natural terms. We start by defining the more general

concept of an alternating path. Given a matching M, an alternating path is a path where the

edges are alternately in M and not in M. And an augmenting path is

an alternating path where the first and the last vertex are unmatched. For example, in this graph here,

going from this unmatched vertex in L to this matched vertex in R back

to this matched one in L and then to this unmatched one in R

constitutes and augmenting path. We use it to augment the matching

by making the unmatched edges matched and the matched edges unmatched. Like so. This always increases the size of

the matching because before we flipped, there was one more unmatched edge

than matched edge in the path. So when we reversed the matched and unmatched edges, we increased

the size of the matching by one. In fact, we can restate the Ford-Fulkerson

method purely in these terms. We initialize the matching

to the empty set, and then while there’s an augmenting path, we

update the matching to be the symmetric difference between the current

matching and the path that we found. The symmetric difference

includes an element if it’s in exactly one of these sets,

or alternatively, you can think about it as the union of the two sets

minus the things that are in both. The things that are in both here

correspond to matched edges in the path. And remember that we flipped

them to being unmatched. And finally, once there are no more augmenting paths,

we simply return the matching.