Branching by Edmonds

Abstract view

Algorithmic problem: Maximum branching

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 incoming arc of [math]\displaystyle{ w }[/math].
2. A critical subgraph [math]\displaystyle{ G'=(V,A') }[/math] of [math]\displaystyle{ G }[/math] contains one critical arc [math]\displaystyle{ (v,w) }[/math] for every node [math]\displaystyle{ w\in V }[/math] with positive indegree and no further 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.

Basic operation at the beginning of each recursive step: compute a critical subgraph [math]\displaystyle{ G'=(V,A') }[/math] for the input graph [math]\displaystyle{ G }[/math].

Induction basis

Abstract view: Terminate if [math]\displaystyle{ G' }[/math] is cycle-free.

Proof: If [math]\displaystyle{ G' }[/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 total weight than [math]\displaystyle{ G' }[/math].

By definition, 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{ G' }[/math] pointing to the same node. Due to the choice of arcs for [math]\displaystyle{ G' }[/math], it is [math]\displaystyle{ w(a)\leq w(a') }[/math].

Induction step

Abstract view:

1. Identify some cycle [math]\displaystyle{ Z }[/math] in [math]\displaystyle{ G' }[/math].
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]:
   1. Decrease the weight of [math]\displaystyle{ (v,w) }[/math] by [math]\displaystyle{ w(v',w)-W\geq 0 }[/math], where [math]\displaystyle{ (v',w) }[/math] is the incoming arc of [math]\displaystyle{ w }[/math] on [math]\displaystyle{ Z }[/math].
   2. If the new weight of [math]\displaystyle{ (v,w) }[/math] is not positive, remove [math]\displaystyle{ (v,w) }[/math] from [math]\displaystyle{ G }[/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, giving branching [math]\displaystyle{ B }[/math].
6. Unshrink the graph.
7. Add all arcs of [math]\displaystyle{ Z }[/math] to [math]\displaystyle{ B }[/math] giving [math]\displaystyle{ B' }[/math].
8. If [math]\displaystyle{ B }[/math] contains an arc [math]\displaystyle{ (v,w) }[/math] such that [math]\displaystyle{ v }[/math] is outside [math]\displaystyle{ Z }[/math] and [math]\displaystyle{ w }[/math] is on [math]\displaystyle{ Z }[/math]: remove the incoming arc of [math]\displaystyle{ w }[/math] on [math]\displaystyle{ Z }[/math] from [math]\displaystyle{ B }[/math]; otherwise, remove one arc with weight [math]\displaystyle{ W }[/math] on [math]\displaystyle{ Z }[/math]. Let [math]\displaystyle{ B'' }[/math] be the result in both cases.
9. Return [math]\displaystyle{ B'' }[/math].

Proof: Obviously, [math]\displaystyle{ B'' }[/math] is a branching, so we have to prove that it has maximum weight. Let [math]\displaystyle{ B_{\mathrm{opt}} }[/math] be a maximum branching in [math]\displaystyle{ G }[/math] such that, among all maximum branchings in [math]\displaystyle{ G }[/math], [math]\displaystyle{ B_{\mathrm{opt}} }[/math] shares as many arcs as possible with [math]\displaystyle{ B'' }[/math].

First we show that [math]\displaystyle{ B_{\mathrm{opt}} }[/math] contains all arcs of [math]\displaystyle{ C }[/math] except one. So, suppose for a contradiction that [math]\displaystyle{ B_{\mathrm{opt}} }[/math] does not contain the arcs [math]\displaystyle{ (v_1,w_1),\ldots,(v_k,w_k) }[/math] of [math]\displaystyle{ C }[/math], and that [math]\displaystyle{ k\gt 1 }[/math]. Since [math]\displaystyle{ B_{\mathrm{opt}} }[/math] is as close as possible to [math]\displaystyle{ B'' }[/math], replacing the incoming arc of any [math]\displaystyle{ w_i }[/math] by [math]\displaystyle{ (v_i,w_i) }[/math] in [math]\displaystyle{ B_{\mathrm{opt}} }[/math] and doing nothing else, would yield a result that is not a branching anymore. Since the indegrees do not change by that replacement, this means that adding [math]\displaystyle{ (v_i,w_i) }[/math] to [math]\displaystyle{ B_{\mathrm{opt}} }[/math] would close a cycle. In other words, there is a path [math]\displaystyle{ p_i }[/math] in [math]\displaystyle{ B_{\mathrm{opt}} }[/math] from [math]\displaystyle{ w_i }[/math] to [math]\displaystyle{ v_i }[/math]. Each path [math]\displaystyle{ p_i }[/math] must enter [math]\displaystyle{ C }[/math] at one of the nodes [math]\displaystyle{ w_j }[/math] because, otherwise, the node where [math]\displaystyle{ p_i }[/math] enters [math]\displaystyle{ C }[/math] had two incoming arcs in [math]\displaystyle{ B_{\mathrm{opt}} }[/math]: the incoming arc on [math]\displaystyle{ C }[/math] and the arc over which [math]\displaystyle{ p_i }[/math] enters [math]\displaystyle{ C }[/math]. However, this would imply that there is a cycle in the union of all paths [math]\displaystyle{ p_i }[/math] plus all arcs of [math]\displaystyle{ C' }[/math] not in [math]\displaystyle{ \{(v_1,w_1),\ldots,(v_k,w_k)\} }[/math]. This union is a subset of [math]\displaystyle{ B_{\mathrm{opt}} }[/math], which yields the desired contradiction.

Now we know that [math]\displaystyle{ B_{\mathrm{opt}} }[/math] contains all arcs except one on [math]\displaystyle{ C }[/math]. We next show that this is the arc [math]\displaystyle{ a }[/math] dropped in step 8. So, suppose for a contradiction that [math]\displaystyle{ a }[/math] belongs to [math]\displaystyle{ B_{\mathrm{opt}} }[/math]. Let [math]\displaystyle{ a' }[/math] be the unique arc on [math]\displaystyle{ C }[/math] that does not belong to [math]\displaystyle{ B_{\mathrm{opt}} }[/math]. Due to the specific choice of [math]\displaystyle{ a }[/math], the arcs of [math]\displaystyle{ B_{\mathrm{opt}} }[/math] that point into nodes of [math]\displaystyle{ C }[/math] do not have higher total weight than the arcs of [math]\displaystyle{ B'' }[/math] that point into nodes of [math]\displaystyle{ C }[/math]. Since [math]\displaystyle{ B_{\mathrm{opt}} }[/math] was chosen as close as possible to [math]\displaystyle{ B'' }[/math], this means replacing the arcs of [math]\displaystyle{ B_{\mathrm{opt}} }[/math] that point to nodes on [math]\displaystyle{ C }[/math] by the arcs in [math]\displaystyle{ B'' }[/math] that point to nodes in [math]\displaystyle{ C }[/math] would result in a subgraph that is not a branching anymore. Again, since the indegrees do not change, this means a cycle would be closed by that replacement. This cycle must enter [math]\displaystyle{ C }[/math] at some node on the segment of [math]\displaystyle{ C }[/math] from [math]\displaystyle{ a }[/math] to [math]\displaystyle{ a' }[/math] because otherwise [math]\displaystyle{ B_{\mathrm{opt}} }[/math] had

Now we know that [math]\displaystyle{ B'' }[/math] and [math]\displaystyle{ B_{\mathrm{opt}} }[/math] on all arcs that point into nodes on [math]\displaystyle{ C }[/math]. Therefore, the difference between the total weight of [math]\displaystyle{ B_{\mathrm{opt}} }[/math] with respect to the original arc weights and the total weight of the reduction of [math]\displaystyle{ B_{\mathrm{opt}} }[/math] to the shrunken graph with respect to the modified arc weights is identical to the difference between the total weights of [math]\displaystyle{ B'' }[/math] and [math]\displaystyle{ B }[/math]. By induction hypothesis, [math]\displaystyle{ B }[/math] is optimal for the shrunken graph. This proves the claim.

Note that at most one arc of [math]\displaystyle{ B }[/math] points into the super-node. Therefore, [math]\displaystyle{ B'' }[/math] contains all arcs of [math]\displaystyle{ Z }[/math] but exactly one.

Complexity

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

Proof: Using DFS for cycle detection, each recursive step requires [math]\displaystyle{ \mathcal{O}(n+m) }[/math]. In each shrink operation, the number of nodes decreases, so the recursion depth is [math]\displaystyle{ \mathcal{O}(n) }[/math].

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.