The Hopcroft-Karp Algorithm – GT – Computability, Complexity, Theory: Algorithms

The Hopcroft-Karp
algorithm goes like this. We first initialize the matching to the
empty set, then we repeat the following. First, we build an alternating
level graph rooted at the unmatched vertices on the left part of the
partition using breadth-first search. Let’s pause for a moment here and
see how this works in an example. The first iteration is trivial, so let’s start with a later iteration
where we have some existing matching marked by the orange edges here
that we’re trying to augment. Level 0 consists of the unmatched
vertices on the left side and to go to the next level,
we follow the unmatched edges. Then we follow matched edges to
get back to the left hand side. And then we follow along unmatched
vertices which lead us to an unmatched vertex on
the right hand side. So that’s a level we can stop at. And we end up with this here for
our total level graph. Having built this level graph, we use
it to augment the current matching with a maximal set of vertex
disjoint shortest augmenting paths. We accomplish this by starting at one
of the unmatched vertices in R and tracing our way back. Let’s say that I used this path here. Well then because I’m looking for a set of vertex disjoint paths, I can
go ahead and delete these vertices. And with these vertices deleted,
I can also go and delete all the other vertices
that got orphaned in the process. And at this point we note that I had
to delete the other unmatched vertex, nr, and
that tells me that I found a maximal set of vertex disjoint
shortest-length paths. Once we’ve applied all these
augmenting paths, we go back and rebuild the level graph, and keeping
doing this until no more augmenting paths exist, and then we can
return the matching that we found.>From the description, it’s clear
that each iteration of this loop, what we’ll call a phase from now
on takes on the order E time, building a level graph is
done by breadth first search. And so that only takes order E time and
the second part can also be thought of as a single
traversal of the graph essentially. As we’re picking a path from one
of the unmatched vertices in R to one of the unmatched in L
we can follow any edge here. We don’t have to be careful at all,
because in effect, all roads lead to
an unmatched vertex in L. The key insight is that only about
the square root of V phases are needed in order for us to get to a point where
there are no more augmenting paths. Overall then,
we seek to prove the theorem stating that given a bipartite graph,
the Hopcroft-Karp algorithm finds a maximum matching in time
order E times the square root of V.

Tags: , , , , ,


Leave a Reply

Your email address will not be published. Required fields are marked *