Hopcroft–Karp algorithm: Difference between revisions

Revision as of 23:01, 5 March 2009

Revision as of 23:38, 5 March 2009

Line 1:

The '''Hopcroft–Karp algorithm''' finds maximum cardinality [[matching]]s in [[bipartite graph]]s in <math>O(\sqrt{V} E''m''&nbsp;&radic;''n'')</math> time, where ''VO'' isinvokes the[[big numberO of vertices andnotation]], ''Em'' is the number of edges ofin the graph.<ref>John E. Hopcroft, Richard M. Karp:and ''An <math>n^{5/2}</math> Algorithm for Maximum Matchings in Bipartite Graphs.'' SIAMis J.the Comput.number 2(4),of 225-231vertices (1973)</ref>of <refthe name=clrs>{{Introduction to Algorithms|2|chapter=26graph.5: The relabel-to-front algorithm|pages=pp. 696–697}}</ref> In the worst case of [[dense graphs,graph]]s i.e.,time whenbound becomes <math>E=O(V^2)''n''</mathsup>, the worst-case time estimate is <math>O(V^{5/2})</mathsup>).

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}}. It increases the size of the matching by a sequence of augmenting paths, a standard technique in matching algorithms, but instead of finding just a single augmenting path, the algorithm finds a maximal set of shortest augmenting paths in each iteration. As a result only O(&radic;''n'') iterations are needed.

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 [[Max-flow min-cut theorem|minimal cut]] associated with the flow is equivalent to the [[König's theorem (graph theory)|minimal vertex cover]] associated with the matching.

==AlternatingAugmenting paths==

Instead of finding just a single augmenting path, the algorithm finds a maximal set of shortest paths in each iteration <ref>{{cite web|author=Norbert Blum|title=A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in Nonbipartite Graphs|url=http://citeseer.ist.psu.edu/258961.html|date=1999}}</ref>. As a result only <math>O(\sqrt{V})</math> iterations are needed.

A vertex that is not the endpoint of an edge in some partial matching ''M'' is called a ''free vertex''. The basic concept that the algorithm relies on is that of an ''alternatingaugmenting path'', a path that starts at ana unmatchedfree vertex, ends at ana unmatchedfree vertex, and alternates between unmatched and matched edges within the path. If ''M'' is a matching of size ''n'', and ''P'' is an alternatingaugmenting path relative to ''M'', then the matching[[symmetric difference]] of the two sets of edges, ''M''&nbsp;⊕&nbsp;''P'', would haveform a sizematching ofwith size ''n''&nbsp;+&nbsp;1. Thus, by finding alternatingaugmenting paths, an algorithm may increase the size of the matching.

Conversely, suppose that a matching ''M'' is not optimal, and let ''P'' be the symmetric difference ''M''&nbsp;⊕&nbsp;''M''* where ''M''* is an optimal matching. Then ''P'' must form a collection of disjoint cycles and alternatingaugmenting paths; the difference in size between ''M'' and ''M''* is the number of paths in ''P''. Thus, if no alternatingaugmenting path can be found, an algorithm may safely terminate, since in this case ''M'' must be optimal.

==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 <math>M'=M\oplus P</math> has all edges of M and P except shared edges <math>M\cap P</math>

An alternatingaugmenting path in a matching problem is closely related to anthe [[augmenting path]],s a patharising in a [[maximum flow]] problemproblems, thatpaths along which one may increasesincrease 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> The Hopcroft–Karp algorithm may therefore be seen as an adaptation of the [[Edmonds-Karp algorithm]] for maximum flow. The same technical can be generalized to problems of maximum flow on unweighted graphs with unit edge capacities, butachieving isa notrunning astime efficientof inO(min(''m''^3/2,&nbsp;''n''^2/3''m'') thatfor generalizationthese asmore itgeneral isproblems.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, forsection bipartite8.2, matchingflows in unit capacity networks, pp. 252–255.</ref>

==Alternating paths==

The basic concept that the algorithm relies on is that of an ''alternating path'', a path that starts at an unmatched vertex, ends at an unmatched vertex, and alternates between unmatched and matched edges within the path. If ''M'' is a matching of size ''n'', and ''P'' is an alternating path relative to ''M'', then the matching ''M''&nbsp;⊕&nbsp;''P'' would have a size of ''n''&nbsp;+&nbsp;1. Thus, by finding alternating paths, an algorithm may increase the size of the matching.

Conversely, suppose that a matching ''M'' is not optimal, and let ''P'' be the symmetric difference ''M''&nbsp;⊕&nbsp;''M''* where ''M''* is an optimal matching. Then ''P'' must form a collection of disjoint cycles and alternating paths; the difference in size between ''M'' and ''M''* is the number of paths in ''P''. Thus, if no alternating path can be found, an algorithm may safely terminate, since in this case ''M'' must be optimal.

An alternating path is closely related to an [[augmenting path]], a path in a [[maximum flow]] problem that increases 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. The Hopcroft–Karp algorithm may be generalized to problems of maximum flow on unweighted graphs, but is not as efficient in that generalization as it is for bipartite matching.

==Algorithm==

Line 37 ⟶ 28:

Since the algorithm performs a total of at most 2&radic;''n'' phases, it takes a total time of O(''m''&nbsp;&radic;''n'').

==Notes==

{{reflist}}

==References==

*{{citation|first1=Ravindra K.|last1=Ahuja|first2=Thomas L.|last2=Magnanti|first3=James B.|last3=Orlin|title=Network Flows: Theory, ALgorithms and Applications|publisher=Prentice-Hall|year=1993}}.

{{reflist}}

*{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''^5/2 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}}.</ref>

[[Category:Graph algorithms]]