Hopcroft–Karp algorithm: Difference between revisions

Revision as of 16:23, 28 October 2023

Latest revision as of 14:52, 14 May 2025

(9 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Algorithm for maximum cardinality matching}}

{{Infobox algorithm|image = |data = [[Graph (data structure)|Graph]]|time = <math>O(E \sqrt V)</math>|class = Graph algorithm|space = <math>O(V)</math>}}
In [[computer science]], the '''Hopcroft–Karp algorithm''' (sometimes more accurately called the '''Hopcroft–Karp–Karzanov algorithm''')<ref>{{harvtxt|Gabow|2017}}; {{harvtxt|Annamalai|2018}}</ref> is an [[algorithm]] that takes a [[bipartite graph]] as input and produces a [[maximum-cardinality matching]] as output — 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]], where <math>E</math> is set of edges in the graph, <math>V</math> is set of vertices of the graph, and it is assumed that <math>|E|=\Omega(|V|)</math>. In the case of [[dense graph]]s the time bound becomes <math>O(|V|^{2.5})</math>, and for sparse [[random graph]]s it runs in time <math>O(|E|\log |V|)</math> with high probability.{{sfnp|Bast|Mehlhorn|Schäfer|Tamaki|2006}}

The algorithm was discovered by {{harvs|first1=John|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard|last2=Karp|author2-link=Richard Karp|txt|year=1973}} and independently by {{harvs|first=Alexander|last=Karzanov|authorlink=Alexander V. Karzanov|year=1973|txt}}.{{sfnp|Dinitz|2006}} 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''. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the [[Ford–Fulkerson algorithm]]‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only <math>O(\sqrt{|V|})</math> iterations are needed instead of <math>O(|V|)</math> iterations. The same performance of <math>O(|E|\sqrt{|V|})</math> can be achieved to find maximum-cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani.{{sfnp|Peterson|Loui|1988}}

Line 69 ⟶ 70:

Dist[NIL] := ∞

'''while''' Empty(Q) = false '''do'''

u := Dequeue(LMQ)

'''if''' Dist[u] < Dist[NIL] '''then'''

'''for each''' v '''in''' Adj[u] '''do'''

Line 105 ⟶ 106:

=== Explanation ===

Let the vertices of our graph be partitioned in <code>U</code> and <code>V</code>, and consider a partial matching, as indicated by the <code>Pair_U</code> and <code>Pair_V</code> tables that contain the one vertex to which each vertex of <code>U</code> and of <code>V</code> is matched, or <code>NIL</code> for unmatched vertices. The key idea is to add two dummy vertices on each side of the graph: uDummy connected to all unmatched vertices in <code>U</code> and vDummy connected to all unmatched vertices in <code>V</code>. Now, if we run a [[breadth-first search]] (BFS) from uDummy to vDummy then we can get the paths of minimal length that connect currently unmatched vertices in <code>U</code> to currently unmatched vertices in <code>V</code>. Note that, as the graph is bipartite, these paths always alternate between vertices in <code>U</code> and vertices in <code>V</code>, and we require in our BFS that when going from <code>V</code> to <code>U</code>, we always select a matched edge. If we reach an unmatched vertex of <code>V</code>, then we end at vDummy and the search for paths in the BFS terminate. To summarize, the BFS starts at unmatched vertices in <code>U</code>, goes to all their neighbors in <code>V</code>, if all are matched then it goes back to the vertices in <code>U</code> to which all these vertices are matched (and which were not visited before), then it goes to all the neighbors of these vertices, etc., until one of the vertices reached in <code>V</code> is unmatched.

Observe in particular that BFS marks the unmatched nodes of <code>U</code> with distance 0, then increments the distance every time it comes back to <code>U</code>. This guarantees that the paths considered in the BFS are of minimal length to connect unmatched vertices of <code>U</code> to unmatched vertices of <code>V</code> while always going back from <code>V</code> to <code>U</code> on edges that are currently part of the matching. In particular, the special <code>NIL</code> vertex, which corresponds to vDummy, then gets assigned a finite distance, so the BFS function returns true iff some path has been found. If no path has been found, then there are no augmenting paths left and the matching is maximal.

If BFS returns true, then we can go ahead and update the pairing for vertices on the minimal-length paths found from <code>U</code> to <code>V</code>: we do so using a [[depth-first search]] (DFS). Note that each vertex in <code>V</code> on such a path, except for the last one, is currently matched. So we can explore with the DFS, making sure that the paths that we follow correspond to the distances computed in the BFS. We update along every such path by removing from the matching all edges of the path that are currently in the matching, and adding to the matching all edges of the path that are currently not in the matching: as this is an augmenting path (the first and last edges of the path were not part of the matching, and the path alternated between matched and unmatched edges), then this increases the number of edges in the matching. This is same as replacing the current matching by the symmetric difference between the current matching and the entire path..

Note that the code ensures that all augmenting paths that we consider are vertex disjoint. Indeed, after doing the symmetric difference for a path, none of its vertices could be considered again in the DFS, just because the <code>Dist[Pair_V[v]]</code> will not be equal to <code>Dist[u] + 1</code> (it would be exactly <code>Dist[u]</code>).

Also observe that the DFS does not visit the same vertex multiple times. This is thanks to the following lines:

Dist[u] = ∞

return false

When we were not able to find any shortest augmenting path from a vertex <code>u</code>, then the DFS marks vertex <code>u</code> by setting <code>Dist[u]</code> to infinity, so that these vertices are not visited again.

One last observation is that we actually don't need uDummy: its role is simply to put all unmatched vertices of <code>U</code> in the queue when we start the BFS. As for vDummy, it is denoted as <code>NIL</code> in the pseudocode above.

== See also ==

Line 146 ⟶ 147:

| volume = 39

| year = 2006| s2cid = 9321036

| citeseerx = 10.1.1.395.6643

}}

*{{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|last=Dinitz|first=Yefim|editor1-last=Goldreich|editor1-first=Oded|editor1-link=Oded Goldreich |editor2-last=Rosenberg|editor2-first=Arnold L.|editor2-link=Arnold L. Rosenberg|editor3-last=Selman |editor3-first=Alan L. |editor3-link=Alan Selman|contribution=Dinitz' Algorithm: The Original Version and Even's Version|url=https://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf|doi=10.1007/11685654_10|___location=Berlin and Heidelberg|pages=218–240|publisher=Springer |series=Lecture Notes in Computer Science |title=Theoretical Computer Science: Essays in Memory of Shimon Even|volume=3895|year=2006|isbn=978-3-540-32880-3 }}.

*{{citation |doi=10.4153/CJM-1965-045-4 |last=Edmonds |first=Jack |author-link=Jack Edmonds |journal=Canadian Journal of Mathematics |pages=449–467 |title=Paths, Trees and Flowers |volume=17 |year=1965 |mr=0177907|s2cid=18909734 |doi-access=free }}.

*{{citation|last=Gabow|first=Harold N.|author-link=Harold N. Gabow|doi=10.3233/FI-2017-1555|issue=1–4|journal=Fundamenta Informaticae|mr=3690573|pages=109–130|title=The weighted matching approach to maximum cardinality matching|volume=154|year=2017|arxiv=1703.03998|s2cid=386509}}

*{{citation|first1=Harold N.|last1=Gabow|author1-link=Harold N. 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|s2cid=18350108|doi-access=free}}.