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

Articles, Blog 2 Comments

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.

eNSWEPost authorhow would we algorithmicaly know that there are no more augmenting paths?

Muhammad IzzuddinPost authorIs there any other algorithm that can be used to find maximum matching in bipartite graph and faster than this hopcroft-karp algorithm ?