TAOCP 7.1.4 Exercise 26
Algorithm C computes, for every node of the BDD, the number of satisfying assignments represented by the subgraph rooted at that node.
Section 7.1.4: Binary Decision Diagrams
Exercise 26. [M20] [M20] Modify Algorithm C so that it computes the reliability polynomial for given probabilities, namely F(p1, . . . , pn) = 1 x1=0 · · · 1 xn=0 (1 −p1)1−x1px1 1 . . . (1 −pn)1−xnpxn n f(x1, . . . , xn).
Verified: no
Solve time: 1m22s
Solution
Algorithm C computes, for every node of the BDD, the number of satisfying assignments represented by the subgraph rooted at that node. The recurrence is obtained by combining the values of the LO and HI successors with equal weight, because each remaining assignment is counted once.
To obtain the reliability polynomial, the same bottom-up traversal is used, but the quantity associated with each node is changed.
For every node $u$, let $R(u)$ denote the probability that the Boolean function represented by the subgraph rooted at $u$ evaluates to $\top$, assuming that the variables appearing at and below $u$ are independently true with probabilities $p_j$.
The sink values become
$$ R(\bot)=0,\qquad R(\top)=1. $$
Suppose that $u$ is a branch node whose variable is $x_j$, with successors
$$ \operatorname{LO}(u),\qquad \operatorname{HI}(u). $$
Condition on the value of $x_j$. If $x_j=0$, which occurs with probability $1-p_j$, evaluation continues at the LO successor. If $x_j=1$, which occurs with probability $p_j$, evaluation continues at the HI successor. Hence
$$ R(u) =(1-p_j),R(\operatorname{LO}(u)) +p_j,R(\operatorname{HI}(u)). $$
This recurrence replaces the addition step of Algorithm C. Every other part of the algorithm, including the reverse topological processing order of the nodes, remains unchanged.
The correctness proof is by induction on the height of the node.
For the basis, the two sink nodes satisfy
$$ R(\bot)=0,\qquad R(\top)=1, $$
which are exactly the probabilities