Maximum matching by Edmonds: Difference between revisions

From Algowiki
Jump to navigation Jump to search
m (→‎Recursive step: Bezeichnung und Link)
 
(19 intermediate revisions by one other user not shown)
Line 1: Line 1:
== Abstract view ==
== Abstract view ==


'''Algo'''
'''Algorithmic problem:'''
[[Cardinality-maximal matching]]


'''Type of algorithm:''' recursion.
'''Type of algorithm:''' recursion.


'''Invariant:'''
'''Invariant:'''
Each recursive step returns a cardinality-maximal matching.
Each recursive step returns a cardinality-maximal matching of its input graph.


'''Variant:'''
'''Variant:'''
The number of nodes decreases.
The number of nodes decreases.


'''Break condition:'''
== Recursion anchor ==
The graph search does not run into a [[Matchings in graphs#Blossoms|blossom]].


== Induction basis ==
The graph search does not find an augmenting path, nor does it run into a [[Matchings in graphs#Blossoms|blossom]].
 
== Recursive step ==


'''Abstract view:'''
'''Abstract view:'''
Start with some matching, for example, the empty matching.
Apply the  [[Classical bipartite cardinality matching#Induction step|modified repeated graph search]] from the [[Classical bipartite cardinality matching|classical algorithm]] for the restriction to [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]]. More specifically, choose a [[Breadth-first search|BFS]] or another graph traversal strategy that will never return to the start node (this requirement excludes [[Depth-first search|DFS]]).
 
== Induction step ==


'''Abstract view:'''
The search maintains a boolean flag even/odd, which indicates the parity of the distance of the current node from the start node of the current search. Also, each node has a boolean label even/odd. When this node is seen for the first time, its label is set according to the flag. If a labeled node is seen again, but with another distance parity than before:
# Apply the modified repeated graph search from the [[Classical bipartite cardinality matching#Induction step|classical algorithm]] for the restriction to [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]].
# The repeated graph search is terminated.
# However, in addition:
# A blossom <math>B</math> is identified.
# Choose a [[Breadth-first search|BFS]] or another grah traversal strategy that will never return to the start node (this requirement excludes [[Depth-first search|DFS]])
# <math>B</math> is [[Matchings in graphs#Blossoms|shrunken]], giving <math>G'=(V',E')</math> and the restriction <math>M'</math> of <math>M</math> to <math>G'</math>.
## The search maintains a boolean flag even/odd, which indicates the parity of the distance of the current node from the start node of the current search.
# The procedure is called recursively with <math>G'</math> and <math>M'</math>.
## Also, each node has a boolean label even/odd. Whenever this node is seen (not only the first time when it is seen), its label is set according to the flag.
# Exactly one node of <math>B</math> is matched by <math>M'</math>, so extend <math>M'</math> in the obvious, unique way by <math>\lfloor|B|/2\rfloor</math> edges of <math>B</math>.
# If a labeled node is seen again, but with another distance parity than before:
# This extension of <math>M'</math> is returned.
## The repeated graph search is terminated.
## A blossom <math>B</math> is identified.
## <math>C</math> is shrunken, giving <math>G'=(V',E')</math> and the restriction <math>M'</math> of <math>M</math> to <math>G'</math>.
## The procedure is called recursively with <math>G'</math> and <math>M'</math>.
## Exactly one node of <math>C</math> is matched by <math>M'</math>, so extend <math>M'</math> in the obvious, unique way by <math>\lfloor|C|/2\rfloor</math> edges of <math>C</math>.
## Return this extension of <math>M'</math>.


'''Remark:'''
'''Remark:'''
In typical formulations of this algorithm, the graph search is not left open but the search strategy applied in [[Hopcroft-Karp]] is hard-coded.
In typical formulations of this algorithm, the graph search is not left open but the search strategy applied in [[Hopcroft-Karp]] is hard-coded.


'''Implementation of step 3.2:'''
'''Implementation of step 2:'''
Let <math>w</math> be the node on which the two different parities occur, and let <math>v</math> be the node from which <math>w</math> is seen at that moment. In the arborescence constructed so far, let <math>u</math> denote the node such that the paths from the start node to <math>v</math> and <math>w</math> coincide up to <math>u</math> and part at <math>u</math>.  Note that the incoming edge of <math>u</math> in the arborescence is matched because, otherwise, the arborescence could mot branch at <math>u</math>. Therefore, the concatenation of the two branches from <math>u</math> to <math>v</math> an <math>w</math>, respectively, with <math>\{v,w\}</math> is a blossom, and the search entered this blossom via its stem.
Let <math>w</math> be the node on which the two different parities occur, and let <math>v</math> be the node from which <math>w</math> is seen at that moment. In the arborescence constructed so far, let <math>u</math> denote the node such that the paths from the start node to <math>v</math> and <math>w</math> coincide up to <math>u</math> and part at <math>u</math>.  Note that the incoming edge of <math>u</math> in the arborescence is matched because, otherwise, the arborescence could not branch at <math>u</math>. Therefore, the concatenation of the branch from <math>u</math> to <math>v</math>, the branch from <math>u</math> to <math>w</math>, and <math>\{v,w\}</math> is a blossom, and the search entered this blossom via its stem.


'''Proof:'''
'''Proof:'''
Basically, we have to show: If <math>M</math> is not maximum, the graph search will either find an augmenting path or run into a blossom via its stem. Suppose the search does not find an augmenting path. Due to the proof in the [[Classical bipartite cardinality matching#Induction step|induction step]] of the [[Classical bipartite cardinality matching|classical bipartite cardinality algorithm]], the graph search runs into an odd cycle. Since we chose a graph search strategy that never returns to the start node, the remark on that proof implies that this odd cycle is a blossom, and that the search entered  this blossom via its stem.
First we show: If <math>M</math> is not maximum, the graph search will either find an augmenting path or run into a blossom via its stem. Suppose the search does not find an augmenting path. Due to the proof in the [[Classical bipartite cardinality matching#Induction step|induction step]] of the [[Classical bipartite cardinality matching|classical bipartite cardinality matching algorithm]], the graph search runs into an odd cycle. Since we chose a graph search strategy that never returns to the start node, the remark on that proof implies that this odd cycle is a blossom, and that the search entered  this blossom via its stem.
 
It remains to show that the returned extension of <math>M'</math> is cardinality-maximal for <math>G</math> provided <math>M'</math> is cardinality-maximal fpr <math>G'</math>. However, this follows immediately from the fundamental [[Matchings in graphs#Blossoms|statement about blossoms]].


== Correctness ==
== Correctness ==


When the recursion terminates, [[Cardinality-maximal matching#Berge's theorem|Berge's theorem]] implies that the
Follows immediately from the invariant.
 
== Complexity ==
 
'''Statement:'''
The asymptotic worst-case complexity is in <math>\mathcal{O}(n\!\cdot\!m)</math>, where <math>n=|V|</math> and <math>m=|E|</math>.
 
'''Proof:'''
Due to the variant, the recursion depth is in <math>\mathcal{O}(n)</math>. Each recursive step is dominated by the graph traversal. The [[Basic graph definitions#Adjacency, incidence, and degree|statement and remark on isolated nodes]] apply.

Latest revision as of 09:25, 22 February 2015

Abstract view

Algorithmic problem: Cardinality-maximal matching

Type of algorithm: recursion.

Invariant: Each recursive step returns a cardinality-maximal matching of its input graph.

Variant: The number of nodes decreases.

Recursion anchor

The graph search does not find an augmenting path, nor does it run into a blossom.

Recursive step

Abstract view: Apply the modified repeated graph search from the classical algorithm for the restriction to bipartite graphs. More specifically, choose a BFS or another graph traversal strategy that will never return to the start node (this requirement excludes DFS).

The search maintains a boolean flag even/odd, which indicates the parity of the distance of the current node from the start node of the current search. Also, each node has a boolean label even/odd. When this node is seen for the first time, its label is set according to the flag. If a labeled node is seen again, but with another distance parity than before:

  1. The repeated graph search is terminated.
  2. A blossom [math]\displaystyle{ B }[/math] is identified.
  3. [math]\displaystyle{ B }[/math] is shrunken, giving [math]\displaystyle{ G'=(V',E') }[/math] and the restriction [math]\displaystyle{ M' }[/math] of [math]\displaystyle{ M }[/math] to [math]\displaystyle{ G' }[/math].
  4. The procedure is called recursively with [math]\displaystyle{ G' }[/math] and [math]\displaystyle{ M' }[/math].
  5. Exactly one node of [math]\displaystyle{ B }[/math] is matched by [math]\displaystyle{ M' }[/math], so extend [math]\displaystyle{ M' }[/math] in the obvious, unique way by [math]\displaystyle{ \lfloor|B|/2\rfloor }[/math] edges of [math]\displaystyle{ B }[/math].
  6. This extension of [math]\displaystyle{ M' }[/math] is returned.

Remark: In typical formulations of this algorithm, the graph search is not left open but the search strategy applied in Hopcroft-Karp is hard-coded.

Implementation of step 2: Let [math]\displaystyle{ w }[/math] be the node on which the two different parities occur, and let [math]\displaystyle{ v }[/math] be the node from which [math]\displaystyle{ w }[/math] is seen at that moment. In the arborescence constructed so far, let [math]\displaystyle{ u }[/math] denote the node such that the paths from the start node to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] coincide up to [math]\displaystyle{ u }[/math] and part at [math]\displaystyle{ u }[/math]. Note that the incoming edge of [math]\displaystyle{ u }[/math] in the arborescence is matched because, otherwise, the arborescence could not branch at [math]\displaystyle{ u }[/math]. Therefore, the concatenation of the branch from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math], the branch from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ w }[/math], and [math]\displaystyle{ \{v,w\} }[/math] is a blossom, and the search entered this blossom via its stem.

Proof: First we show: If [math]\displaystyle{ M }[/math] is not maximum, the graph search will either find an augmenting path or run into a blossom via its stem. Suppose the search does not find an augmenting path. Due to the proof in the induction step of the classical bipartite cardinality matching algorithm, the graph search runs into an odd cycle. Since we chose a graph search strategy that never returns to the start node, the remark on that proof implies that this odd cycle is a blossom, and that the search entered this blossom via its stem.

It remains to show that the returned extension of [math]\displaystyle{ M' }[/math] is cardinality-maximal for [math]\displaystyle{ G }[/math] provided [math]\displaystyle{ M' }[/math] is cardinality-maximal fpr [math]\displaystyle{ G' }[/math]. However, this follows immediately from the fundamental statement about blossoms.

Correctness

Follows immediately from the invariant.

Complexity

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

Proof: Due to the variant, the recursion depth is in [math]\displaystyle{ \mathcal{O}(n) }[/math]. Each recursive step is dominated by the graph traversal. The statement and remark on isolated nodes apply.