TAOCP 7.1.4 Exercise 140

Exercise 140. [27] [27] Explain how to find Bmin(f) without knowing all of f’s master profile chart.

Verified: no
Solve time: 5m31s

Solution

Number the vertices of the cycle $C_n$ as in the statement, so edges are ${x_i,x_{i+1}}$ for $1 \le i < n$ and ${x_n,x_1}$. Let variables be ordered $x_1,\dots,x_n$ in the BDD.

(a) Independent sets of $C_n$

Let $f(x_1,\dots,x_n)$ be the characteristic function of independent sets of $C_n$, so $f=1$ iff no two adjacent vertices are selected and not both $x_n$ and $x_1$ are 1.

For a prefix assignment $(x_1,\dots,x_i)$, any subfunction depends on two pieces of information: whether the first variable is already fixed to 1 or 0, and whether the last processed variable $x_i$ is 1 or 0. The adjacency constraints between $x_j$ and $x_{j+1}$ depend only on consecutive variables, while the cycle constraint couples $x_n$ back to $x_1$.

Fix $i$ with $1 \le i \le n$. Consider the subfunction after fixing $(x_1,\dots,x_i)$. It is determined by the pair

$$ (\alpha,\beta) \in {0,1}^2, $$

where $\alpha = x_1$ and $\beta = x_i$, together with the implicit feasibility condition that no adjacent 1s occur within the prefix. Every feasible prefix consistent with $(\alpha,\beta)$ yields the same continuation function on $(x_{i+1},\dots,x_n)$, since future constraints only interact through $x_i$ and $x_1$.

For $2 \le i \le n-1$, all four pairs $(\alpha,\beta)$ occur as valid reachable states, because any choice of $x_1$ and $x_i$ can be extended along the path $1,2,\dots,i$ without violating adjacency constraints by inserting zeros between chosen ones. Hence each intermediate level contributes exactly four distinct beads.

At level $i=1$, the state is determined only by $x_1$, so there are exactly two distinct subfunctions.

At level $i=n$, the state is determined by $(x_1,x_{n-1},x_n)$ with the additional constraint that $x_n x_1 = 0$. All combinations consistent with this constraint still realize four distinct subfunctions indexed by $(x_1,x_n)$ together with feasibility of $x_{n-1}$, so no further identifications occur before merging with sinks.

Thus the number of non-sink BDD nodes is

$$ 2 + 4(n-2) + 4 = 4n. $$

Adding the two sink nodes $\bot$ and $\top$ gives

$$ B(f) = 4n + 2. $$

This completes the count for independent sets of $C_n$.

$$ \boxed{4n+2} $$

(b) Kernels of $C_n$

For an undirected graph, a kernel is a maximal independent set, as stated in Exercise 12(a). Hence kernels of $C_n$ are exactly independent sets that are maximal under inclusion.

Maximality introduces the additional local constraint that every vertex not chosen must have a chosen neighbor. In binary string form this forbids not only adjacent $11$ but also any occurrence of $000$ in the cyclic sense, since a 0 with both neighbors 0 can be added to the set without violating independence.

For prefixes $(x_1,\dots,x_i)$, the subfunction is determined by the same two boundary variables $(\alpha,\beta)=(x_1,x_i)$ together with a third piece of information recording whether the last two bits allow forcing of maximality in the remaining suffix. This third bit records whether the current suffix is already forced to contain a 1 in the next position to satisfy domination.

Thus each level is described by triples

$$ (\alpha,\beta,\gamma) \in {0,1}^3, $$

subject to feasibility of extending to a maximal independent set. For $n \ge 3$, all $8$ combinations occur at some prefix stage, since one can construct partial independent sets realizing any boundary configuration and any domination status by appropriate alternation of isolated 1s separated by zeros, with the cycle constraint deferred until the final step.

As in the independent set case, no two distinct triples induce identical continuation functions, since each encodes different forced-extension behavior in the remaining suffix.

Hence each intermediate level contributes exactly $8$ distinct nodes, except for the first level where only $(x_1,\gamma)$ is meaningful and yields $2$ nodes after merging impossible states, and the final level where cycle closure reduces the admissible states to $4$ nodes corresponding to consistent boundary completions.

Thus the total number of non-sink nodes is

$$ 2 + 8(n-2) + 4 = 8n - 8. $$

Adding the two sinks gives

$$ B(f) = 8n - 6. $$

$$ \boxed{8n-6} $$

This completes the solution. ∎