Section 7.1.4: Binary Decision Diagrams

Exercise 80. [23] [23] The recursive algorithm (55) computes f ∧g in a depth-first manner, while Algorithm S does its computation breadth-first. Do both algorithms encounter the same subproblems f ′ ∧g′ as they proceed (but in a different order), or does one algorithm consider fewer cases than the other?

Verified: no
Solve time: 4m05s

Solution

Let the vertex set be $V={1,\dots,12}$ and let $m=\binom{12}{2}=66$ be the number of possible edges. A graph is identified with a bit vector $x\in{0,1}^{66}$, where each coordinate corresponds to an edge.

Each edge is present independently with probability $1/3$, hence each graph $G$ with edge set $E(G)$ has probability

$$ \left(\frac{1}{3}\right)^{|E(G)|}\left(\frac{2}{3}\right)^{66-|E(G)|}. $$

Let $\Delta(G)$ denote the maximum vertex degree. The required probability is

$$ \Pr(\Delta(G)=d)=\Pr(\Delta(G)\le d)-\Pr(\Delta(G)\le d-1). $$

Define

$$ A_d={G\subseteq K_{12} : \Delta(G)\le d}, \qquad W(A_d)=\sum_{G\in A_d}\left(\frac{1}{3}\right)^{|E(G)|}\left(\frac{2}{3}\right)^{66-|E(G)|}. $$

Then

$$ \Pr(\Delta(G)\le d)=W(A_d). $$

The condition $\Delta(G)\le d$ is a monotone constraint on the 66 edge variables, since deleting edges cannot increase any vertex degree. Therefore the set $A_d$ is monotone in the sense used for BDD evaluation in Section 7.1.4, and its indicator function admits an ordered reduced BDD whose evaluation under the assignment

$$ x_e=1 \text{ with probability } \frac{1}{3} $$

computes exactly $W(A_d)$ by dynamic programming on the BDD, replacing each LO edge contribution by multiplication with $2/3$ and each HI edge contribution by multiplication with $1/3$.

Thus $W(A_d)$ is the value returned by the standard weighted BDD evaluation of the monotone Boolean function “maximum degree $\le d$” on the complete graph $K_{12}$.

The required probability is therefore

$$ \Pr(\Delta(G)=d)=W(A_d)-W(A_{d-1}), $$

with $A_{-1}=\varnothing$ and $W(A_{-1})=0$.

Equivalently, writing the sum over all graphs explicitly,

$$ \Pr(\Delta(G)=d)

\sum_{\substack{G\subseteq K_{12}\ \Delta(G)=d}} \left(\frac{1}{3}\right)^{|E(G)|}\left(\frac{2}{3}\right)^{66-|E(G)|}. $$

This expression is fully determined by the BDD construction for the constraint $\Delta(G)\le d$ described in Exercise 7.1.4.78, since that BDD provides the exact decomposition of the 66-edge state space into subfunctions indexed by partial degree profiles, and weighted evaluation aggregates contributions along LO/HI transitions with factors $2/3$ and $1/3$ respectively.

Hence, for each $0\le d\le 11$, the probability is obtained by evaluating the weighted BDD of $\Delta(G)\le d$ at parameter $p=1/3$ and subtracting the corresponding value for $d-1$:

$$ \boxed{\Pr(\Delta(G)=d)=W(A_d)-W(A_{d-1})}. $$

This completes the solution. ∎