## 5 Numberlink Instance Enumeration  
This section presents an algorithm that enumerates all pair matchings \(h\) that give a good instance \((G,h)\) of the Numberlink problem for a given graph \(G\). Fixing \(G\), we say that a pair matching \(h\) is _good_ if \((G,h)\) is a good instance. Let us first consider an easier task, which enumerates all the instances that admit at least one solution. A solution for an instance of the Numberlink problem is a path matching and conversely every path matching \(P\) on \(G\) consisting of \(u_{i}\)-\(v_{i}\) simple paths for all \(i=1,\ldots,k\) is a solution for \((G,h_{P})\) where \(h_{P}\) consists of \(\{u_{i},v_{i}\}\) for all \(i=1,\ldots,k\). Our instance enumeration algorithm, shown as Algorithm 3, is again based on Algorithm 1, but now what we should enumerate is not edge sets but rather pair matchings. The ZDD \(Z_{G}\) output by Algorithm 1 will be a part of the input of Algorithm 3. For a valid path \(\pi\) in \(Z_{G}\), the corresponding path matching \(E(\pi)\) consists of two kinds of simple paths: fixed paths and unfixed paths. _Fixed paths_ are \(u\)-\(v\) paths where \(u,v\
otin V^{\geq e_{|\pi|+1}}=\mathrm{dom}(\mathrm{mate}_{n(\pi)})\). In other words, every fixed path in \(E(\pi)\) will be a constituent of any path matching represented as \(E(\pi\cdot\rho)\) (We note that whether a simple path in a path matching \(E(\pi)\) is fixed or unfixed depends on \(\pi\) rather than \(E(\pi)\) itself. Yet we prefer a concise phrasing relying on the reader's flexibility and assume that the vertex set in concern is understood.). We note that by definition \(\mathrm{mate}_{n(\pi)}\) does not tell us whether \(E(\pi)\) contains a fixed \(u\)-\(v\) path. On the other hand, the presence of an _unfixed_\(u\)-\(v\)_path_ is observed in the mate function. If a \(u\)-\(v\) path is unfixed, at least one of \(u,v\) is in \(V^{\geq e_{|\pi|+1}}=\mathrm{dom}(\mathrm{mate}_{n(\pi)})\). Without loss of generality, we assume \(u\in\mathrm{dom}(\mathrm{mate}_{n(\pi)})\), where we have \(\mathrm{mate}_{n(\pi)}(u)=v\). Since \(u\) has an incident edge in \(E^{\geq e_{|\pi|+1}}\), the path may be extended so that \(u\) has degree 2. ```
Data: A graph \(G=(V,E)\)
1 begin
2 let \(Z_{G}\) be the output by Algorithm 1 for \(G\);
3 let \(S_{n(\epsilon)}\leftarrow\{\emptyset\}\) and \(B_{n(\epsilon)}\leftarrow\emptyset\) for the root \(n(\epsilon)\) of \(Z_{G}\);
4 let \(N_{|E|+1}\leftarrow\{\mathbf{1}\}\);
5 foreach\(i=2,\ldots,|E|,|E|+1\)do
6 foreach\(n\in N_{i}\)do
7 let \(S_{n}\leftarrow\bigcup\{\,S_{n^{\prime},b}\mid n^{\prime}\in N_{i-1}\) is a \(b\)-parent of \(n\) };
8 let \(B_{n}\leftarrow\bigcup\{\,S_{n_{1},b_{1}}\cap S_{n_{2},b_{2}}\mid n_{j}\in N_{i -1}\) is a \(b_{j}\)-parent of \(n\) for \(j=1,2\) and \(n_{1}\
eq n_{2}\) }
9\(\cup\bigcup\{\,S_{n^{\prime},0}\mid n^{\prime}\) is a \(0\)-parent of \(n\) such that \(\mathrm{mate}_{n^{\prime}}(u)=u\) for some \(u\in e_{i}\setminus V^{\geq e_{i+1}}\) }
10\(\cup\bigcup\{\,B_{n^{\prime},b}\mid n^{\prime}\) is a \(b\)-parent of \(n\) };
11
12 end if
13
14 end for
15
16 return\(S_{\mathbf{1}}\setminus B_{\mathbf{1}}\);
17
18 end for
```  
**Algorithm 3**Numberlink Generator  
We prove the correctness of Algorithm 3 in Appendix C.  
Let \(T(\pi)\) denote the pair matching corresponding to the ends of fixed paths:  
\[T(\pi)=\{\,\{u,v\}\subseteq V\mid E(\pi)\text{ contains a $u$-$v$ path with $u,v\
otin V^{\geq e_{|\pi|+1}}$}\,\}\]  
Note that \(T(\pi)\subseteq T(\pi\cdot\rho)\) for any \(\pi\) and \(\rho\) as long as \(E(\pi\cdot\rho)\) is a path matching. We decorate each node \(n\) of the ZDD \(Z_{G}\) with the family  
\[S_{n}=\{\,T(\pi)\mid n(\pi)=n\,\}\]  
When a path \(\pi\) ends in \(\mathbf{1}\) in \(Z_{G}\), all the simple paths constituting \(E(\pi)\) are fixed. By definition, \(S_{\mathbf{1}}\) will be the family of pair matchings \(h\) such that \((G,h)\) admits a solution.