On finding maximum disjoint paths with different colors : Computational complexity and practical LP-based algorithms

With the rapid development of wireless networks, the burden on data transmission is becoming much higher, so are the requirements for bandwidth and load balancing. To cope with these changing requirements, we investigate a novel problem of finding maximum disjoint paths with different colors (MDPDC). In MDPDC, transmission frequencies in a network are modeled as different colors on network nodes. The aim is to find a maximum number of color-constrained node-disjoint paths where nodes must share the same color within any disjoint path, and differ in color among different disjoint paths. For this proposed problem, we first prove MDPDC is NP-complete in both directed and undirected graphs. Then we provide two practical linear programming based solutions with theoretical justifications of their correctness and time complexity. Extensive computer experiments are also carried out with several compared baseline methods to demonstrate the effectiveness of proposed algorithms both in running time and solution quality