Hopcroft–Karp algorithm: Difference between revisions

Revision as of 22:43, 5 March 2009

Revision as of 22:51, 5 March 2009

Line 12:

* Symmetric difference <math>M'=M\oplus P</math> has all edges of M and P except shared edges <math>M\cap P</math>

==Alternating paths==

==Algorithm==

The basic concept that the algorithm relies on is that ifof 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 augmentingalternating path relative to ''M'', then the matching ''M''&nbsp;⊕&nbsp;''P'' would have a size of ''n''&nbsp;+&nbsp;1. Thus, sinceby therefinding wouldalternating bepaths, noan matchingalgorithm greatermay in size thanincrease the maximumsize matching,of the maximum matching would not have an augmenting path.

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.

==Algorithm==

Let ''U'' and ''V'' be the two sets in the bipartition of ''G'', and let the matching from ''U'' to ''V'' at any time be represented as the set ''M''.

The algorithm is run in phases. Each phase consists of the following steps.

* A [[breadth first search]] is run from the free vertices in ''U''. ThisAt searchthe stopsfirst atlevel of the firstsearch, layeronly unmatched edges may be traversed (since ''kU'' whereis onenot oradjacent moreto freeany verticesmatched inedges); ''V''at aresubsequent reached.levels Collectof ''all''the freesearch, verticesrestrict inthe ''V''traversed atedges layerso ''k''that they andalternate putbetween themunmatched inand matched. Terminate the setsearch ''F''.at Thatthe is,first a vertexlayer ''vk'' iswhere putone intoor Fmore iffree andvertices onlyin if''V'' it endsare a shortest augmenting pathreached.

* Collect ''all'' free vertices in ''V'' at layer ''k'' and put them in the set ''F''. That is, a vertex ''v'' is put into F if and only if it ends a shortest augmenting path.

* Find a maximal set of ''vertex disjoint'' augmenting paths of length ''k''. This is set may be computed by [[depth first search]] from ''F'' to the free vertices in ''U'', 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. Once an augmenting path is found that involves one of the vertices in ''F'', the depth first search is continued from the next starting vertex.

* Every one of the paths found in this way is used to enlarge ''M''.