## 3 Approximation and Parameterized Complexity of Max CDP  
In this section, we present a reduction from Maximum Independent Set to Max CDP. Since the reduction preserves the solution cost, it implies that Max CDP is not approximable within factor \(c^{1-\varepsilon}\), for any \(\varepsilon>0\), and that CDP is W[1]-hard when the parameter is the size \(p\) of the solution. Given an undirected graph \(G_{I}=(V_{I},E_{I})\), the Maximum Independent Set (MaxIndSet) problem asks for an independent set \(I\subseteq V_{I}\) of maximum cardinality, _i.e._, a maximum-cardinality set \(I\) such that if \(v^{\prime},v^{\prime\prime}\in I\) then \(\{v^{\prime},v^{\prime\prime}\}\
ot\in E_{I}\). In the following, starting from a graph \(G_{I}\), we construct a gadget (an edge-colored graph) \(G_{C}\), such that finding an independent set \(I\) of cardinality \(k\) in \(G_{I}\) is equivalent to finding \(k\) disjoint uni-color \(st\)-paths in \(G_{C}\). First, we describe the edge-colored graph \(G_{C}\) associated with a generic graph \(G_{I}\), then we prove some properties of the computed gadget. Description of the gadget.Let \(G_{I}=(V_{I},E_{I})\) be an undirected graph, with \(V=\{v_{1},\ldots,v_{n}\}\) and \(E_{I}=\{e_{1},\ldots,e_{m}\}\). Without loss of generality, we assume that \(G_{I}\) is connected, since a maximumindependent set of a non-connected graph is the union of the maximum independent sets of its connected components. Let \(\Pi_{E_{I}}\) be an ordered list of the edges of \(G_{I}\), based on some ordering. We construct an edge-colored graph \(G_{C}=(V_{C},E_{1},\ldots,E_{n})\) associated with \(G_{I}\) as follows. Informally, the vertex set \(V_{C}\) is composed by two distinguished vertices \(s\) and \(t\) and a vertex for each edge of \(G_{I}\), while each set \(E_{i}\), \(1\leq i\leq c\), is composed connecting the vertices associated with edges of \(G_{I}\) incident to \(v_{i}\) in the same order as they appear in \(\Pi_{E_{I}}\). Formally, the set of colors is:  
\[C=\{1,\ldots,n\}\]  
Now, we define the vertex set \(V_{C}\):  
\[V_{C}=\{s,t\}\cup\{u_{i,j}\mid\{v_{i},v_{j}\}\in E_{I}\}\]  
Finally, we define the edge set \(E_{i}\), \(1\leq i\leq n\):  
\[E_{i}= \big{\{}\{u_{i,x},u_{i,y}\}\mid\text{no edge }\{v_{i},v_{z}\} \text{ appears between }\{v_{i},v_{x}\}\text{ and }\{v_{i},v_{y}\}\text{ in the list }\Pi_{E_{I}}\}\cup\] \[\big{\{}\{s,u_{i,j}\}\mid u_{i,j}\text{ is the first edge incident in }v_{i}\text{ of the list }\Pi_{E_{I}}\}\cup\] \[\big{\{}\{u_{i,j},t\}\mid u_{i,j}\text{ is the last edge incident in }v_{i}\text{ of the list }\Pi_{E_{I}}\}\]  
Figure 1 represents an example of an undirected graph \(G_{I}\) and of the edge-colored graph \(G_{C}\) associated with it. **Figure 1.** An example of a graph \(G_{I}\) and the edge-colored graph \(G_{C}\) associated with it. For convenience, we labelled the edges of \(G_{I}\) such as they correspond to the vertices in \(G_{C}\). The colors of the edges in \(G_{C}\) are indicated by numbers placed near the edges, while the two distinguished vertices \(s\) and \(t\) are highlighted in grey. The order \(\Pi_{E_{I}}\) of the edges of \(G_{I}\) is simply the lexicographic order of their labels. Given a graph \(G_{I}\) with \(n\) vertices and \(m\) edges, the associated edge-colored graph \(G_{C}\) has \(m+2\) vertices, \(O(mn)\) edges, and \(n\) colors, _i.e._, \(c=n\). Properties of the gadget.First, we introduce the following properties of the gadget. **Remark 1**. : _A uni-color \(st\)-path of color \(i\), with \(1\leq i\leq c\), contains each vertex \(u_{i,x}\) of \(G_{C}\) associated with an edge incident in \(v_{i}\in V_{I}\)._Proof. : The proof follows by construction, since the edges of color \(i\), with \(1\leq i\leq c\), induce a \(st\)-path that contains each vertex \(u_{i,x}\) of \(G_{C}\) associated with an edge incident in \(v_{i}\in V_{I}\) ordered as in list \(\Pi_{E_{I}}\). Next, we prove the two main results of the reduction from MaxIndSet to MaxCDP. **Lemma 2**.