Matching Problems Suppose we have a bipartite graph G and seek a set of disjoint pairing of vertices one member of each pair in each part under the condition that paired vertices are adjacent they form an edge in the graph G Among the questions that we can raise about such pairings or matchings in a graph are How large can such a pairing be How can we find a maximum sized matching How many steps does it take to do so Similar problems exist in non bipartite graphs with interesting answers and there are similar problems in which each edge in the graph has a value and we want a matching whose edge value sum is as large as possible And there are somewhat more general commodity flow problems that are closely related to matching problems A bipartite graph is also called a two colorable graph and we will call the two parts of G its Left and Right parts A bipartite graph can be described by a matrix with rows corresponding to the vertices of the Left part and columns to vertices in the Right part This matrix called G s adjacency matrix has a 1 if its row and column form an edge and 0 otherwise If edges have values these values can replace the 1 s in the matrix The vertices adjacent to any vertex v are often called v s neighbors We define the deficiency of a set S of rows by its size less the size of the set of columns that is the union of the neighbors of its elements when it is positive D S S UvinS N v The answer is to our first question is then The size of a maximum matching is the size of L less the maximum deficiency among the subsets of S At first glance this seems like a useless condition because L has a number of subsets that is 2 raised to the power of L s cardinality which can be huge Fortunately there is an easy way to find the maximum deficiency of a subset of L which also provides us with a way to prove this condition First notice that if S vertices have only S D neighbors we cannot possibly supply more than S D matches to elements of S We therefore need only prove that we can actually match all but the maximum deficiency of the vertices in L To prove this we suppose that we have a maximum sized matching and it leaves k unmatched vertices in L We will use a labeling procedure to prove our claim here This same labeling procedure can be used to find a maximum sized matching The labeling procedure consists of starting with the unmatched vertices in L and putting a label or marker on each of their neighbors If any of these neighbors is not matched in our matching we can add the edge consisting of it and its unmatched L neighbor to our matching Doing so is called Augmenting the matching and augmenting increases the size of the matching Since we assume that our matching has maximum size no augmentation can exist which means all the neighbors we find in R must be matched with vertices of L We then label the neighbors of the L vertices paired with of our first set of neighbors and it is still true that if any of these are unmatched we can find an augmentation Thus if unmatched v is a neighbor of w which is matched to x which has an unmatched neighbor y we can unpair w and x and instead pair v with w and x with y which is an augmentation Such augmentations are possible whenever we can find a path from an unpaired L vertex to an unpaired R vertex that alternates between edges out of and in our matching We can continue labeling neighbors of matches of neighbors of matches of unmatched vertices of L and continue in this fashion until all vertices of R that can be reached in this manner are reached Notice that there will be an augmentation unless every one of the reachable vertices in R is matched to a vertex in L Notice how similar this idea is to the switching of two colors in the proof of the five color theorem and the false proof of the four color theorem And so we have found our set S of vertices of L with maximum deficiency It consists of the unmatched vertices in L plus all those vertices in L who are matched to the labeled vertices in R And what is the union of their neighborhoods It consists of the labeled vertices in R The size of this union is the number of labeled vertices in this S which is the cardinality of S less the number of its unmatched vertices The entire number of unmatched vertices of L is therefore the deficiency of S which is what we set out to prove Not only does this argument permit us to find S it allows us to find a maximum size matching starting from nothing We can do so by labeling until we find an augmentation then doing it again and repeating until there are no more augmentations possible The procedure just described is a bit vague because there are lots of ways to label neighbors in a graph That is there are lots of ways to choose the order in which you assign labels to neighbors Among these are depth first search in which having labeled a vertex you would if it is paired in the partial matching you are trying to augment label a neighbor of its partner next In a breadth first search you label all immediate neighbors of unmatched vertices first then those who are three steps away from an unmatched vertex next then five steps away next etc Here breadth first search is most efficient We can show that if we first find a maximal set of 1 step augmentations then a maximal set of 3 step augmentations and so on we can increase the size of the minimum length augmentation by at least 2 using only one labeling procedure The number of labelings each of which could at worst require us to look at all the edges is then at most the number of different sizes of augmentations that we encounter And this number is at most on the order of V1 2 so that the number steps necessary to find a maximum sized matching this way is at most on the order of EV1 2 Why is the number of augmentation lengths at most on the order of V1 2 If you look at the edges that are in a partial matching and not some maximum sized matching and vice versa they have degree 0 1 or 2 at each vertex They therefore consist of a set of cycles and paths in G the maximum matching will be bigger in cardinality than the partial matching by at most the number of those disjoint paths here that have more maximum matching edges than partial matching edges and …