Branching by Edmonds

Abstract view

Definition:

1. An arc [math]\displaystyle{ (v,w)\in A }[/math] is critical if its weight is not smaller than the weight of any other arc into [math]\displaystyle{ w }[/math].
2. A critical subgraph of [math]\displaystyle{ G }[/math] consists of all nodes of [math]\displaystyle{ G }[/math] and of a maximum number of critical arcs.

Type of algorithm: recursion.

Invariant: The output of a recursive call is a maximum branching of the weighted graph that was the argument of this recursive call.

Basis operation in each recursiv step: compute a critical graph.

Induction basis

Abstract view: Terminate if the critical graph is cycle-free.

Proof: If a critical graph [math]\displaystyle{ C }[/math] is cycle-free, it is a branching. Consider some other branching [math]\displaystyle{ B }[/math]. We have to show that [math]\displaystyle{ B }[/math] does not have more weight than [math]\displaystyle{ C }[/math].

Obviously, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc [math]\displaystyle{ a }[/math] of [math]\displaystyle{ B }[/math], there is an arc [math]\displaystyle{ a' }[/math] in[math]\displaystyle{ C }[/math] pointing to the same node. Due to the choice of arcs for [math]\displaystyle{ C }[/math], it is [math]\displaystyle{ w(a)\leq w(a') }[/math].

Induction step

Abstract view:

1. Identify one cycle [math]\displaystyle{ Z }[/math] in the computed critical graph.
2. Let [math]\displaystyle{ W }[/math] denote the minimum weight of all arcs on [math]\displaystyle{ Z }[/math].
3. For every arc [math]\displaystyle{ (v,w)\in A }[/math] pointing from some node [math]\displaystyle{ v }[/math] outside [math]\displaystyle{ Z }[/math] to some node [math]\displaystyle{ w }[/math] on [math]\displaystyle{ Z }[/math]: Increase the weight of [math]\displaystyle{ (v,w) }[/math] by [math]\displaystyle{ W-w(v',w) }[/math], where [math]\displaystyle{ (v',w) }[/math] is the arc on [math]\displaystyle{ Z }[/math] that points into [math]\displaystyle{ w }[/math].
4. Shrink [math]\displaystyle{ Z }[/math] into one new super-node, where every arc pointing to (resp., from) some node on [math]\displaystyle{ Z }[/math] now points to (from) that super-node.
5. Call the algorithm recursively for the modified weighted graph after shrinking.
6. Unshrink the graph.

Remarks

1. The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on [math]\displaystyle{ Z }[/math] must probably be maintained.
2. Several cycles may be discovered simultaneously by one run of DFS. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled simulaneously, in one recursive call, without any interference.