TAOCP 7.1.4 Exercise 211

Exercise 211. [M20] [M20] When f describes the solutions to an exact cover problem, is Z(f)≤B(f)?

Verified: yes
Solve time: 1m57s

Solution

Let $f$ be the Boolean function that represents solutions of an exact cover instance on a universe $U$ with a family of subsets encoded by variables $x_1,\dots,x_n$. A solution is a choice of subsets that covers every element of $U$ exactly once. The function value is $f(x)=1$ if and only if the chosen subsets form an exact cover.

The question asks whether, in all such cases, the size of the ZDD representing $f$, denoted $Z(f)$, is always bounded by the size of the BDD representing the same function, denoted $B(f)$.

Consider the degenerate exact cover instance in which the universe $U$ is empty. The exact cover condition imposes no constraints, since there are no elements that must be covered. Every choice of subsets satisfies the condition vacuously, hence every assignment $x \in {0,1}^n$ is a solution. Therefore the Boolean function is constant,

$$ f(x_1,\dots,x_n)=1. $$

The reduced ordered BDD for a constant function $f \equiv 1$ consists only of a single terminal node $\top$, with no branch nodes. Hence

$$ B(f)=1 $$

if sinks are counted as nodes, or $B(f)=2$ if both $\bot$ and $\top$ are included as distinct terminal nodes. In either standard convention, $B(f)$ is $O(1)$ and independent of $n$.

The ZDD representation of the family of all subsets of an $n$-element set encodes the full power set. In a ZDD, the reduction rule removes nodes whose 1-arc leads to $\bot$, but retains structure for 0-arcs. The canonical ZDD for the full power set forms a chain in which each variable appears exactly once along any root-to-terminal path, and no node can be merged because each level corresponds to a distinct variable index. This yields exactly $n$ nonterminal nodes plus a terminal node, so

$$ Z(f)=n+1. $$

For all $n \ge 2$, this gives

$$ Z(f)=n+1 > 2 \ge B(f), $$

under either standard counting convention for $B(f)$.

This instance is an exact cover problem in the sense that it is a valid (though trivial) cover system with no constraints, yet it violates the inequality $Z(f)\le B(f)$.

This completes the proof. ∎