ZDDs - Constructing ZDDs

Constructing ZDDs

Given a family $F$ of sets, we can find its ZDD as follows.

If $F = \emptyset$ ( $F$ is empty) return $⊥$ . If $F = ε$ ( $F$ contains only the empty set) then return $⊤$ .
Find the smallest element $v$ amongst all elements in all sets of $F$ . Create a node $v$ .
Let $F_{0}$ be the family of all sets in $F$ not containing $v$ , that is, $F_{0} = {α : α \in F, v \notin α}$ . Recursively construct the ZDD for $F_{0}$ , and connect the LO edge from $v$ to the root of $F_{0}$ .
Let $F_{1}$ be the family resulting from taking all sets in $F$ that contain $v$ and then removing $v$ from each set: $F_{1} = {α ∖ {v} : α \in F, v \in α}$ . Recursively construct the ZDD for $F_{1}$ , and connect the HI edge from $v$ to the root of $F_{1}$ .
Look for identical nodes (same label, same LO desination and same HI destination) and combine them.

Some families have special properties allowing their ZDDs to be immediately constructed. In a universe of size $n$ , consider for example the family of all sets of size $k$ which we denote $S_{k} ({1, . . ., n})$ . The ZDD of $S_{2} ({1,2,3}) = {{1,2}, {2,3}, {1,3}}$ is the following:

The ZDD of $S_{k} ({1, . . ., n})$ turns out to be easy to describe (exercise).

Here are some more examples. Let $U = {1, . . ., 6}$ . Then the ZDD of all sets containing exactly one of $S = {2,3,5}$ is:

The ZDD of all sets containing at least one element of $S$ is:

The ZDD of all sets containing at most one element of $S$ is:

These 3 examples are readily generalized. Each can be viewed as a ZDD of all sets that branches off at the smallest element of $S$ , before joining the main branch again after the largest element of $S$ has been handled.

In many combinatorial problems, we start with families that can be immediately written down. We then perform operations on these families to construct other families which we use to solve the problem. For example, given ZDDs $F$ and $G$ , we construct $F \cup G$ , or $F \cap G$ , or $F ⊔ G$ , or similar.