On the maximum disjoint paths problem on edge-colored graphs

We study the problem of finding the maximum number of disjoint uni-color paths in an edge-colored graph. We show the NP-hardness and the approximability and present approximation and exact algorithms. We also study the length-bounded version of the problem, in which the numbers of edges of the found paths are required to be upper bounded by a fixed integer ll. It is shown that the problem can be solved in polynomial time for l≤3l≤3 and is NP-hard for l≥4l≥4. We also show that the problem can be approximated with ratio (l−1)/2+ε(l−1)/2+ε in polynomial time for any ε>0ε>0. Particularly, for l=4l=4, we present an efficient 2-approximation algorithm.