## 1 Introduction  
Social networks are usually represented and studied as graphs. Vertices represent the elements analyzed (e.g., individuals), while edges represent a binary relation between the considered elements. Among the different properties considered to study such graphs, one of the most relevant is the vertex connectivity of two given vertices. Vertex connectivity is a measure of the information flowing from one vertex to the other, and it has many applications. For example, it is used for the identificationsof important structural properties of a social network, like group cohesiveness and centrality [1,2]. A classical result of graph theory, known as [PERSON]'s theorem, states that vertex connectivity is equivalent to the maximum number of disjoint paths between two given vertices.  
While a lot of interest has been put in the study of networks that represent a single type of relation, a natural extension that has been recently introduced in literature [3] is to consider multi-relational social networks, that is social networks where more than one kind of relation between elements of the network is considered. In order to investigate vertex connectivity in multi-relational social networks, the combinatorial problem known as _Maximum Colored Disjoint Paths_ (Max CDP) has been introduced in [3]. Max CDP asks for the maximum number of vertex-disjoint uni-color paths in an edge-colored graph, where the different edge-colors represent different kinds of relation.  
The computational and approximation complexity of Max CDP has been investigated in [3]. When the input graph contains exactly one color, Max CDP is polynomial time solvable (it can be reduced to the maximum flow problem), while it has been shown to be \(\mathrm{NP}\)-hard when the edges of the graph are colored. Moreover, Max CDP is shown to be approximable within factor \(c\), where \(c\) is the number of colors of the edges of the input graph, but not approximable within factor \(2-\varepsilon\), for any \(\varepsilon>0\), even when \(c\) is a fixed constant.  
In [3], it is also investigated a variant of the problem, denoted as \(\ell\)-LCDP, where the length of the paths in the solution are (upper) bounded by an integer \(\ell\geq 1\). The \(\ell\)-LCDP problem is \(\mathrm{NP}\)-hard, for \(\ell\geq 4\), while it admits a polynomial time algorithm when \(\ell\leq 3\). This variant of the problem can be approximated in polynomial time within factor \((\ell-1)/2+\varepsilon\).  
In this paper we investigate the approximation and parameterized complexity of Max CDP and \(\ell\)-LCDP. First, we show in Section 3 that Max CDP is not approximable within factor \(c^{1-\varepsilon}\), for any constant \(\varepsilon>0\), and that the corresponding decision problem (CDP) is \(\mathrm{W}[1]\)-hard when parametrized by the number \(p\) of disjoint uni-color paths. Then, in Section 4, we give a fixed-parameter algorithm for \(\ell\)-LCDP, when \(\ell\) and the number of disjoint uni-color paths are considered as parameters. Table 1 summarizes the results known about the complexities of these problems along with the new results presented in this work.  
\begin{table}
\begin{tabular}{l l l l} \hline \hline
**Problem** & **Parameter** & **Status** & **Ref.** \\ \hline Max CDP & \(c\) & \(\mathrm{NP}\)-hard for any \(c\geq 2\), & \\  & & \(c\)-approximable & \\  & & & Inapprox. within \(c^{1-\varepsilon}\) & **new** \\ \hline CDP & \(p\) & \(\mathrm{W}[1]\)-hard & **new** \\ \hline \(\ell\)-LCDP & \(\ell\) & \(\mathrm{NP}\)-hard for \(\ell\geq 4\) & [3] \\  & & & Poly-time for \(\ell\leq 3\) & [3] \\ \(\ell\)-LCDP\({}_{p}\) & \((\ell,p)\) & \(\mathrm{FPT}\) & **new** \\ \hline \hline \end{tabular}
\end{table}
Table 1: Complexity status of Max CDP.