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 layer k where one or more free V vertices are reached. Collect all free V vertices at layer k and put them in the set F. A vertex v is put in F iff ${\displaystyle v\in V}$  and v ends a shortest augmenting path.
• Find a maximal set of vertex disjoint augmenting paths of length k. This is set is computed by DFS from F (computed by BFS) to free U vertices. Every one of this paths is used to enlarge M.

Pseudo Code

for all ${\displaystyle q\in U\cup V}$ 
  q.matching= null;
end for
while (true)
  // Find all potential beginnings of shortest augmenting paths
  B := empty;
  for all u:U s.t. (u.matching = null)
       insert u in B;
  end for
  
  // Find all endings of shortest augmenting paths
  F := Find_Augmenting_Path_Endings(B);
  if (F is empty)
    M:= empty;
    for all u:U s.t. (u.matching ≠ null)
      insert (u, u.matching) in M; // insert edge
    end for
    return M;
  end if
  Augment_Paths(F);
end while

// Perform BFS starting with vertices of B.
// Return: a list of free vertices which potentially 
//         end the shortest vertex-disjoint augmenting paths.
// Side effect: For any vertex v.layer has the index of
//              the BFS layer to reach this vertex (or -1)
// B: potential beginning of augmenting paths
Find_Augmenting_Path_Endings(B):
 
Q := B;
// F: The set of free endings (the other side of augmenting paths)
F := empty;
for all ${\displaystyle q\in U\cup V}$ 
  q.layer:=-1;
end for
// The potential beginnings of augmenting paths are at layer 0.
for all b:B
  b.layer:=0;
end for

while (Q is not empty)
   Q' := empty;
   for all q: Q
     for all (q,p):E s.t. (p.layer = -1)
       p.layer:= q.layer+1;
       if (p.matching = null)
         insert p in F; // Collect the free vertex, continue BFS
       else
         insert p in Q';
       end if
     end for
   end for
   if (F is not empty)
      return F; // Free vertices found, stop at this layer.
   end if
   Q:= empty;
   for all q:Q'
     // By construction, q matched.
     p:= q.matching;
     p.layer:= q.layer+1;
     insert p in Q;
   end for
end while
return empty;

Augment_Paths(F): 
  for all ${\displaystyle q\in U\cup V}$ 
    q.visited= false;
  end for
  for all q:F
    P:=Get_Augmenting_Path(q);
    // Make sure q ends a vertex-disjoint augmenting path
    if (P is not empty) 
      // Perform ${\displaystyle M:=M\oplus P}$ 
      for all (t,u):P
        // Make (t,u) match all edges starting from the last layer
        t.matching := u;
        u.matching := t;
      end for
    end if
  end for

// DFS from p, avoiding previously visited vertices.
// Start at the last layer of BFS, and go backwards
// to layer 0. 
// Return: List of edges on augmenting path. Returns only edges from
// even to odd layers.
// p: Vertex at the end of a non-matching edge (an odd layer)
Get_Augmenting_Path(p):
  if (p.visited OR p.layer = 0)
     return empty;
  end if
  p.visited:= true;
  // Consider only edges going one layer backwards.
  for all (q,p):E s.t. (p.layer-1=q.layer AND NOT q.matching.visited)
    // q is at an even layer
    if (q.layer = 0)
      // q is free vertex on the first layer
      return ((q, p));
    end if
    // Note that q.matching must be defined, and point to 
    // the previous layer. This is due to BFS traversal order.
    P= Get_Augmenting_Path(q.matching);
    if (P not empty)
      // Append (q, p) to the path found so far.
      return (P, (q, p)); 
    end if
  end for
  // Could not find a vertex-disjoint augmenting path ending with p.
  return empty;

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".