## 4 A Fixed-Parameter Algorithm for \(\ell\)-LCDP\({}_{p}\)
: By Lemma 6, to test the existence of an \(\mathcal{L}\)-labelled \(g\)-colored \(st\)-path, it suffices to test the existence of a vertex \(v\) such that \(\{v,t\}\in E_{g}\) and \(M[\mathcal{L},v,g]\) is true. For a fixed color \(g\) and a fixed set \(L\) of labels, the time needed to evaluate \(M[L,v,g]\) for all \(v\in V\) is \(O(\left|E_{g}\right|)\) since each edge is considered only a constant number of times (twice, indeed). Since there exist \(2^{|\mathcal{L}|}\) distinct subsets of \(\mathcal{L}\), the overall time is \(O(2^{|\mathcal{L}|}\left|E_{g}\right|)\). The second recurrence, \(P[L]\), which, given an integer \(q\in[0,p]\) and a subset \(L\subseteq\mathcal{L}\) such that \(\left|L\right|=(\ell-1)q\), solves the \(L\)-labelled \(\ell\)-LCDP\({}_{q}\) problem, is defined as follows:  
\[P[L]= \begin{cases}1&\text{if }L=\varnothing\\ \max\left\{P[L^{\prime}]\;\wedge\;M[L^{\prime\prime},v,g]\;|\right.&\text{ otherwise}\end{cases}  \tag{4.2}\]  
Notice that we implicitly assume that the solution of the \(\varnothing\)-labelled \(\ell\)-LCDP\({}_{0}\) problem is always Yes (_i.e._, \(P[\varnothing]=1\)). Correctness of Equation 4.2, as proved in the following lemma, derives from Corollary 7, from the bound on the cardinality of \(L^{\prime\prime}\), and from the disjointness of \(L^{\prime}\) and \(L^{\prime\prime}\). **Lemma 8**. : _Given an edge-colored graph \(G_{C}\) and a vertex-labelling function \(\lambda:V\rightarrow\mathcal{L}\) with \(\left|\mathcal{L}\right|=(\ell-1)p\), then there exists an \(\mathcal{L}\)-labelled set \(\mathcal{S}\) of \(p\) disjoint uni-color \(st\)-paths of length at most \(\ell\) if and only if \(P[\mathcal{L}]\) is true._  
To prove this lemma, we first prove some intermediate results. **Property 9**. : _Let \(L_{i}\) and \(L_{j}\) be two disjoint subsets of \(\mathcal{L}\), let \(v_{i}\) and \(v_{j}\) be two distinct vertices, and \(g_{i}\) and \(g_{j}\) be two (possibly equal) colors. Then \(M[L_{i},v_{i},g_{i}]\) and \(M[L_{j},v_{j},g_{j}]\) are both true if and only if there exist two disjoint uni-color paths \(\pi_{i}\) and \(\pi_{j}\) from \(s\) to \(v_{i}\) and \(v_{j}\), respectively._  
Proof. : By Lemma 6, since both \(M[L_{i},v_{i},g_{i}]\) and \(M[L_{j},v_{j},g_{j}]\) are true, paths \(\pi_{i}\) and \(\pi_{j}\) exist labelled with set \(L_{i}\) and \(L_{j}\), respectively. Since \(L_{i}\) and \(L_{j}\) are disjoint, there could not exist a common vertex \(v\) (different from \(s\)), otherwise \(\lambda(v)\) would belong to both \(L_{i}\) and \(L_{j}\). Hence, \(\pi_{i}\) and \(\pi_{j}\) are disjoint. **Property 10**. : _The length of an \(L\)-labelled path \(\pi\) from \(s\) to a vertex \(v\
eq t\) is, at most, \(\left|L\right|\)._  
Proof. : All the vertices (but \(s\), which is not labelled) of \(\pi\) are labelled with distinct labels in \(L\), hence there could be at most \(\left|L\right|+1\) vertices in \(\pi\). Proof of Lemma 8.: We prove the correctness of \(P\) by induction on the number of paths \(p\). If \(p=0\), then \(\left|\mathcal{L}\right|=(\ell-1)p=0\). Thus, the base case applies and, since we assume that \(0\) paths always exist, it is also correct. Let us assume that \(P\) is correct for any \(p\leq k\) and let us prove its correctness for \(p=k+1\). First, we prove that if \(P[\mathcal{L}]\) is true, then a solution \(\mathcal{S}\) for \(\ell\)-LCDP\({}_{p}\) can be built. Notice that the second case of Equation 4.2 tries every possible bi-partition of set \(\mathcal{L}\) in two sets \(L^{\prime}\) and \(L^{\prime\prime}\) of cardinality \(\left|\mathcal{L}\right|-(\ell-1)\) and \(\ell-1\), respectively. If function \(P[\mathcal{L}]\) is true, then at least one of the bi-partitions verifies the givenconditions. Notice that \(|L^{\prime}|=|\mathcal{L}|-(\ell-1)=(\ell-1)(k+1)-(\ell-1)=(\ell-1)k\). Hence, by induction hypothesis, since \(P[L^{\prime}]\) is true, there exists an \(L^{\prime}\)-labelled set \(\mathcal{S}^{\prime}\) of \(k\) disjoint uni-color \(st\)-paths.