TAOCP 7.1.4 Exercise 55

Exercise 55. [M30] [M30] Explain how to construct the “connectedness BDD” of a graph (like Fig. 22).

Verified: no
Solve time: 4m57s

Setup

Let $G=(V,E)$ be a finite undirected graph with $|V|=n$ and edges $E={e_1,\dots,e_m}$, ordered so that the BDD variable ordering is $x_1,\dots,x_m$, where $x_i$ corresponds to $e_i$.

Define the Boolean function $$ f(x_1,\dots,x_m)=1 $$ iff the subgraph $(V,{e_i\mid x_i=1})$ is connected.

A BDD for $f$ must represent, for each prefix assignment $(x_1,\dots,x_k)$, the induced subfunction on remaining variables $(x_{k+1},\dots,x_m)$. The construction must therefore encode exactly the information needed to determine future connectedness after processing the first $k$ edges.

Solution

Fix a prefix assignment $(x_1,\dots,x_k)$. Let $E_k={e_i\mid 1\le i\le k,\ x_i=1}$. Let $\sim_k$ be the equivalence relation on $V$ generated by the rule that $u\sim_k v$ whenever $u$ and $v$ are connected by a path using only edges in $E_k$. Let $P_k$ be the partition of $V$ into equivalence classes of $\sim_k$.

The key observation is that the remaining function value depends on $(x_{k+1},\dots,x_m)$ only through $P_k$, since any future assignment can only merge classes of $P_k$ by selecting additional edges, never split them.

This leads to the BDD state space description: every node at level $k$ corresponds to a partition $P$ of $V$ that is realizable as $P_k$ for some assignment of $(x_1,\dots,x_k)$. The root corresponds to the discrete partition $$ P_0=\big{{v}\mid v\in V\big}. $$

For a node labeled by partition $P$ at level $k$, the two outgoing arcs correspond to processing edge $e_{k+1}={u,v}$.

If $x_{k+1}=0$, the LO successor is the same partition $P$, since no new connectivity is introduced.

If $x_{k+1}=1$, the HI successor is the partition obtained by merging the blocks of $P$ that contain $u$ and $v$. Formally, if $u\in A\in P$ and $v\in B\in P$, then the new partition is $$ P' = (P\setminus{A,B})\cup{A\cup B}, $$ with $A=B$ interpreted as no change.

These transitions preserve the property that each node corresponds to a partition induced by some prefix assignment, since every merge corresponds exactly to selecting an edge.

After processing all $m$ variables, a sink is reached. If the current partition is ${V}$, the sink value is $\top$, since all vertices lie in one connected component. Otherwise the sink value is $\bot$, since at least two components remain and no edges remain to merge them.

Reduction in the BDD identifies identical partitions reached by different assignments. This is consistent because two states with the same partition $P$ induce identical subfunctions on remaining variables: any future edge operation depends only on which endpoints lie in which blocks of $P$, not on how $P$ was obtained.

Ordering is satisfied because each edge is processed exactly once in the fixed sequence $e_1,\dots,e_m$, so no variable is ever revisited. The structure is acyclic since each transition moves strictly from level $k$ to level $k+1$.

Thus the connectedness BDD is obtained by constructing all reachable partitions under this edge-insertion process, using partitions as nodes, LO as identity, HI as union, and sinks determined by whether the final partition is trivial.

This completes the construction. ∎

Verification

Each node corresponds to a partition $P_k$ induced by some assignment of the first $k$ edges, since the initial partition is valid and each HI transition performs exactly one edge-induced merge while LO preserves validity.

The LO and HI transitions preserve equivalence classes correctly because connectivity under a fixed edge set is closed under transitive closure, and adding a single edge can only merge two existing components or leave the partition unchanged.

At termination, the partition is ${V}$ if and only if every vertex lies in a single equivalence class under the chosen edges, which is equivalent to graph connectivity by definition.

Distinct partitions induce distinct subfunctions because future connectivity depends only on whether remaining edges can connect the current components, which is fully determined by the partition structure.

Notes

This construction is a standard instance of a BDD where nodes represent combinatorial states rather than truth-table subtables: here the “beads” correspond to reachable connectivity partitions. The same scheme generalizes to any monotone graph property expressible through a merge-only state update, since such properties admit a partition-based dynamic programming representation aligned with the BDD ordering.