## 3 Approximation and Parameterized Complexity of Max CDP
: _Let \(G_{I}=(V_{I},E_{I})\) be an undirected graph and \(I\subseteq V_{I}\) be an independent (vertex) set for \(G_{I}\). Then, we can compute in polynomial time (at least) \(|I|\) disjoint uni-color \(st\)-paths in the edge-colored graph \(G_{C}\) associated with \(G_{I}\)._  
**Lemma 3**. : _Let \(G_{I}=(V_{I},E_{I})\) be an undirected graph and \(G_{C}\) be the edge-colored graph associated with \(G_{I}\). If there exist \(k\) disjoint uni-color \(st\)-paths in \(G_{C}\), then we can compute in polynomial time an independent set \(I\subseteq V_{I}\) for \(G_{I}\), with \(|I|=k\)._  
The first lemma is easily proved by showing that the uni-color \(st\)-paths associated with the vertices of the independent set \(I\) are pairwise disjoint. Conversely, the second lemma can be proved by showing that the vertices of \(G_{I}\) associated with the \(k\) uni-color \(st\)-paths of \(G_{C}\) form an independent set for \(G_{I}\). Proof of Lemma 2.: By construction, in \(G_{C}\) there exists a uni-color \(st\)-path associated with each vertex \(v\) of the original graph \(G_{I}\). We will show that the set \(P\) of paths of \(G_{C}\) associated with each vertex \(v\in I\) are internally disjoint. Let \(\pi_{i}\) and \(\pi_{j}\) be two paths of \(P\) associated with vertices \(v_{i}\) and \(v_{j}\), respectively, of \(I\). Notice that the two paths \(\pi_{i}\) and \(\pi_{j}\) connect the vertices which represent the edges of \(G_{I}\) incident to \(v_{i}\) and \(v_{j}\), respectively. Since \(I\) is an independent set in \(G_{I}\), no edge \(e^{\prime}\in E_{I}\) is incident to both \(v_{i}\) and \(v_{j}\) (i.e., \(u_{i,j}\
ot\in E_{I}\)), thus \(\pi_{i}\) and \(\pi_{j}\) are (internally) disjoint. Proof of Lemma 3.: Let \(P\) be the set of \(k\) disjoint uni-color \(st\)-paths of \(G_{C}\). Since each color is (bi-univocally) associated with a single path in \(G_{C}\) which, in turn, is (bi-univocally) associated with a single vertex of \(G_{I}\), we can define a set \(I\subseteq V_{I}\) that consists of the vertices of \(G_{I}\) associated with a path of \(P\). Clearly, \(|I|=|P|=k\). We claim that \(I\) is an independent vertex set for \(G_{I}\). Suppose that \(I\) is not an independent set, thus there exist two vertices \(v_{i},v_{j}\in I\) such that \(\{v_{i},v_{j}\}\in E_{I}\). Let \(u_{i,j}\) be the vertex of \(G_{C}\) representing edge \(\{v_{i},v_{j}\}\). Since \(v_{i},v_{j}\in I\), then there exist two paths \(\pi_{i},\pi_{j}\) in \(P\) associated with \(v_{i}\) and \(v_{j}\). By Remark 1, both paths must contain vertex \(u_{i,j}\) as an internal vertex, since edge \(\{v_{i},v_{j}\}\) is incident to both \(v_{i}\) and \(v_{j}\). Hence paths \(\pi_{i}\) and \(\pi_{j}\) are not internally disjoint, which contradicts our assumption and thus \(I\) is an independent set for \(G_{I}\). Consequences.Lemmas 2 and 3 prove the existence of an L-reduction [4] from MaxIndSet to MaxCDP with constants \(\beta=\gamma=1\). Hence, considering that, unless \(\mathrm{P}=\mathrm{NP}\), MaxIndSet cannot be approximated in polynomial time within factor \(|V_{I}|^{1-\varepsilon}\) for any constant \(\varepsilon>0\)[5], and that \(|V_{I}|=c\), the following theorem holds. **Theorem 4**. : _For any constant \(\varepsilon>0\), MaxCDP cannot be approximated within factor \(c^{1-\varepsilon}\) in polynomial time unless \(\mathrm{P}=\mathrm{NP}\)._  
This result greatly improves the previous inapproximability factor \(2-\varepsilon\) for MaxCDP [3] and, given the \(c\)-approximation algorithm presented in [3], it is the asymptotically optimal inapproximability ratio for MaxCDP. However, notice that the inapproximability factor \(2-\varepsilon\) for MaxCDP given in [3] holds even if \(c\) is a fixed constant, while in our reduction \(c\) is not fixed. From the parameterized complexity point of view, the reduction also implies the \(\mathrm{W}[1]\)-hardness of the decision problem CDP, as stated in the following theorem. **Theorem 5**.