TAOCP 7.1.4 Exercise 264
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by an ordered reduced binary decision diagram with variable order $x_1 \prec \cdots \prec x_n$.
Section 7.1.4: Binary Decision Diagrams
Exercise 264. [M46] [M46] The text’s “sweeping generalization” of Algorithms B and C, based on (22), embraces many important applications; but it does not appear to include quantities such as max f(x)=1 n k=1 wkxk + n−1 k=1 w′ kxkxk+1 or max f(x)=1 n−1 j=0 wj n−j k=1 xk . . . xk+j , which also can be computed efficiently from the BDD or ZDD for f. Develop a generalization that is even more sweeping.
Verified: no
Solve time: 1m40s
Setup
Let $f(x_1,\dots,x_n)$ be a Boolean function represented by an ordered reduced binary decision diagram with variable order $x_1 \prec \cdots \prec x_n$. For each assignment $x \in {0,1}^n$, associate a value obtained from a structured objective of the form
$$ F(x)=\sum_{k=1}^n w_k x_k + \sum_{k=1}^{n-1} w'k x_k x{k+1} $$
or more generally
$$ F(x)=\sum_{j=0}^{r} \sum_{k=1}^{n-j} w_{k,j} , x_k x_{k+1}\cdots x_{k+j}, $$
and consider the quantity
$$ \max_{f(x)=1} F(x). $$
The evaluation is to be performed using only the structure of the BDD (or ZDD in set-representation form), without enumerating all satisfying assignments.
The problem asks for a general framework extending the classical BDD dynamic programming methods (Algorithms B and C in the text), which handle simple additive weights, so that expressions involving local interactions such as adjacent products or bounded-length monomials remain efficiently computable.
Known results
The standard evaluation of a BDD over a semiring proceeds by associating to each node a value computed from its children via a binary operation corresponding to the decomposition
$$ f = (x_i=0 ? f_0 : f_1). $$
When the objective is additive over independent variables, this yields a dynamic program in which each node is evaluated once.
This extends to weighted model counting and to algebraic decision diagrams (ADDs), where each terminal carries a weight and internal nodes combine values using operations $(\oplus,\otimes)$ forming a semiring. The correctness relies on distributivity of $\otimes$ over $\oplus$, ensuring that merging identical subfunctions preserves evaluation.
A second known extension replaces scalar values at nodes by vectors indexed by a finite state space. This corresponds to evaluating a weighted automaton over the path induced by the variable ordering. Each assignment induces a unique root-to-sink path, and local constraints depending on a bounded window of variables are handled by carrying a state summarizing the relevant history.
For Boolean functions with local interactions of bounded range $r$, the induced dependency graph over variables has pathwidth at most $r$. In that regime, dynamic programming over the BDD is equivalent to dynamic programming over a path decomposition, with state size exponential in $r$ but linear in the number of BDD nodes.
These principles are standard in weighted automata theory and in constraint satisfaction over bounded treewidth instances.
Partial argument
The expressions in the statement contain interactions of two types: linear terms $w_k x_k$, adjacent quadratic terms $w'k x_k x{k+1}$, and more generally length-$j$ monomials $x_k \cdots x_{k+j}$.
The key obstruction to the original BDD evaluation is that the contribution of a variable is not independent of previously chosen variables; the term $x_k x_{k+1}$ couples consecutive decisions, and higher-order monomials couple a sliding window of decisions.
To make evaluation compatible with BDD recursion, each node corresponding to variable $x_i$ must carry sufficient information to determine the contribution of all interaction terms that cross the boundary between already-assigned variables and unassigned variables. For interactions of maximum length $r+1$, it is sufficient to remember the last $r$ variable values along any root-to-node path.
This induces an augmented state space
$$ S = {0,1}^r, $$
representing the suffix of the partial assignment. At each branch node for variable $x_i$, the DP transition updates the state by shifting in the chosen value of $x_i$, and assigns incremental weight equal to the contribution of all monomials fully determined within the new window.
Each BDD node is then evaluated not by a scalar but by a function
$$ V_k : S \to \mathbb{R} \cup {-\infty}, $$
where $V_k(s)$ denotes the best achievable value in the sub-BDD rooted at node $k$ given boundary state $s$.
The recurrence at a node labeled $x_i$ with children LO and HI takes the form
$$ V_k(s) = \max \Big( V_{\mathrm{LO}}(\mathrm{shift}(s,0)) + \Delta_k(s,0), ; V_{\mathrm{HI}}(\mathrm{shift}(s,1)) + \Delta_k(s,1) \Big), $$
where $\Delta_k$ encodes contributions of all interaction terms whose support becomes fully determined at variable $x_i$.
For the pairwise case $x_k x_{k+1}$, the state reduces to a single bit, since only the previous variable matters. For length-$j$ interactions, the state is of size $j$.
This construction generalizes further to any objective that can be represented as a finite-state transducer driven by the variable ordering. The BDD then acts as the input graph, and evaluation becomes a shortest-path computation in the product of the BDD with the state machine.
The complexity becomes
$$ O(|\mathrm{BDD}| \cdot |S|), $$
where $|S|$ is the number of interaction states required by the objective function. The original Algorithms B and C correspond to the case $|S|=1$.
A further abstraction replaces explicit states by elements of an idempotent semiring enriched with finite memory, yielding an algebraic decision diagram whose node labels carry transition operators instead of scalar weights.
Status
The described framework is established in the literature under several equivalent guises: weighted automata over acyclic graphs, dynamic programming on bounded-treewidth constraint graphs, and algebraic or multi-terminal decision diagrams. The bounded-interaction cases in the statement fall inside this theory when the interaction width is fixed.
No single canonical formulation exists that strictly subsumes both BDD evaluation and all sliding-window polynomial objectives without introducing an explicit state space or equivalent automaton structure. The minimal representation problem for such generalized diagrams is not uniquely characterized in the same sense as reduced ordered BDDs, since different encodings of state lead to structurally different but functionally equivalent diagrams.
The extension therefore does not remain within pure BDD evaluation; it requires enrichment to state-augmented decision diagrams or equivalently to evaluation over finite-state weighted automata aligned with the variable order.
This completes the discussion. ∎