View source for Cantic cubic honeycomb

In [[computer science]], the '''Hopcroft–Karp algorithm''' is an [[algorithm]] that takes as input a [[bipartite graph]] and produces as output a maximum [[cardinality]] [[Matching (graph theory)|matching]] – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in <math>O(|E|\sqrt{|V|})</math> time in the [[worst case analysis|worst case]], where <math>E</math> is set of edges in the graph, and <math>V</math> is set of vertices of the graph. In the case of [[dense graph]]s the time bound becomes <math>O(|V|^{2.5})</math>, and for [[random graph]]s it runs in near-linear time.

The algorithm was found by {{harvs|first1=John|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard|last2=Karp|author2-link=Richard Karp|txt|year=1973}}. As in previous methods for matching such as the [[Hungarian algorithm]] and the work of {{harvtxt|Edmonds|1965}}, the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. However, instead of finding just a single augmenting path per iteration, the algorithm finds a maximal set of shortest augmenting paths. As a result only <math>O(\sqrt{n})</math> iterations are needed. The same principle has also been used to develop more complicated algorithms for non-bipartite matching with the same asymptotic running time as the Hopcroft–Karp algorithm.

==Augmenting paths==
A vertex that is not the endpoint of an edge in some partial matching <math>M</math> is called a ''free vertex''. The basic concept that the algorithm relies on is that of an ''augmenting path'', a path that starts at a free vertex, ends at a free vertex, and alternates between unmatched and matched edges within the path. If <math>M</math> is a matching, and <math>P</math> is an augmenting path relative to <math>M</math>, then the [[symmetric difference]] of the two sets of edges, <math>M \oplus P</math>, would form a matching with size <math>|M| + 1</math>. Thus, by finding augmenting paths, an algorithm may increase the size of the matching.

Conversely, suppose that a matching <math>M</math> is not optimal, and let <math>P</math> be the symmetric difference <math>M \oplus M^*</math> where <math>M^*</math> is an optimal matching. Then <math>P</math> must form a collection of disjoint augmenting paths and cycles or paths in which matched and unmatched edges are of equal number; the difference in size between <math>M</math> and <math>M^*</math> is the number of augmenting paths in <math>P</math>. Thus, if no augmenting path can be found, an algorithm may safely terminate, since in this case <math>M</math> must be optimal.

An augmenting path in a matching problem is closely related to the [[augmenting path]]s arising in [[maximum flow problem]]s, paths along which one may increase the amount of flow between the terminals of the flow. It is possible to transform the bipartite matching problem into a maximum flow instance, such that the alternating paths of the matching problem become augmenting paths of the flow problem.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, section 12.3, bipartite cardinality matching problem, pp. 469–470.</ref> In fact, a generalization of the technique used in Hopcroft–Karp algorithm to arbitrary flow networks is known as [[Dinic's algorithm]].

: '''Input''': Bipartite graph <math>G(U \cup V, E)</math>
: '''Output''': Matching <math>M \subseteq E</math>
: <math>M \leftarrow \empty</math>
: '''repeat'''
:: <math>\mathcal P \leftarrow \{P_1, P_2, \dots, P_k\}</math> ''maximal set of vertex-disjoint shortest augmenting paths''
:: <math>M \leftarrow M \oplus (P_1 \cup P_2 \cup \dots \cup P_k)</math>
: '''until''' <math>\mathcal P = \empty</math>

==Algorithm==
Let <math>U</math> and <math>V</math> be the two sets in the bipartition of <math>G</math>, and let the matching from <math>U</math> to <math>V</math> at any time be represented as the set <math>M</math>.

The algorithm is run in phases. Each phase consists of the following steps.
* A [[breadth-first search]] partitions the vertices of the graph into layers. The free vertices in <math>U</math> are used as the starting vertices of this search, and form the first layer of the partition. At the first level of the search, only unmatched edges may be traversed (since the free vertices in <math>U</math> are by definition not adjacent to any matched edges); at subsequent levels of the search, the traversed edges are required to alternate between matched and unmatched. That is, when searching for successors from a vertex in <math>U</math>, only unmatched edges may be traversed, while from a vertex in <math>V</math> only matched edges may be traversed.  The search terminates at the first layer <math>k</math> where one or more free vertices in <math>V</math> are reached.
* All free vertices in <math>V</math> at layer <math>k</math> are collected into a set <math>F</math>. That is, a vertex <math>v</math> is put into <math>F</math> if and only if it ends a shortest augmenting path.
* The algorithm finds a maximal set of ''vertex disjoint'' augmenting paths of length <math>k</math>. This set may be computed by [[depth first search]] from <math>F</math> to the free vertices in <math>U</math>, using the breadth first layering to guide the search: the depth first search is only allowed to follow edges that lead to an unused vertex in the previous layer, and paths in the depth first search tree must alternate between matched and unmatched edges. Once an augmenting path is found that involves one of the vertices in <math>F</math>, the depth first search is continued from the next starting vertex.
* Every one of the paths found in this way is used to enlarge <math>M</math>.

The algorithm terminates when no more augmenting paths are found in the breadth first search part of one of the phases.

==Analysis==
Each phase consists of a single breadth first search and a single depth first search. Thus, a single phase may be implemented in linear time.
Therefore, the first <math>\sqrt{|V|}</math> phases, in a graph with <math>|V|</math> vertices and <math>|E|</math> edges, take time <math>O(|E|\sqrt{|V|})</math>.

It can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial <math>\sqrt{|V|}</math> phases of the algorithm are complete, the shortest remaining augmenting path has at least <math>\sqrt{|V|}</math> edges in it. However, the [[symmetric difference]] of the eventual optimal matching and of the partial matching ''M'' found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least <math>\sqrt{|V|}</math>, there can be at most <math>\sqrt{|V|}</math> paths in the collection, and the size of the optimal matching can differ from the size of <math>M</math> by at most <math>\sqrt{|V|}</math> edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most <math>\sqrt{|V|}</math> additional phases before the algorithm terminates.

Since the algorithm performs a total of at most <math>2\sqrt{|V|}</math> phases, it takes a total time of <math>O(|E|\sqrt{|V|})</math> in the worst case.

In many instances, however, the time taken by the algorithm may be even faster than this worst case analysis indicates. For instance, in the [[average case analysis|average case]] for [[sparse graph|sparse]] bipartite [[random graph]]s, {{harvtxt|Bast|Mehlhorn|Schafer|Tamaki|2006}} (improving a previous result of {{harvnb|Motwani|1994}}) showed that with high probability all non-optimal matchings have augmenting paths of [[logarithm]]ic length. As a consequence, for these graphs, the Hopcroft–Karp algorithm takes <math>O(\log |V|)</math> phases and <math>O(|E| \log |V|)</math> total time.

==Comparison with other bipartite matching algorithms==
For [[sparse graph]]s, the Hopcroft–Karp algorithm continues to have the best known worst-case performance, but for dense graphs a more recent algorithm by {{harvtxt|Alt|Blum|Mehlhorn|Paul|1991}} achieves a slightly better time bound, <math>O\left(n^{1.5}\sqrt{\frac{m}{\log n}}\right)</math>. Their algorithm is based on using a [[push-relabel maximum flow algorithm]] and then, when the matching created by this algorithm becomes close to optimum, switching to the Hopcroft–Karp method.

Several authors have performed experimental comparisons of bipartite matching algorithms. Their results in general tend to show that the Hopcroft–Karp method is not as good in practice as it is in theory: it is outperformed both by simpler breadth-first and depth-first strategies for finding augmenting paths, and by push-relabel techniques.<ref>{{harvtxt|Chang|McCormick|1990}}; {{harvtxt|Darby-Dowman|1980}}; {{harvtxt|Setubal|1993}}; {{harvtxt|Setubal|1996}}.</ref>

==Non-bipartite graphs==
The same idea of finding a maximal set of shortest augmenting paths works also for finding maximum cardinality matchings in non-bipartite graphs, and for the same reasons the algorithms based on this idea take <math>O(\sqrt{|V|})</math> phases. However, for non-bipartite graphs, the task of finding the augmenting paths within each phase is more difficult. Building on the work of several slower predecessors, {{harvtxt|Micali|Vazirani|1980}} showed how to implement a phase in linear time, resulting in a non-bipartite matching algorithm with the same time bound as the Hopcroft–Karp algorithm for bipartite graphs. The Micali–Vazirani technique is complex, and its authors did not provide full proofs of their results; subsequently,
a "clear exposition" was published by {{harvtxt|Peterson|Loui|1988}} and alternative methods were  described by other authors.<ref>{{harvtxt|Gabow|Tarjan|1989}} and {{harvtxt|Blum|2001}}.</ref> In 2012, Vazirani offerred a new simplified proof of the Micali-Vazirani algorithm.<ref>{{harvtxt|Vazirani|2012}}</ref>

==Pseudocode==
 /*
  G = G1 ∪ G2 ∪ {NIL}
  where G1 and G2 are partition of graph and NIL is a special null vertex
 */
   
 function BFS ()
     for v in G1
         if Pair_G1[v] == NIL
             Dist[v] = 0
             Enqueue(Q,v)
         else
             Dist[v] = ∞
     Dist[NIL] = ∞
     while Empty(Q) == false
         v = Dequeue(Q)
         if Dist[v] < Dist[NIL] 
             for each u in Adj[v]
                 if Dist[ Pair_G2[u] ] == ∞
                     Dist[ Pair_G2[u] ] = Dist[v] + 1
                     Enqueue(Q,Pair_G2[u])
     return Dist[NIL] != ∞
 
 function DFS (v)
     if v != NIL
         for each u in Adj[v]
             if Dist[ Pair_G2[u] ] == Dist[v] + 1
                 if DFS(Pair_G2[u]) == true
                     Pair_G2[u] = v
                     Pair_G1[v] = u
                     return true
         Dist[v] = ∞
         return false
     return true
 
 function Hopcroft-Karp
     for each v in G
         Pair_G1[v] = NIL
         Pair_G2[v] = NIL
     matching = 0
     while BFS() == true
         for each v in G1
             if Pair_G1[v] == NIL
                 if DFS(v) == true
                     matching = matching + 1
     return matching

==Notes==
{{reflist}}

==References==
*{{citation|first1=Ravindra K.|last1=Ahuja|author1-link=Ravindra K. Ahuja|first2=Thomas L.|last2=Magnanti|author2-link=Thomas L. Magnanti|first3=James B.|last3=Orlin|author3-link=James B. Orlin|title=Network Flows: Theory, Algorithms and Applications|publisher=Prentice-Hall|year=1993}}.
*{{citation|first1=H.|last1=Alt|first2=N.|last2=Blum|first3=K.|last3=Mehlhorn|author3-link=Kurt Mehlhorn|first4=M.|last4=Paul|title=Computing a maximum cardinality matching in a bipartite graph in time <math>\scriptstyle O\left(n^{1.5}\sqrt{\frac{m}{\log n}}\right)</math>|journal=Information Processing Letters|volume=37|issue=4|pages=237–240|year=1991|doi=10.1016/0020-0190(91)90195-N}}.
*{{citation|first1=Holger|last1=Bast|first2=Kurt|last2=Mehlhorn|author2-link=Kurt Mehlhorn|first3=Guido|last3=Schafer|first4=Hisao|last4=Tamaki|year=2006|title= Matching algorithms are fast in sparse random graphs|journal=Theory of Computing Systems|pages=3–14|volume=39|issue=1|doi=10.1007/s00224-005-1254-y}}.
*{{citation|first=Norbert|last=Blum|title=A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs|year=2001|publisher=Tech. Rep. 85232-CS, Computer Science Department, Univ. of Bonn|url=http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85232-CS.ps.gz}}.
*{{citation|first1=S. Frank|last1=Chang|first2=S. Thomas|last2=McCormick|title=A faster implementation of a bipartite cardinality matching algorithm|publisher=Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia|year=1990}}. As cited by {{harvtxt|Setubal|1996}}.
*{{citation|first=Kenneth|last=Darby-Dowman|title=The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms|publisher=Ph.D. thesis, Brunel University|year=1980}}. As cited by {{harvtxt|Setubal|1996}}.
*{{citation | doi = 10.4153/CJM-1965-045-4 | last = Edmonds | first = Jack | author-link = Jack Edmonds | journal = Canadian J. Math | pages = 449–467 | title = Paths, Trees and Flowers | volume = 17 | year = 1965 | mr = 0177907}}.
*{{citation|first1=Harold N.|last1=Gabow|first2=Robert E.|last2=Tarjan|author2-link=Robert Tarjan|title=Faster scaling algorithms for general graph matching problems|journal=Journal of the ACM|volume=38|issue=4|year=1991|pages=815–853|doi=10.1145/115234.115366}}.
*{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.
*{{citation | last1 = Micali | first1 = S. | author1-link = Silvio Micali | last2 = Vazirani | first2 = V. V. | author2-link = Vijay Vazirani | contribution = An <math>\scriptstyle O(\sqrt{|V|}\cdot|E|)</math> algorithm for finding maximum matching in general graphs | doi = 10.1109/SFCS.1980.12 | pages = 17–27 | title = [[Symposium on Foundations of Computer Science|Proc. 21st IEEE Symp. Foundations of Computer Science]] | year = 1980}}.
*{{citation | last1 = Peterson | first1 = Paul A. | last2 = Loui | first2 = Michael C. | title= The general maximum matching algorithm of Micali and Vazirani | doi = 10.1007/BF01762129 | pages = 511–533 | journal= [[Algorithmica]] | year = 1980 | volume=3|issue=1-4}}.
*{{citation|first=Rajeev|last=Motwani|authorlink=Rajeev Motwani|title=Average-case analysis of algorithms for matchings and related problems|year=1994|journal=Journal of the ACM|volume=41|issue=6|pages=1329–1356|doi=10.1145/195613.195663}}.
*{{citation|last=Setubal|first=João C.|contribution=New experimental results for bipartite matching|title=Proc. Netflow93|publisher=Dept. of Informatics, Univ. of Pisa|pages=211–216|year=1993}}. As cited by {{harvtxt|Setubal|1996}}.
*{{citation|last=Setubal|first=João C.|title=Sequential and parallel experimental results with bipartite matching algorithms|publisher=Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas|year=1996|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3539}}.
*{{citation|last=Vazirani|first=Vijay|title=An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm|publisher= CoRR abs/1210.4594|year=2012|url=http://arxiv.org/abs/1210.4594}}.

{{DEFAULTSORT:Hopcroft-Karp algorithm}}
[[Category:Graph algorithms]]
[[Category:Matching]]