## 3 ZDD for Path Matchings  
[PERSON] has proposed an algorithm that constructs a ZDD representing all the \(s\)-\(t\) paths on a given graph \(G\) and two vertices \(s\) and \(t\) in \(G\), as an answer to Exercise 225 in [13]. Based on [PERSON]'s algorithm, this section presents an algorithm that constructs in a topdown manner a ZDD \(Z_{G}\) representing all the path matchings over a graph \(G=(V,E)\). This algorithm prepares for our puzzle solvers. Let \(G=(V,E)\) be an undirected graph. The edge set \(E=\{e_{1},\ldots,e_{|E|}\}\) is the universal set of \(Z_{G}\), where we have \(e_{i}\leq e_{j}\) if and only if \(i\leq j\). We define \(E^{\geq e_{i}}=\{\,e_{j}\in E\mid e_{j}\geq e_{i}\,\}\). The root node \(n_{\mathrm{root}}\) of \(Z_{G}\) is labeled with \(e_{1}\) and if a node is labeled with \(e_{i}\) then its children are labeled with \(e_{i+1}\) unless they are terminal nodes, **0** or **1**. By \(N_{i}\) we denote the set of nodes with the label \(e_{i}\) for \(i=1,\ldots,|E|\). Hence \(N_{1}\) is the singleton of the root node \(n_{\mathrm{root}}\) and \(N_{i+1}\) consists of the children of nodes in \(N_{i}\). Every valid path ending in **1** has length \(|E|\) in \(Z_{G}\). For a \(0,1\)-sequence \(\pi\), we denote the length of \(\pi\) by \(|\pi|\). For \(\pi\) with \(|\pi|\leq|E|\), we define  
\[E(\pi)=\{\,e_{i}\in E\mid\text{the $i$th number of $\pi$ is $1$}\,\}\]  
We then have \(Z_{G}(\pi)=E(\pi)\) if \(\pi\) is a valid path in \(Z_{G}\). For a valid path \(\pi\), we let \(n(\pi)\) denote the node in which \(\pi\) ends. We have \(Z_{G}(n)=\{\,E(\pi)\mid n(\pi)=n\,\}\). The ZDD \(Z_{G}\) will be constructed so that  
\[E(\pi)\subseteq E\text{ is a path matching if and only if $\pi$ is valid in $Z_{G}$} \tag{1}\]  
Note that every subgraph of a path matching is a path matching. Our algorithm constructs \(Z_{G}\) in a top-down manner. The construction consists of \(|E|\) phases, where we create nodes in \(N_{i+1}\) as children of nodes in \(N_{i}\) in the \(i\)th phase. Figure 4 illustrates an example of \(G\) and \(Z_{G}\), which would help the reader understand our algorithm. We first initialize \(N_{i}\) to be empty for all \(i=2,\ldots,|E|\) and \(N_{1}\) to be the singleton of the root node \(n_{\mathrm{root}}\). We create nodes in \(N_{i}\) after the upper part of \(Z_{G}\) consisting of the nodes in \(\bigcup_{j<i}N_{j}\) and the arcs among them have been constructed for \(i=2,\ldots,|E|\). The algorithm stores some topological information of the path matching \(E(\pi)\) at the node \(n=n(\pi)\) reached by a valid path \(\pi\). Let \(|\pi|=i-1\), where we have \(n\in N_{i}\) and \(n\) is labeled by \(e_{i}\) unless \(n=\mathbf{1}\). We assign the node \(n\) a function \(\mathrm{mate}_{n}:V^{\geq e_{i}}\to V\cup\{0\}\), which we call a _mate function_, where \(V^{\geq e_{i}}=\bigcup E^{\geq e_{i}}\) and \(0\
otin V\). It is determined so that  
\[\mathrm{mate}_{n}(v)= \begin{cases}v&\text{if $v\
otin\bigcup E(\pi)$}\\ u&\text{if $E(\pi)$ contains a $u$-$v$ path}\\ 0&\text{otherwise}\end{cases}  \tag{2}\]  
for each \(v\in V^{\geq e_{i}}\). In other words, \(\mathrm{mate}_{n}(v)=v\) if \(v\) has degree 0 in \(E(\pi)\), and \(\mathrm{mate}_{n}(v)=0\) if \(v\) has degree 2 in \(E(\pi)\). Particularly for the root node \(n_{\mathrm{root}}\), we have \(\mathrm{mate}_{n_{\mathrm{root}}}(v)=v\) for all \(v\in V^{\geq e_{1}}\); the set \(V^{\geq e_{1}}\) is identical to \(V\), since \(G\) has no isolated vertices. The domain of a mate function \(\mathrm{mate}_{n}\) is restricted to \(V^{\geq e_{i}}\), which is the set of vertices to which at least one edge in \(E^{\geq e_{i}}\) is incident. We are not interested in the topological information on vertices that we will not visit any more. Note that \(V^{\geq e_{i}}=V^{\geq e_{i+1}}\cup e_{i}\). Hereafter we stipulate that \(V^{\geq e_{|E|+1}}\) denotes the empty set. In the example of Figure 4, we have \(V=V^{\geq e_{1}}=V^{\geq e_{2}}=\{p,q,r,s\}\), \(V^{\geq e_{3}}=e_{3}\cup e_{4}=\{q,r,s\}\) and \(V^{\geq e_{4}}=e_{4}=\{q,s\}\).