TAOCP 7.1.4 Exercise 24

Section 7.1.4: Binary Decision Diagrams

Exercise 24. [M22] [M22] Suppose twelve weights (w12, w13, . . . , w89) have been assigned to the edges of the grid in Fig. 22. Explain how to find a minimum spanning tree in that graph (namely, a spanning tree whose edges have minimum total weight), by applying Algo- rithm B to the BDD shown there.

Verified: no
Solve time: 6m43s

Solution

Let $G$ be the grid graph of Fig. 22, whose edges are the twelve edges $(w_{12}, w_{13}, \dots, w_{89})$. Let each edge $e$ have weight $w_e$, and let the variable associated with $e$ in the BDD be $x_e \in {0,1}$, where $x_e=1$ means that $e$ is selected.

The BDD in Fig. 22 represents exactly the family $\mathcal{T}$ of spanning trees of $G$. Each root-to-$\top$ path corresponds to a spanning tree, and each HI arc corresponds to inclusion of an edge, while each LO arc corresponds to exclusion. The structure of the BDD enforces all spanning tree constraints: acyclicity and connectivity are built into the reduction of states, so that only valid spanning trees appear as successful paths. In particular, since $G$ has $9$ vertices, every spanning tree contains exactly $8$ edges, which is reflected in the fact that every root-to-$\top$ path contains exactly eight HI choices, as established in the preceding exercise.

Define the weight of a selection $x=(x_e)$ by

$$ W(x)=\sum_{e} w_e x_e. $$

The problem of finding a minimum spanning tree is therefore equivalent to finding a root-to-$\top$ path in the BDD minimizing $W(x)$.

Algorithm B evaluates a weighted BDD by dynamic programming from sinks to the root. Let $C(v)$ denote the minimum cost of reaching $\top$ from node $v$. For the sink nodes,

$$ C(\top)=0, \qquad C(\bot)=\infty. $$

For a branch node $v$ labeled by edge $e$ with LO successor $v_0$ and HI successor $v_1$, the recurrence is

$$ C(v)=\min\bigl(C(v_0),; w_e + C(v_1)\bigr). $$

The term $C(v_0)$ corresponds to excluding edge $e$, and the term $w_e + C(v_1)$ corresponds to including edge $e$ and paying its weight. This recurrence is valid because every path from $v$ to $\top$ begins either with the LO arc or the HI arc, and the BDD is acyclic and ordered, so all successor costs are already well-defined when $C(v)$ is computed.

Applying this recurrence bottom-up over the BDD in Fig. 22 assigns a cost to every node, and in particular yields $C(\mathrm{ROOT})$, which equals the minimum total weight over all root-to-$\top$ paths. The corresponding predecessor choices at each node reconstruct a minimizing assignment $(x_e)$, and the selected edges ${e : x_e=1}$ form a spanning tree because every feasible path in the BDD encodes exactly one spanning tree of $G$.

Thus Algorithm B transforms the BDD of all spanning trees into a shortest-path computation in the implicit decision graph, and the resulting optimal path yields a minimum spanning tree of $G$.

This completes the proof. ∎