## 3 ZDD for Path Matchings
In the second case, \(\mathrm{mate}_{n}(w)=u\) means either that \(E(\pi)\) has a \(w\)-\(u\) path or that \(w=u\) and \(w\) is isolated in \(E(\pi)\). It is convenient for explanation to regard an isolated vertex \(t\) as a \(t\)-\(t\) path. According to this terminology, \(E(\pi)\) contains a \(w\)-\(u\) path and a \(v\)-\(\mathrm{mate}_{n}(v)\) path. Then the edge \(e_{i}=\{u,v\}\) will bridge those paths: \(E(\pi)\cup\{e_{i}\}\) contains a \(w\)-\(\mathrm{mate}_{n}(v)\) path (Figure 5(b)). The third case is similar to the second case. If none of those three cases apply, adding \(e_{i}\) does not matter for the vertex \(w\). We note that by the assumption, the first three cases are mutually exclusive. Summarizing the above, by observing \(\mathrm{mate}_{n}\), one can determine whether \(E(\pi\cdot 1)\) is a path matching or not. Moreover one can compute both \(\mathrm{mate}_{n^{\prime}}\) and \(\mathrm{mate}_{n^{\prime\prime}}\) for the \(0\)-child \(n^{\prime}\) and \(1\)-child \(n^{\prime\prime}\) of \(n\)  
Figure 5: updating mate. respectively, unless they are \(\mathbf{0}\) or \(\mathbf{1}\). Consequently, if two nodes \(n_{1}\) and \(n_{2}\) with the same label have the same mate function, their descendants will constitute subgraphs of exactly the same shape in \(Z_{G}\). This means that such equivalent nodes \(n_{1}\) and \(n_{2}\) should be merged before generating children. Our actual algorithm, shown as Algorithm 1, maintains each node set \(N_{i}\) not to contain distinct nodes assigned the same mate function. This is realized by a procedure named \(\mathrm{GN}\) (short for \"getting a node\") which takes two arguments: an edge index \(i\in\{1,\ldots,|E|\}\) and a mate function \(m\). \(\mathrm{GN}(i,m)\) returns a node labeled \(e_{i}\) and assigned \(m\). If such a node has already been created in \(N_{i}\), that node is returned. Otherwise, we create one in \(N_{i}\) and return it. It is conveniently assumed that \(\mathrm{GN}(|E|+1,m)\) gives the terminal node \(\mathbf{1}\). Note that this procedure may update \(N_{i}\). ```
Data: A graph \(G=(V,E)\) begin
1 create a root node and two terminal nodes \(\mathbf{0}\) and \(\mathbf{1}\);
2 let \(N_{1}\leftarrow\{n_{\mathrm{root}}\}\), \(N_{i}\leftarrow\emptyset\) for \(i=2,\ldots,|E|\) and \(\mathrm{mate}_{n_{\mathrm{root}}}\) be the identity on \(V\);
3 foreach\(i=1,\ldots,|E|\)do
4 foreach\(n\in N_{i}\)do
5 let the \(0\)-child of \(n\) be \(\mathrm{GN}(i+1,\mathrm{mate}_{n}|_{V^{\geq e_{i+1}}})\);
6 if\(\mathrm{mate}_{n}\)rejects\(e_{i}\)then let the \(1\)-child of \(n\) be \(\mathbf{0}\);
7 else let the 1-child of \(n\) be \(\mathrm{GN}(i+1,\mathrm{MU}(\mathrm{mate}_{n},e_{i})|_{V^{\geq e_{i+1}}})\);
8
9 end if
10
11 end for return the constructed diagram;
12
13 end for
```  
**Algorithm 1**Enumeration of path matchings  
For a node labeled \(e_{i}\) and assigned a mate function \(m\) which does not reject \(e_{i}\), the mate function of its \(1\)-child is given by \(\mathrm{MU}(m,e_{i})|_{V^{\geq e_{i+1}}}\) in Algorithm 1, which is determined in the way described in Equation (3). That is, \(\mathrm{MU}\) (short for \"mate update\") takes a mate function \(m\) and an edge \(e_{i}\) and returns a mate function defined by  
\[\mathrm{MU}(m,e_{i})(w)= \begin{cases}0&\text{ if }w\in e_{i}\text{ and }m(w)\
eq w\\ m(v)&\text{ if }e_{i}=\{v,m(w)\}\\ m(w)&\text{ otherwise}\end{cases} \]  
for each \(w\in\mathrm{dom}(m)\). The domain of \(\mathrm{MU}(m,e_{i})\) is the same as that of \(m\). By \(\mathrm{MU}(m,e_{i})|_{V^{\geq e_{i+1}}}\) we denote the subfunction of \(\mathrm{MU}(m,e_{i})\) whose domain is restricted to \(V^{\geq e_{i+1}}\). We prove the correctness of Algorithm 1 in Appendix A.