## 4 Numberlink Solver  
This section presents a Numberlink solver, which constructs a ZDD that represents all the solutions for a given instance \((G,h)\) of Numberlink. Recall that a solution for an instance \((G,h)\) of Numberlinkis a path matching that satisfies a property represented by the pair matching \(h\). It is in fact rather easy to modify Algorithm 1 to obtain a Numberlink solver. Let us consider when we should connect an arc of a node to \(\mathbf{0}\) in addition to the cases we have discussed in Section 3. Suppose that we have chosen edges from \(\{e_{1},\ldots,e_{i}\}\) and by picking up other edges from \(E^{\geq e_{i+1}}\), we would like to form a solution. Let \(\pi\) be a \(0,1\)-sequence of length \(i\) that represents the choice. It is easy to see that if one of the following conditions holds, \(E(\pi)\cup P\) cannot be a solution of \((G,h)\) for any edge set \(P\subseteq E^{\geq e_{i+1}}\). * \(E(\pi)\) is not a path matching,
* there is \(v\in\bigcup h\) of degree \(2\) in \(E(\pi)\),
* there is \(v\in\bigcup h\setminus V^{\geq e_{i+1}}\) of degree \(0\) in \(E(\pi)\),
* there are \(u,v\in\bigcup h\) such that \(E(\pi)\) contains a \(u\)-\(v\) path and \(\{u,v\}\
otin h\),
* there is a vertex \(v\
otin\bigcup h\cup V^{\geq e_{i+1}}\) of degree \(1\) in \(E(\pi)\). Our Numberlink solver, shown as Algorithm 2, constructs a ZDD so that if a path \(\pi\) of length \(i\) satisfies one of the above, then (a prefix of) \(\pi\) leads to \(\mathbf{0}\). While Algorithm 1 connects no \(0\)-arcs to \(\mathbf{0}\), our Numberlink solver sometimes connects \(0\)-arcs to \(\mathbf{0}\) according to the above conditions. This judgement is realized by observing the mate functions. For a mate function \(m:V^{\geq e_{i}}\to V\cup\{0\}\) and an edge index \(i\), we say that \((m,i,0)\) is _incompatible with_\(h\) if for some \(v\in e_{i}\setminus V^{\geq e_{i+1}}\), one of the following conditions holds. * \(v\in\bigcup h\) and \(m(v)=v\),
* \(v\
otin\bigcup h\) and \(m(v)\
otin\{0,v\}\). When \((\mathrm{mate}_{n},i,0)\) is incompatible with \(h\) for \(n\in N_{i}\), the \(0\)-arc of \(n\) should be connected to \(\mathbf{0}\), since \(P=E(\pi\cdot 0)\cup E^{\prime}\) cannot be a solution for any \(E^{\prime}\subseteq E^{\geq e_{i+1}}\). In the first case, the degree of \(v\in\bigcup h\) is 0 in \(P\). In the second case, the degree of \(v\
otin\bigcup h\) is 1 in \(P\). ```
Data: A graph \(G=(V,E)\) and a pair matching \(h\) over \(V\)
1 begin
2 create a root node and two terminal nodes \(\mathbf{0}\) and \(\mathbf{1}\);
3 let \(N_{1}\leftarrow\{n_{\mathrm{root}}\}\) and \(N_{i}\leftarrow\emptyset\) for \(i=2,\ldots,|E|\);
4 foreach\(i=1,\ldots,|E|\)do
5 foreach\(n\in N_{i}\)do
6 if\((\mathrm{mate}_{n},i,0)\) is incompatible with \(h\)then let the 0-child of \(n\) be \(\mathbf{0}\);
7 else let the 0-child of \(n\) be \(\mathrm{GN}(i+1,\mathrm{mate}_{n}\big{|}_{V^{\geq e_{i+1}}})\);
8 if\((\mathrm{mate}_{n},i,1)\) is incompatible with \(h\)then let the \(1\)-child of \(n\) be \(\mathbf{0}\);
9 else let the 1-child of \(n\) be \(\mathrm{GN}(i+1,\mathrm{MU}(\mathrm{mate}_{n},e_{i})\big{|}_{V^{\geq e_{i+1}}})\);
10
11 end if
12
13 end foreach
14 return the constructed diagram;
15
16 end foreach
```  
**Algorithm 2**Numberlink solver  
We prove the correctness of Algorithm 2 in Appendix B. We say that \((m,i,1)\) is _incompatible with \(h\)_ if for \(e_{i}=\{u,v\}\), one of the following conditions holds. * \(m\) rejects \(e_{i}\), _i.e._, \(m(v)\in\{0,u\}\),
* \(v\in\bigcup h\) and \(m(v)\
eq v\),
* \(m(u),m(v)\in\bigcup h\cup(V\setminus V^{\geq e_{i+1}})\) and \(\{m(u),m(v)\}\
otin h\). When \((\mathrm{mate}_{n},i,1)\) is incompatible with \(h\) for \(n\in N_{i}\), the \(1\)-arc of \(n\) should be connected to \(\mathbf{0}\), since \(P=E(\pi\cdot 1)\cup E^{\prime}\) cannot be a solution for any \(E^{\prime}\subseteq E^{\geq e_{i+1}}\). In the first case, \(P\) is not a path matching. In the second case, \(v\) has degree more than 1 in \(P\).