## 4 A Fixed-Parameter Algorithm for \(\ell\)-LCDP\({}_{p}\)  
In this section, we study \(\ell\)-LCDP\({}_{p}\), the length-bounded (decision) version of Max CDP, which asks if there exist \(p\) uni-color disjoint \(st\)-paths of length at most \(\ell\). We show that \(\ell\)-LCDP\({}_{p}\) is fixed-parameter tractable when the parameters are \(\ell\) and \(p\) by presenting a parameterized algorithm based on the _color coding_ technique [8]. For an introduction to parameterized complexity see [6]. Notice that \(\ell\)-LCDP\({}_{p}\) is unlikely to admit fixed-parameter tractable algorithms when parameterized only by \(p\) or only by \(\ell\). Indeed in the latter case, \(\ell\)-LCDP\({}_{p}\) is already \(\mathrm{NP}\)-hard when \(\ell=4\)[3]. In the former case, we have proved in the previous section that CDP (hence \(\ell\)-LCDP\({}_{p}\), when \(\ell=n\)) is \(\mathrm{W}[1]\)-hard when parameterized by \(p\). Color coding is a technique initially introduced to design fixed-parameter algorithms for various restrictions of the subgraph isomorphism problem. It then gained popularity and it has been successfully applied to tackle the computational hardness of various problems on networks and graphs [9; 10; 11], on strings [12; 13], and problems of subset selection [14; 15]. The basic idea of the color coding technique applied on graph problems is, first, to \"color\" the vertices of the graph from a set of \(k\) colors (for an appropriate choice of the number \(k\) of colors), and, then, to find a solution of the given problem with the additional constraint that the vertices of the solution are colored with distinct colors (called a \"colorful\" or \"color coded\" solution), if such a solution exists. The process is re-iterated with a different coloring if a colorful solution is not found. The key theoretical result, which allows to obtain deterministic algorithms based on the color coding technique, is the deterministic construction of \(k\)-perfect families of hash functions. A family \(F\) of hash functions from a set \(U\) (the vertex set in the traditional applications of color coding) to the set \(\{1,\ldots,k\}\) of colors is \(k\)_-perfect_ if, for each subset \(U^{\prime}\) of \(U\) such that \(|U^{\prime}|=k\), there exists a hash function \(f\) in \(F\) such that \(U^{\prime}\) is colorful w.r.t. \(f\), _i.e._, \(f\) assigns a distinct label to each element of \(U^{\prime}\). In fact, if the given problem has a solution \(S\) of size \(k\), then there exists a hash function in \(F\) such that solution \(S\) is colorful. Hence, it suffices to test if there exists a colorful solution for one of the colorings given by the hash functions of the \(k\)-perfect family in order to guarantee the existence of a solution of the original problem, if such a solution exists. Crucial to the overall running time is the size of a \(k\)-perfect family and the time required to enumerate and evaluate the hash functions of the family. Currently, the best bounds (such as [8; 16; 17]) are, in general, explicit constructions of families of size \(2^{O(k)}\log^{O(1)}(|U|)\) in time proportional to their size. The description of the parameterized algorithm for the \(\ell\)-LCDP\({}_{p}\) problem is divided into two parts. First, we present a procedure that, given an edge-colored graph \(G_{C}\) and a vertex-coloring function \(\lambda\)verifies if in \(G_{C}\) there exist \(p\) disjoint uni-color \(st\)-paths long at most \(\ell\) and with the additional constraint that the inner vertices of the \(p\) paths are colored with distinct colors. Then, we show that, by exploiting well-known properties of families of perfect hash functions, the previous procedure can be used to solve the \(\ell\)-LCDP\({}_{p}\) problem in polynomial time (if \(p\) and \(\ell\) are parameters). In the following, to avoid ambiguities between vertex's and edge's colors, function \(\lambda\) will be called _vertex-labelling_ function (or, simply, a _labelling_ function) instead of the traditional term of coloring function.