TAOCP 7.1.4 Exercise 244

Let the edges of $P_3$ be $e_1$ and $e_2$, where $e_1$ joins vertices $1$ and $2$, and $e_2$ joins vertices $2$ and $3$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 244. [25] [25] What is the ZDD for the connectedness function of P3 P3 (Fig. 22)? What is the BDD for the spanning tree function of the same graph? (See Corollary S.)

Verified: no
Solve time: 1m38s

Solution

Let the edges of $P_3$ be $e_1$ and $e_2$, where $e_1$ joins vertices $1$ and $2$, and $e_2$ joins vertices $2$ and $3$. Assume the variable order $e_1 < e_2$ throughout.

A subset of edges determines a subgraph of $P_3$. Connectedness of this subgraph is equivalent to the condition that the selected edges form a connected spanning subgraph on all three vertices.

For $P_3$, the edge subsets are

$\emptyset,\ {e_1},\ {e_2},\ {e_1,e_2}.$

The subsets $\emptyset$, ${e_1}$, and ${e_2}$ all leave at least one vertex isolated, hence each produces a disconnected subgraph. The subset ${e_1,e_2}$ produces a path on all three vertices and is connected. Therefore the connectedness function on edge sets is the indicator of the single set ${e_1,e_2}$.

The ZDD therefore represents the family

$\mathcal{F} = \bigl{{e_1,e_2}\bigr}.$

For a ZDD, each node at variable $e_i$ branches into LO (exclude $e_i$) and HI (include $e_i$). The zero-suppressed rule eliminates nodes whose HI edge points to $0$ when no solution contains that variable, but here every valid set contains both edges, so both variables are essential.

At the root $e_1$, no valid set excludes $e_1$, hence the LO branch must go to $0$. The HI branch proceeds to a node labeled $e_2$ representing the subfamily ${{e_2}}$ relative to having already included $e_1$.

At the node $e_2$, again no valid set excludes $e_2$, hence its LO branch goes to $0$, and its HI branch goes to $1$, representing completion of the unique set.

Thus the ZDD is

  • root $e_1$
  • $e_1.\mathrm{LO} = 0$
  • $e_1.\mathrm{HI} =$ node $e_2$
  • $e_2.\mathrm{LO} = 0$
  • $e_2.\mathrm{HI} = 1$

This structure is already reduced, since no node has identical LO and HI pointers and no duplicate $(V,\mathrm{LO},\mathrm{HI})$ triples occur.

Hence the ZDD has exactly two internal nodes and two terminals.

For the spanning tree function on $P_3$, every spanning tree of a connected graph on three vertices must contain exactly two edges, and for the path graph these must be both edges $e_1$ and $e_2$. Therefore the spanning tree indicator function is

$f(e_1,e_2) = e_1 \land e_2.$

We construct its BDD under the same variable order $e_1 < e_2$.

At the root node labeled $e_1$, the HI branch corresponds to $e_1=1$ and the LO branch to $e_1=0$. If $e_1=0$, the function value is $0$ regardless of $e_2$, hence the LO edge goes to the sink $\bot$.

If $e_1=1$, the function reduces to $e_2$, so the HI branch leads to a node labeled $e_2$.

At node $e_2$, the LO branch corresponds to $e_2=0$, giving $0$, hence it points to $\bot$. The HI branch corresponds to $e_2=1$, giving $1$, hence it points to $\top$.

No reduction is possible because the $e_2$ node has distinct LO and HI successors.

Thus the BDD is

  • root $e_1$
  • $e_1.\mathrm{LO} = \bot$
  • $e_1.\mathrm{HI} = e_2$
  • $e_2.\mathrm{LO} = \bot$
  • $e_2.\mathrm{HI} = \top$

The connectedness ZDD and the spanning-tree BDD are therefore both linear chains reflecting the fact that in $P_3$ there is exactly one connected spanning edge set and exactly one spanning tree, both equal to ${e_1,e_2}$.

$$ \boxed{\text{ZDD: single path } e_1 \to e_2 \text{ representing } {{e_1,e_2}}; \quad \text{BDD: } e_1 \land e_2 \text{ with chain } e_1 \to e_2} $$

∎