Hopcroft–Karp algorithm

The Hopcroft–Karp algorithm finds maximum cardinality matchings in bipartite graphs in ${\displaystyle O({\sqrt {V}}E)}$ time, where V is the number of vertices and E is the number of edges of the graph.^{[1] [2]} In the worst case of dense graphs, i.e., when ${\displaystyle E=O(V^{2})}$, the worst-case time estimate is ${\displaystyle O(V^{5/2})}$.

The algorithm is an adaptation of the Edmonds-Karp algorithm for maximum flow, since bipartite matching is equivalent to finding the maximum (integer) flow if the vertices in each partition are considered sources (respectively sinks) of capacity 1. The minimal cut associated with the flow is equivalent to the minimal vertex cover associated with the matching.

Instead of finding just a single augmenting path, the algorithm finds a maximal set of shortest paths in each iteration ^[3]. As a result only ${\displaystyle O({\sqrt {V}})}$ iterations are needed.

Definition

Consider a graph G(V,E). The following definitions are relative to a matching M in G.

• An alternating path is a path in which the edges would belong alternatively to M and E-M.
• A free vertex is a vertex which has no incoming edges which belong to M.
• Finally, an augmenting path P is an alternating path such that both its end points are free vertices.
• Symmetric difference ${\displaystyle M'=M\oplus P}$  has all edges of M and P except shared edges ${\displaystyle M\cap P}$ 

Algorithm

The Basic concept that the algorithm relies on is that if we have a matching N of size n, and P is the augmenting path relative to N, then the matching ${\displaystyle N\oplus P}$  would have a size of n+1. Thus, since there would be no matching greater in size than the maximum matching, the maximum matching would not have an augmenting path.

Lets name the two sets in which G can be partitioned as U and V. The matching from U to V at any time is represented as the set M.

The algorithm is run in phases. Each phase consists of:

• A BFS is run from free U vertices. This BFS stops at depth k where a free V vertex is reached. Note that, at the last iteration, the algorithm collects all free V vertices at depth k.
• Find a maximal set of non-overlapping augmenting paths of length k. Achieved by DFS from the free V vertices computed by BFS to free U vertices.

Work-in-progress. The following pseudo code does not describe this algorithm correctly. It has to be rewritten. Even worse, it requires O(n) iterations instead of ${\displaystyle O({\sqrt {n}})}$  as a result its complexity is O(n³) instead of O(n^2.5)

We also maintain a queue(first in first out data-structure) Q in our pseudo code.

Pseudo Code

Initialization:
 
M = null;

for u:U
 for v:V such that (u,v) belongs to E
  if (v is not in M)
     add (u,v) to M;
     break; 
  end if
 end for
end for 
Start;


Start :
  
for all u:U not in M
 if (u.flag_inserted != true)
        insert u in Q;
        u.flag_inserted = true;
        u.previous_node = null; 
 end if
end for
Create_path;

Create_path:

while (Q is not empty)
pop an element q from Q;
if (q.previous_node = null || (q.previous_node,q) is in M )
   for e(q,p): E out of q
     if (e is not in M && p.flag_inserted = false)
       if (p is a free vertex)
             Augmenting_Path(q.previous_node, q , p)
       else 
            add p to Q;
            p.flag_inserted = true;
       end if 
     end if
   end for
 
 else
    for e(q,p): E out of q
     if (e is in M && p.flag_inserted = false)
       add p to Q;
       p.flag_inserted = true;
     end if
   end for
end if
end while
return M
     
Augmenting_Path(q.previous_node, q , p) :
 Re-create the augmenting path ( p -> q -> q.previous_node ->...) using bfs, till the time you hit a free vertex.
 Then alternate by un-matching all the nodes in that path that were matched and matching all the nodes which were 
 originally un-matched. Update M accordingly.
 Empty the queue;
 For each node, mark all the flag_inserted false and previous_node = null;
 Delete the paths;
 Start;

References

1. John E. Hopcroft, Richard M. Karp: An ${\displaystyle n^{5/2}}$  Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4), 225-231 (1973)
2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "26.5: The relabel-to-front algorithm". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. pp. 696–697. ISBN 0-262-03293-7. {{cite book}}: |pages= has extra text (help)
3. Norbert Blum (1999). "A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in Nonbipartite Graphs".