Hopcroft–Karp algorithm

The algorithm of Hopcroft and Karp ( 1973 by John E. Hopcroft and Richard M. Karp developed ) is used in graph theory for determining a maximum matching in a bipartite graph. It is based on the pairing that contains no edges, and designed to " alternate " paths between nodes still unpaired. Each such path provides a magnification ( " augmentation " ) mating to an edge.

Augmenting paths

Is a graph with edge set of a given pairing, we consider coherent subgraphs that have no circle ( called trees) and which consist of

• ( a) an unpaired node as a root,
• ( b ) paired nodes that can be reached from the root in the tree on alternate paths straight number of edges (alternating means that the edges of the path to belong alternately and not to belong, so these nodes have even distance from the root ) and
• ( c) all the nodes and edges along the path of (b) (this distance and odd node are added from the root ).

A group of such trees, which have no common node, namely forest.

If nodes and from two different trees of the forest, each straight distance from their roots, are connected by the edge, then this edge does not belong to, because the nodes are already paired with each other inside edge of the tree ( it unless it is the root, which is unpaired anyway). The path with edge set from the root of a tree on the root of the other tree is then an alternating path with unpaired start and end points. Such a path is called the path - augmenting, for a pair that includes an edge over.

Conversely, that a pairing that contains more edges, a subgraph with edge set as follows, where all paths between and alternate, and one of which must be no common node at least Paths augmentierend. is exactly then a greatest pairing, if there is no - augmenting path.

Hungarian forests

In the definition of forests considered has not been provided a bipartite graph exists. In a bipartite graph, but is more important: where the nodes are straight distance from their roots in or, depending on where the root is also. If it is then in the forest are no two nodes, and in the last section and the forest no longer in compliance with the properties (a) may be increased to (c), it is called a Hungarian forest. Because of Bipartitheit can then show that the pairing is then exactly a greatest pairing, if there is to her a Hungarian forest.

Algorithm

The following algorithm is a precursor to the algorithm of Hopcroft and Karp. He constructs a bipartite graph with pairing a forest with properties (a ) to ( c ), the

• Either a Hungarian forest is
• Or one - augmenting path provides.

At the beginning of the algorithm is executed with. If it ends in step 3 with a - augmenting path, is replaced and the algorithm performed again. The case that the algorithm in step 2 ends with a Hungarian Forest ( in which case a greatest pairing ) must occur after runs of the algorithm at the latest, because the pairing is enlarged in each case to two nodes in the other case. The running time for one-time implementation of the algorithm is proportional to the number of edges, the total running time on repeated conduct that is proportional to the product of edge and node number.

Example

And is shown on the right in the example. The animated version of this graphic depicts the repeated execution of this algorithm, five times a augmenting path and then a Hungarian forest is determined.

Simultaneous augmentation multiple paths

The total running time of the algorithm can be reduced when multiple - augmenting paths are considered simultaneously. It is the length of the shortest - augmenting path. We consider augmenting - node-disjoint paths of length, where no further - augmenting path of length can add to node-disjoint. Then it can be shown that

The above-mentioned Algorithm can be extended to the algorithm of Hopcroft and Karp that he not only returns an augmenting path, but a lot of augmenting paths being viewed. For this step you need 2 and 3 are performed as a breadth-first search, where the constructed paths will only be extended in the forest when no new paths of previous length to find more. Once a path to a node performs unpaired (ie an augmenting path ), no paths even greater length longer need to be considered.

Is a greatest pairing and so provides the advanced algorithm runs as a pairing with node- and - augmenting paths whose length is at least. Because none of the nodes is included in two of these paths must be, that is the greatest pairing must be achieved within subsequent runs. The total running time of the algorithm of Hopcroft and Karp is therefore proportional to the product of the number of edges and square root of the number of nodes.