Hopcroft-Karp: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 42: Line 42:
The invariant is obviously maintained. To prove the variant, consider an execution of step 3.2. Let <math>p</math> denote the path along which the augmentation takes place. Let <math>p'</math> and <math>p''</math> the paths in he arborescences from the start nodes to <math>v</math> and <math>w</math>, respectively.
The invariant is obviously maintained. To prove the variant, consider an execution of step 3.2. Let <math>p</math> denote the path along which the augmentation takes place. Let <math>p'</math> and <math>p''</math> the paths in he arborescences from the start nodes to <math>v</math> and <math>w</math>, respectively.


For a contradiction, suppose augmenting along <math>p</math> has created a a new augmenting path <math>q</math> that is ''not'' longer than <math>p</math>. In either orientation of <math>p</math> and <math>q</math>, let <math>v'</math> be the first node of <math>p</math> that also belongs to <math>q</math>, and let <math>w'</math> be the last node of <math>p</math> that also belongs to <math>q</math>. Without loss of generality, let <math>v</math> be the last node of <math>p'</math> and let <math>v</math> be on <math>p'</math>. Note that each edge of <math>q</math> that is incident to exactly one node on <math>p</math> must be unmatched.
For a contradiction, suppose augmenting along <math>p</math> has created a new augmenting path <math>q</math> that is ''not'' longer than <math>p</math>. In either orientation of <math>p</math> and <math>q</math>, let <math>v'</math> be the first node of <math>p</math> that also belongs to <math>q</math>, and let <math>w'</math> be the last node of <math>p</math> that also belongs to <math>q</math>. Without loss of generality, let <math>v</math> be the last node of <math>p'</math> and let <math>v</math> be on <math>p'</math>. Note that each edge of <math>q</math> that is incident to exactly one node on <math>p</math> must be unmatched.


First, <math>v'=v</math> must hold because, otherwise, one subpath of <math>p</math> up to <math>v'</math> and one of <math>q</math> up to <math>v'</math> would be a shorter augmenting path, which contradicts the induction hypothesis. Moreover, <math>v'=v</math> implies that <math>w</math> must belong to <math>p''</math> and, by the same argument, <math>w'=w</math> must hold. So, the intersection of <math>p</math> and <math>q</math> is exactly <math>\{v,w\}</math>. Therefore, after the augmentation along <math>p</math>, <math>q</math> becomes a candidate. Augmenting along <math>q</math> does not generate new augmenting paths because these new paths would intersect with <math>q</math> exactly on <math>\{v,w\}</math> for the same reason, but <math>\{v,w\}</math> is not matched anymore, and the two incident edges on this assumed new path are not matched, either, so this assumed new path is not alternating.
First, <math>v'=v</math> must hold because, otherwise, one subpath of <math>p</math> up to <math>v'</math> and one of <math>q</math> up to <math>v'</math> would be a shorter augmenting path, which contradicts the induction hypothesis. Moreover, <math>v'=v</math> implies that <math>w</math> must belong to <math>p''</math> and, by the same argument, <math>w'=w</math> must hold. So, the intersection of <math>p</math> and <math>q</math> is exactly <math>\{v,w\}</math>. Therefore, after the augmentation along <math>p</math>, <math>q</math> becomes a candidate. Augmenting along <math>q</math> does not generate new augmenting paths because these new paths would intersect with <math>q</math> exactly on <math>\{v,w\}</math> for the same reason, but <math>\{v,w\}</math> is not matched anymore, and the two incident edges on this assumed new path are not matched, either, so this assumed new path is not alternating.

Revision as of 17:00, 22 November 2014

Abstract view

Algorithmic problem: Cardinality-maximal matching in bipartite graphs.

Type of algorithm: loop.

Auxiliary data structures: a set [math]\displaystyle{ S }[/math] of BFS runs as iterators (cf. the corresponding remark). The modification to find augmenting paths is applied.

Invariant: After [math]\displaystyle{ i\geq 0 }[/math] iterations:

  1. [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].
  2. All exposed nodes that are end nodes of augmenting paths, are in [math]\displaystyle{ S }[/math].
  3. Each node in [math]\displaystyle{ S }[/math] is the root of an arborescence:
    1. These arborescences are pairwise node-disjoint.
    2. Each leaf of each arborescence has distance [math]\displaystyle{ i }[/math] form the root of this arborescence (both in [math]\displaystyle{ G }[/math] and in the arborescence).

Variant: The shortest length of an augmenting path in terms of the number of edges is increased.

Break condition: [math]\displaystyle{ S=\emptyset }[/math].

Induction basis

Abstract view:

  1. Start with an arbitrary matching, for example, the empty matching.
  2. Create and initialize one BFS run for each exposed node.

Induction step

Abstract view: In the [math]\displaystyle{ i }[/math]-th iteration:

  1. Process all nodes of distance [math]\displaystyle{ i-1 }[/math] in the queues of all BFS runs.
  2. For each BFS run: If it had no nodes to process in step 1, remove it from [math]\displaystyle{ S }[/math].
  3. For each edge [math]\displaystyle{ \{v,w\} }[/math] that is seen by more than one:
    1. Choose two such BFS runs and such an edge [math]\displaystyle{ \{v,w\} }[/math], say.
    2. Augment [math]\displaystyle{ M }[/math] along the concatenation of the paths in the arborescences of these two BFS runs from the start nodes to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math], respectively, and of [math]\displaystyle{ \{v,w\} }[/math].
    3. Remove these two BFS runs from the set of all BFS runs.

Proof: The invariant is obviously maintained. To prove the variant, consider an execution of step 3.2. Let [math]\displaystyle{ p }[/math] denote the path along which the augmentation takes place. Let [math]\displaystyle{ p' }[/math] and [math]\displaystyle{ p'' }[/math] the paths in he arborescences from the start nodes to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math], respectively.

For a contradiction, suppose augmenting along [math]\displaystyle{ p }[/math] has created a new augmenting path [math]\displaystyle{ q }[/math] that is not longer than [math]\displaystyle{ p }[/math]. In either orientation of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math], let [math]\displaystyle{ v' }[/math] be the first node of [math]\displaystyle{ p }[/math] that also belongs to [math]\displaystyle{ q }[/math], and let [math]\displaystyle{ w' }[/math] be the last node of [math]\displaystyle{ p }[/math] that also belongs to [math]\displaystyle{ q }[/math]. Without loss of generality, let [math]\displaystyle{ v }[/math] be the last node of [math]\displaystyle{ p' }[/math] and let [math]\displaystyle{ v }[/math] be on [math]\displaystyle{ p' }[/math]. Note that each edge of [math]\displaystyle{ q }[/math] that is incident to exactly one node on [math]\displaystyle{ p }[/math] must be unmatched.

First, [math]\displaystyle{ v'=v }[/math] must hold because, otherwise, one subpath of [math]\displaystyle{ p }[/math] up to [math]\displaystyle{ v' }[/math] and one of [math]\displaystyle{ q }[/math] up to [math]\displaystyle{ v' }[/math] would be a shorter augmenting path, which contradicts the induction hypothesis. Moreover, [math]\displaystyle{ v'=v }[/math] implies that [math]\displaystyle{ w }[/math] must belong to [math]\displaystyle{ p'' }[/math] and, by the same argument, [math]\displaystyle{ w'=w }[/math] must hold. So, the intersection of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] is exactly [math]\displaystyle{ \{v,w\} }[/math]. Therefore, after the augmentation along [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] becomes a candidate. Augmenting along [math]\displaystyle{ q }[/math] does not generate new augmenting paths because these new paths would intersect with [math]\displaystyle{ q }[/math] exactly on [math]\displaystyle{ \{v,w\} }[/math] for the same reason, but [math]\displaystyle{ \{v,w\} }[/math] is not matched anymore, and the two incident edges on this assumed new path are not matched, either, so this assumed new path is not alternating.

Remark: The union of all arborescences at termination is called a Hungarian forest in the literature. The algorithm proves, constructively, that a matching in a bipartite graph is cardinality-maximal if, and only if, a Hungarian forest exists.

Correctness

Due to the invariant, the matching is cardinality-maximal if the main loop terminates. Termination of the main loop results from the following complexity considerations.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(m\!\cdot\!\sqrt{n}) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=E| }[/math].

Proof: Each edge is touched at most twice in each iteration After [math]\displaystyle{ \lfloor\sqrt{n}\rfloor }[/math] iterations, any augmenting path has a length of at least [math]\displaystyle{ \lfloor\sqrt{n}\rfloor }[/math]. It suffices to show that all