## 2 Basic Notions on ZDDs  
Since we do not treat BDDs, we only introduce ZDDs. ZDDs are graph representations for set families. Figure 1 illustrates the ZDD representing the set family \(\{\emptyset,\{e_{1}\},\{e_{2}\},\{e_{3}\}\}\). Whenever a ZDD is given, we always assume that a ground set \(S\) and the order of the elements are fixed. For simplicity, let \(S:=\{e_{1},\ldots,e_{n}\}\), where the elements are numbered from \(1\) to \(n\)\((=|S|)\) and ordered in this order. The node at the top is called the root. Each internal node has the three fields \(\mathrm{V}\), \(\mathrm{LO}\) and \(\mathrm{HI}\). The field \(\mathrm{V}\) holds the index of an element in \(S\). The fields \(\mathrm{LO}\) and \(\mathrm{HI}\) point to other nodes, which are called LO and HI children, respectively. The arc to a LO child is called a LO arc and illustrated by a dashed arrow, while the arc to a HI child is called a HI arc and illustrated by a solid arrow. There are only two non-internal nodes, denoted by \(\bot\) and \(\top\).  
Figure 1: The two graph representations for the same set family \(\{\emptyset,\{e_{1}\},\{e_{2}\},\{e_{3}\}\}\). (**a**) Binary Decision Tree; (**b**) ZDD.  
The following two conditions for ZDDs enable a unique and efficient representation. First, whenever an arc goes from an internal node \(f\) to an internal node \(g\), a ZDD must satisfy \(\mathrm{V}\left(f\right)<\mathrm{V}\left(g\right)\). Thus no nodes having the same index occur twice in a path. Second, a ZDD must be irreducible in the sense that the following reduction operations cannot be applied anymore.  
1. For each internal node \(f\) whose HI child is \(\bot\), redirect all the incoming arcs of \(f\) to the LO child of \(f\), and then eliminate \(f\) (Figure 2(a)).
2. Share all equivalent subgraphs (Figure 2(b)).  
Now, let us see the correspondence between ZDDs and set families. Given a ZDD, for each path \(P\) from the root to \(\top\), define a subset \(T_{P}\) of \(S\) such that \(e_{i}\in T_{P}\) if the HI arc of an internal node \(f\) is selected (where \(i=\mathrm{V}\left(f\right)\)); otherwise, \(e_{i}\
ot\in T_{P}\). Note that if \(P\) contains no nodes of index \(i\), then we can know that \(e_{i}\
ot\in T_{P}\) due to the node elimination rule. We obtain the set family \(\{T_{P}\colon P\) is a path in the ZDD\(\}\). Conversely, given a set family, construct the corresponding binary decision tree as is illustrated in Figure 1(a) and make it irreducible by applying the two reduction rules. Observe for example that Figure 1(b) is obtained from Figure 1(a). It is known (see [1,12] (SS7.1.4), for details) that every set family has one and only one representation as a ZDD if the size of a ground set and the order of the elements are fixed.  
For any node \(f\) in a ZDD, the graph consisting of all nodes accessible from \(f\) forms a ZDD whose root is \(f\). The size of a ZDD is the total number of nodes in the ZDD, including non-internal nodes. The cardinality of a node is the total number of paths from the node to \(\top\). Since in ZDDs we are interested in paths leading to \(\top\), we mean by a branch node an internal node whose two children have paths leading to \(\top\); in other words, the LO child is not \(\bot\). Note that a branch node is not a synonym of an internal node.