Hopcroft–Karp algorithm: Difference between revisions

Revision as of 08:53, 4 April 2020

Revision as of 09:03, 4 April 2020

Line 1:

{{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 as input a [[bipartite graph]] and produces as output a [[Maximum cardinality matching|maximum cardinality 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, <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 near-linear (in |E|) time{{reference needed}}.

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}} 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 thatof the graph, which alternate between beingedges in the matching and edges out of the partial matching, suchand thatwhere swappingthe whichinitial edgesand offinal edge are not in the partial matching. Finding an augmenting path areallows inus andto whichincrement arethe outsize of the partial matching, producesby asimply largertoggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). HoweverSimpler algorithms for bipartite matching, insteadsuch ofas findingthe just[[Ford–Fulkerson aalgorithm]]‚ singlefind one augmenting path per iteration,: the Hopkroft-Karp algorithm instead finds a maximal set of shortest augmenting paths., Asso aas result,to ensure that only <math>O(\sqrt{|V|})</math> iterations are needed instead of <math>O(V)</math> iterations. The same principleperformance hasof also<math>O(|E|\sqrt{|V|})</math> beencan usedbe achieved to developfind moremaximum complicatedcardinality algorithmsmatchings forin non-bipartitearbitrary matchinggraphs, with the samemore asymptoticcomplicated runningalgorithm timeof asMicali theand Hopcroft–KarpVazirani<ref>{{Cite journal|last=Peterson|first=Paul A.|last2=Loui|first2=Michael C.|date=1988-11-01|title=The general maximum matching algorithm of micali and vazirani|url=https://doi.org/10.1007/BF01762129|journal=Algorithmica|language=en|volume=3|issue=1|pages=511–533|doi=10.1007/BF01762129|issn=1432-0541}}</ref>.

==Augmenting paths==