## 2 Preliminaries  
### Zero-suppressed Binary Decision Diagrams  
A _zero-suppressed binary decision diagram_, ZDD for short, represents a family of sets over a universal set \(E\) whose elements are linearly ordered [12]. We index the elements of \(E\) as \(e_{1},\ldots,e_{|E|}\) where we write \(e_{i}\leq e_{j}\) if and only if \(i\leq j\). A ZDD is defined to be a labeled directed acyclic graph that satisfies the following properties. * There is only one node with indegree 0, called the _root node_. * There are just two nodes **0** and **1** with outdegree 0, called the _0-terminal_ and _1-terminal_. * Each node except terminals has just 2 outgoing arcs, which are labeled by \(0\) and \(1\) and called the _0-arc_ and _1-arc_, respectively. We call the node pointed by the \(j\)-arc of a node \(n\) the _\(j\)-child_ of \(n\). * Each node \(n\) except for the terminals is labeled by an element of \(E\). * The label of a non-terminal node is strictly smaller than those of its children. If a node \(n\) is the \(j\)-child of another node \(n^{\prime}\), we call \(n^{\prime}\) a _\(j\)-parent_ of \(n\) for \(j\in\{0,1\}\). We say that a path from the root node of a ZDD \(Z\) is _valid_ if it ends in a node which is not **0**. To each valid path \(\pi\) we assign a set \(Z(\pi)\subseteq E\) by  
\[Z(\pi)=\{\,e_{j}\mid\text{the 1-arc of a node labeled with $e_{j}$ appears in $\pi$}\,\}\]  
By representing a path from the root node of a ZDD by a sequence of \(0\) and \(1\), which we call a _\(0,1\)-sequence_, we have an alternative inductive definition of the set:  
\[Z(\pi\cdot 0) =Z(\pi)\] \[Z(\pi\cdot 1) =Z(\pi)\cup\{e\}\]  
where \(e\) is the label of the node in which \(\pi\) ends. Each node \(n\
eq\textbf{0}\) is assigned a set \(Z(n)\subseteq 2^{E}\) defined by  
\[Z(n)=\{\,Z(\pi)\mid\text{a valid path $\pi$ ends in $n$}\,\}\]  
An equivalent inductive definition is given by  
\[Z(n) =\{\,S\mid S\in Z(n^{\prime})\text{ for some $0$-parent $n^{\prime}$ of $n$}\,\}\] \[\quad\cup\{\,S\cup\{e\}\mid S\in Z(n^{\prime})\text{ for some $1$-parent $n^{\prime}$ of $n$ such that $n^{\prime}$ is labeled with $e$}\,\}\]  
The family of sets that a ZDD represents is defined to be \(Z(\textbf{1})\). Figure 3 shows an example of a ZDD. A ZDD is said to be _reduced_ if  
* there is no distinct nodes that have the same label, \(0\)-child and \(1\)-child,
* there is no node whose \(1\)-child is \(\mathbf{0}\). It is known that every ZDD admits a unique reduced one that represents the same family of sets. Moreover the number of nodes of a ZDD is minimum amongst ZDDs representing the same family if and only if it is reduced. A linear-time algorithm that reduces a ZDD can be found in [13, pp. 84-85, algorithm R]. A (reduced) ZDD can represent a family of sets in a compact way by letting multiple sets in the family share some subgraphs of the ZDD. If sets in the family have some \"regular\" structures, the size of the ZDD can be logarithmically smaller than the sum of the cardinalities of the sets in it. An even more important and widely appreciated virtue of ZDDs is that one can efficiently perform fundamental mathematical operations on families of sets over ZDDs, like union, intersection, _etc._ The efficiency depends on the size of the ZDDs rather than the cardinality of the sets in the target families. Some packages of implementation of ZDDs are provided to users of different purposes, where for given two ZDDs representing families of sets \(A\) and \(B\), it can compute the ZDD for \(A\cup B\), \(A\cap B\), \(A\setminus B\), \(A\oplus B\) and so on. For \(e\in E\), it can compute the ZDD for \(\{\,S\cup\{e\}\mid S\in A\,\}\), \(\{\,S\setminus\{e\}\mid S\in A\text{ and }e\in S\,\}\), \(\{\,S\mid S\in A\text{ and }e\
otin S\,\}\)_etc._ [PERSON] [13] has discussed further operations for families of sets, which enable us to extract maximal elements \(\{\,S\in A\mid\
eg\exists T\in A,\ S\subsetneq T\,\}\), minimal elements \(\{\,S\in A\mid\
eg\exists T\in A,\ T\subsetneq S\,\}\) among others.