## 4 A Fixed-Parameter Algorithm for \(\ell\)-LCDP\({}_{p}\)
A dynamic-programming procedure for the \(\mathcal{L}\)-labelled \(\ell\)-LCDP\({}_{p}\) problem.Let \(G_{C}=(V,E_{1},\ldots,E_{c})\) be a \(C\)-edge-colored graphs with two distinguished vertices \(s\) and \(t\), and let \(\lambda\) be a labelling function which maps each vertex \(v\) of \(V\setminus\{s,t\}\) to a label \(\lambda(v)\) belonging to a set \(\mathcal{L}\) (we assume that \(\lambda\) assigns a distinct label to each vertex of a solution of \(\ell\)-LCDP\({}_{p}\)). Let \(L\subseteq\mathcal{L}\) be a fixed set of labels. A simple path \(\pi\) in \(G_{C}\) is _\(L\)-labelled_ if and only if the labels of its vertices (with the exclusion of \(s\) and \(t\)) are contained in \(L\) and are pairwise distinct. A set \(\{\pi_{1},\ldots,\pi_{k}\}\) of simple paths is _\(L\)-labelled_ if and only if there exists a partition \(\{L_{1},\ldots,L_{k}\}\) of \(L\) such that each \(\pi_{i}\) is \(L_{i}\)-labelled. We say that a path \(\pi\) is _\(g\)-colored_, with \(g\in C\), if all of its edges belong to set \(E_{g}\). The \(\mathcal{L}\)-labelled \(\ell\)-LCDP\({}_{p}\) problem, given \(G_{C}\) and \(\lambda:V\rightarrow\mathcal{L}\) with \(|\mathcal{L}|=(\ell-1)p\), asks if there exists an \(\mathcal{L}\)-labelled solution for the \(\ell\)-LCDP\({}_{p}\) problem on \(G_{C}\). We solve the \(\mathcal{L}\)-labelled \(\ell\)-LCDP\({}_{p}\) problem by combining two dynamic-programming recurrences. The first one, \(M[L,v,g]\), tests if, for a set of labels \(L\subseteq\mathcal{L}\), there exists an \(L\)-labelled \(g\)-colored path from vertex \(s\) to a vertex \(v\) different from \(t\). The second one, \(P[L]\), tests if, for a set of labels \(L\subseteq\mathcal{L}\) such that \(|L|=(\ell-1)q\) for some integer \(q\in[0,p]\), there exists a partition \(\{L_{1},\ldots,L_{q}\}\) of \(L\) in \(q\) subsets such that each set \(L_{i}\) labels a \(g_{i}\)-colored \(st\)-path of length \(l\leq\ell\). Recurrence for \(M[L,v,g]\) is defined as follows (where \(\uplus\) represents the disjoint union operator):  
\[M[L,v,g]= \begin{cases}1&\text{if $v=s$}\\ 0&\text{if $L=\varnothing$ and $v\
eq s$}\\ \max\big{\{}M[L^{\prime},u,g]\ |\ L=L^{\prime}\uplus\{\lambda(v)\}\wedge\{u,v \}\in E_{g}\big{\}}&\text{otherwise}\end{cases}  \tag{1}\]  
Correctness of the previous recurrence is proved by the following lemma. **Lemma 6**. : \(M[L,v,g]\) _is true if and only if there exists an \(L\)-labelled \(g\)-colored path from \(s\) to \(v\)._  
Proof. : The proof is by induction on the cardinality of \(L\). If \(|L|=0\), the base cases apply and a path which does not use any label exits if and only if \(v=s\). Now, assume that \(M[L,v,g]\) is correct for any \(L\) such that \(|L|\leq k\) (for some \(k\)) and we will prove the correctness of \(M[L^{\prime},v,g]\) for all \(L^{\prime}\) such that \(|L^{\prime}|=k+1\). Moreover, assume that \(v\
eq s\), since, otherwise, the first base case applies which is clearly correct. Then, an \(L^{\prime}\)-labelled \(g\)-colored path from \(s\) to \(v\
eq s\) exists if and only if (_i_) \(\lambda(v)\in L\) and (_ii_) there exists an \(L^{\prime\prime}\)-labelled \(g\)-colored path \(\pi\) from \(s\) to a vertex \(u\) such that \(\{u,v\}\in E_{g}\) and \(L^{\prime\prime}=L^{\prime}\setminus\{\lambda(v)\}\). Since \(|L^{\prime\prime}|=|L^{\prime}|-1=k\), path \(\pi\) exists if and only if \(M[L^{\prime\prime},u,g]\) is true. The inductive case of Equation 1 tests the above mentioned conditions, hence \(M[L^{\prime},v,g]\) is correct also for sets of labels \(L\) such that \(|L|=k+1\), concluding the proof. Clearly, \(M\) can be used to test if there exists an \(\mathcal{L}\)-labelled \(g\)-colored \(st\)-path, as illustrated by the following corollary. **Corollary 7**. : _The existence of an \(\mathcal{L}\)-labelled \(g\)-colored \(st\)-path can be tested in time \(O(2^{|\mathcal{L}|}\left|E_{g}\right|)\)._  
Proof.