## 3 ZDD for Path Matchings
For \(\pi=1\cdot 1\), \(E(\pi)=\{e_{1},e_{2}\}\) is a path matching consisting solely of a \(q\)-\(r\) path. The domain of the mate function \(\mathrm{mate}_{n(\pi)}\) is \(V^{\geq e_{3}}=\{q,r,s\}\) and \(\mathrm{mate}_{n(\pi)}(q)=r\), \(\mathrm{mate}_{n(\pi)}(r)=q\) and \(\mathrm{mate}_{n(\pi)}(s)=s\). Let us consider the \(i\)th phase of our algorithm, where we already have constructed an incomplete ZDD until the nodes in \(N_{i}\). We determine the children of a node \(n(\pi)\in N_{i}\) for a valid path \(\pi\). The arcs given in this phase correspond to the choice whether or not we pick \(e_{i}\) in a path matching. Let \(n=n(\pi)\). Giving a \(0\)-child to \(n\) involves no difficulty. By assumption \(E(\pi)\) is a path matching and by definition \(E(\pi\cdot 0)=E(\pi)\). We create a node \(n^{\prime}\) in \(N_{i+1}\) as the \(0\)-child of \(n\) and label \(n^{\prime}\) by \(e_{i+1}\). That is, \(n(\pi\cdot 0)=n^{\prime}\). The mate function \(\mathrm{mate}_{n^{\prime}}\) of \(n^{\prime}\) should be identical to \(\mathrm{mate}_{n}\) except that the domain  
Figure 4: An example of \(G\) and \(Z_{G}\). \(\mathrm{dom}(\mathrm{mate}_{n^{\prime}})=V^{\geq e_{i+1}}\) may be smaller than \(\mathrm{dom}(\mathrm{mate}_{n})=V^{\geq e_{i}}\). In the case where \(i=|E|\), the \(0\)-child of \(n\) is \(\mathbf{1}\). On the other hand, \(E(\pi\cdot 1)\
eq E(\pi)\) and it is not always the case that \(E(\pi\cdot 1)\) is a path matching. If \(E(\pi\cdot 1)\) is not a path matching, the \(1\)-child of \(n\) should be \(\mathbf{0}\). Otherwise, we give a node \(n^{\prime\prime}\) with an appropriate mate function as the \(1\)-child of \(n\). We must decide whether \(E(\pi)\cup\{e_{i}\}\) is still a path matching or not. Let \(e_{i}=\{u,v\}\). We note that \(u\) and \(v\) are in the domain \(V^{\geq e_{i}}\) of \(\mathrm{mate}_{n}\). There exist several cases depending on the topology of \(E(\pi)\). Recall that an edge set \(P\subseteq E\) is a path matching if and only if the degree of every node in \(P\) is at most \(2\) and no subset \(P^{\prime}\subseteq P\) is a cycle. In the case where \(\mathrm{mate}_{n}(u)=0\), the degree of \(u\) in \(E(\pi)\) is \(2\), so the degree of \(u\) will be \(3\) in \(E(\pi)\cup\{e_{i}\}\), which is therefore not a path matching. The same holds when \(\mathrm{mate}_{n}(v)=0\). Moreover, if \(\mathrm{mate}_{n}(u)=v\) (equivalently \(\mathrm{mate}_{n}(v)=u\)), which means that \(E(\pi)\) contains a \(u\)-\(v\) path \(P_{u,v}\subseteq E(\pi)\), then \(E(\pi)\cup\{e_{i}\}\) contains a simple cycle \(P_{u,v}\cup\{e_{i}\}\). We say that a mate function \(m\)_rejects_ an edge \(\{u,v\}\) if \(m(u)\in\{0,v\}\) or \(m(v)\in\{0,u\}\). If \(\mathrm{mate}_{n}\) rejects \(e_{i}\), then \(E(\pi\cdot 1)\) is not a path matching, hence the \(1\)-child of \(n\) should be \(\mathbf{0}\). On the other hand, if \(\mathrm{mate}_{n}\) does not reject \(e_{i}\), \(E(\pi)\cup\{e_{i}\}\) is a path matching. So we need to give a node as the \(1\)-child of \(n\). Particularly in the case where \(i=|E|\), the \(1\)-child of \(n\) will be \(\mathbf{1}\). If \(i<|E|\), we create a node \(n^{\prime\prime}\) in \(N_{i+1}\) as the \(1\)-child of \(n\) (_i.e._, \(n^{\prime\prime}=n(\pi\cdot 1)\)) and assign a function \(\mathrm{mate}_{n^{\prime\prime}}\) that is consistent with the requirement of Equation (2). Actually one can compute \(\mathrm{mate}_{n^{\prime\prime}}\) from \(\mathrm{mate}_{n}\) and \(e_{i}=\{u,v\}\) by  
\[\mathrm{mate}_{n^{\prime\prime}}(w)= \begin{cases}0&\text{if $w\in e_{i}=\{u,v\}$ and $ \mathrm{mate}_{n}(w)\
eq w$}\\ \mathrm{mate}_{n}(v)&\text{if $\mathrm{mate}_{n}(w)=u$}\\ \mathrm{mate}_{n}(u)&\text{if $\mathrm{mate}_{n}(w)=v$}\\ \mathrm{mate}_{n}(w)&\text{otherwise}\end{cases}  \tag{3}\]  
for \(w\in\mathrm{dom}(\mathrm{mate}_{n^{\prime\prime}})=V^{\geq e_{i+1}}\). We explain why this is correct. The first case means that \(w\) has degree \(1\) in \(E(\pi)\). Hence, the degree of \(w\in e_{i}\) will be \(2\) in \(E(\pi)\cup\{e_{i}\}\) (Figure 5(a)).