Hopcroft–Karp Algorithm

The Hopcroft-Karp algorithm is an algorithm that takes a bipartite graph \(G(E,V)\) and outputs a maximum matching, \(M\). It runs in worst-case \(O\big(|E| \sqrt{|V|}\big)\) time.

The Hopcroft-Karp algorithm uses similar techniques as the Hungarian algorithm and Edmonds’ blossom algorithm. Like those algorithms, Hopcroft-Karp repeatedly increases the size of a partial matching by determining augmenting paths. However, Hopcroft-Karp improves upon these other algorithms by finding a maximal set of shortest augmenting paths per iteration, and increases the augmenting path by the maximum flow rather than one by one.

In practice, researchers have found that Hopcroft-Karp is not as good as the theory suggests—it is often outperformed by breadth-first and depth-first approaches to finding augmenting paths.^[1]

Unlike a simple matching algorithm, like the Hungarian maximum matching algorithm that finds a single augmenting path per iteration, the Hopcroft-Karp algorithm finds a maximal set of shortest augmenting paths during each round. Because of this, only \( O\big(\sqrt n\big)\) iterations of the algorithm are needed.

Pseudocode

Define two sets of vertices from the bipartition of \(G\), \(U\) and \(V\), with an equal number of nodes. The matchings, or set of edges, between nodes in \(U\) and nodes in \(V\) is called \(M\).

A simple bipartite graph^[2]

The algorithm runs in phases made up of the following steps.^[3]

• Use a breadth-first search to find augmenting paths. It partitions the vertices of the graph into layers of matching and not matching edges. For the search, start with the free nodes in \(U\). This forms the first layer of the partitioning. The search finishes at the first layer \(k\) where one or more free nodes in \(V\) are reached.
• The free nodes in \(V\) are added to a set called \(F\). This means that any node added to \(F\) will be the ending node of an augmenting path—and a shortest augmenting path at that since the breadth-first search finds shortest paths.^[4]
• Once an augmenting path is found, a depth-first search is used to add augmenting paths to current matching \(M\). At any given layer, the depth-first search will follow edges that lead to an unused node from the previous layer. Paths in the depth-first search tree must be alternating paths (switching between matched and unmatched edges). Once the algorithm finds an augmenting path that uses a node from \(F\), the depth-first search moves on to the next starting vertex.

The algorithm terminates when the algorithm can find no more augmenting paths in the breadth-first search step.

This problem attempts to match numbers to letters so as to maximize the amount of matches. This will require two basic steps, which are iterated until the algorithm finds a perfect matching:

1. Build an alternating level graph rooted at unmatched vertices in L using BFS.
2. Augment M with a maximal set of vertex-disjoint shortest-length paths using DFS.

Observe the graph with edges but no assigned matchings.

The original graph without any assigned matchings

Perform BFS starting at all the numeric vertices without a match. Pick any unmatched leaf and go all the way back to a root using DFS. Match the leaf to the root.

Match a to 1

Delete all the instances of 1 and a found in the trees.

Repeat the process to find the next matching. Match b to 2 and delete b from the tree spanning from 3.

In this iteration, 1 is matched to a, 2 is matched to b, and 3, along with c, is left without a match.

Since 3 is left without a match, perform BFS starting from 3 in order to find a matching, or assert that the current matching is already optimal.

The yellow edges represent previously found matchings and the blue edges represent unmatched edges.

Perform DFS once again from the unmatched leaf all the way to the root.

DFS finds a path from c to 1, to a, and terminates at 3.

Augment the path by switching the edges that are matched with those that are unmatched.

Now 1 is matched with c and 3 is matched with a.

This produces the maximal matching between numbers and letters in the graph.

Maximal matching and termination of algorithm

Another way to terminate the algorithm occurs when the path augmentation step does not produce more matchings. In that case, a maximal matching has been found even though not all vertices are matched.^[5]

Each iteration of the Hopcroft-Karp algorithm executes breadth-first search and depth-first search once. This takes \(O(E)\) time. Since each iteration of the algorithm finds the maximal set of shortest augmenting paths by eliminating a path from a root to an unmatched edge, there are at most \(O\big(\sqrt V\big)\) iterations needed.

For dense graphs, the running time is \(O\big(|V|^{2.5}\big)\) and for random graphs, the running time is \(O\big(|V|\big)\). For sparse graphs, it runs in worst-case \(O\big(|E| \sqrt{|V|}\big)\) time.^[6]

• Matching Algorithms
• Tree Traversals
• Hungarian Matching
• Blossom Algorithm

1. , . Hopcroft–Karp algorithm. Retrieved June 19, 2016, from https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
2. , M. Simple-bipartite-graph.svg. Retrieved June 18, 2016, from https://en.wikipedia.org/wiki/File:Simple-bipartite-graph.svg
3. Gupta, R. Hopcroft–Karp Algorithm for Maximum Matching . Retrieved from http://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-2-implementation/
4. , . Hopcroft–Karp algorithm. Retrieved June 29, 2016, from https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
5. Chauhan, D. hopcroft-karp algorithm. Retrieved from https://www.youtube.com/watch?v=pJHdqbxvZOI
6. , . Hopcroft–Karp algorithm. Retrieved June 30, 2016, from https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm