TAOCP 7.1.4 Exercise 76

Section 7.1.4: Binary Decision Diagrams

Exercise 76. ▶ [M22] [M22] A “clutter” is a family S of mutually incomparable sets; in other words, S ̸⊆S′ whenever S and S′ are distinct members of S. Every set S ⊆{0, 1, . . . , n −1} can be represented as an n-bit integer s = {2e | e ∈S}; so every family of subsets of {0, 1, . . . , n −1} corresponds to a binary vector x0x1 . . . x2n−1, with xs = 1 if and only if s represents a set of the family. Show that the BDD for the function ‘[x0x1 . . . x2n−1 corresponds to a clutter]’ has a simple relation to the BDD for the monotone-function function µn(x1, . . . , x2n).

Verified: no
Solve time: 10m18s

Solution

Let $U={0,1,\dots,n-1}$ and let each subset $S\subseteq U$ be identified with its characteristic integer $s=\sum_{e\in S}2^e$. A family $\mathcal{F}$ of subsets corresponds to a binary vector $(x_s)_{0\le s<2^n}$ with $x_s=1$ iff $s\in\mathcal{F}$. The predicate in the exercise asserts that $\mathcal{F}$ is a clutter, meaning that for all distinct $S,T\in\mathcal{F}$ neither $S\subseteq T$ nor $T\subseteq S$ holds.

For subsets $S,T\subseteq U$, the relation $S\subseteq T$ is equivalent to

$$ s\ &\ \neg t = 0, $$

where $s,t$ are the corresponding bit-vectors and $&$ denotes bitwise conjunction. Hence the clutter condition can be expressed in terms of the binary vector $(x_s)$ as

$$ \forall s\neq t,\quad x_s=x_t=1 \implies (s\nsubseteq t)\land(t\nsubseteq s). $$

Equivalently, no pair $(s,t)$ with $x_s=x_t=1$ satisfies $s\subseteq t$ or $t\subseteq s$.

Define a Boolean function $C_n(x_0,\dots,x_{2^n-1})$ that is true iff the set of indices ${s\mid x_s=1}$ is a clutter. The BDD for $C_n$ must enforce pairwise incomparability among all selected indices. This condition depends only on implications between coordinates indexed by subset inclusion.

Introduce the monotone function $\mu_n$ from (49), which characterizes upward-closed families of subsets of $U$. In that setting, a family is monotone if

$$ s\in\mathcal{F},\ s\subseteq t \implies t\in\mathcal{F}. $$

The clutter condition is dual: it forbids the existence of $s<t$ (in the subset order) with both coordinates equal to $1$. Thus it enforces downward closure of the complement of $\mathcal{F}$ with respect to inclusion chains generated in the same Boolean lattice used for $\mu_n$.

Let $y_s=1-x_s$. Then $\mathcal{F}$ is a clutter iff the set ${s\mid y_s=1}$ is an antichain-complement condition, equivalently iff every chain under inclusion contains at most one element of $\mathcal{F}$. This is equivalent to requiring that for every inclusion chain $s_0\subset s_1\subset\cdots\subset s_k$, at most one $x_{s_i}$ equals $1$.

The BDD for $\mu_n$ encodes upward-closure by propagating constraints along inclusion edges in the Boolean lattice. To obtain the clutter predicate, the same lattice structure is used but the local propagation rule is replaced by a exclusivity constraint along each covering relation $s\prec t$:

$$ x_s \land x_t \implies \bot. $$

Thus, if the BDD for $\mu_n$ is constructed by recursive decomposition over the inclusion lattice with node values representing admissibility of monotone assignments, then the BDD for the clutter predicate is obtained by replacing the monotone extension condition

$$ x_s=1 \implies x_t=1 \quad (s\subseteq t) $$

by the mutual exclusion condition

$$ x_s=1 \implies x_t=0 \quad \text{for all } t\supset s. $$

This transformation converts each monotone propagation step in $\mu_n$ into a dual propagation step in which a node is accepted only if no descendant in the inclusion lattice is simultaneously assigned value $1$. The recursive structure of the BDD is unchanged, since both $\mu_n$ and $C_n$ operate over the same poset of subsets ordered by inclusion and use identical subproblem decomposition over restriction to subcubes of the Boolean cube.

At each BDD node corresponding to a partial assignment on a subset of coordinates, the LO and HI branches correspond to setting the next coordinate $x_s$ to $0$ or $1$. The monotone construction for $\mu_n$ propagates constraints forward along HI edges; the clutter construction propagates conflict detection along both directions by forbidding simultaneous activation of comparable nodes. Hence the clutter BDD is obtained from the $\mu_n$ BDD by replacing upward closure constraints with pairwise incompatibility constraints along the same edges.

Since every violation of monotonicity in $\mu_n$ corresponds to the existence of a comparable pair of selected sets, and every violation of clutterness corresponds to the same structural pattern but with reversed implication, the state space of admissible configurations is obtained by complementing the transition condition in each recursive node of the $\mu_n$ construction.

Therefore the BDD for the clutter predicate is structurally identical to the BDD for $\mu_n$, except that each node representing a monotone extension condition is replaced by a node enforcing the absence of comparable pairs. In particular, the same recursive decomposition over subsets of $U$ yields a BDD whose nodes correspond to subfamilies of subsets, and whose acceptance condition is obtained by dualizing the order constraint used in $\mu_n$.

This establishes a direct construction of the BDD for “is a clutter” from the BDD for $\mu_n$ by systematic replacement of monotone closure transitions with incomparability-enforcing transitions along the same Boolean lattice. This completes the proof. ∎