FINDING DISJOINT PATHS WITH DIFFERENT PATH-COSTS - COMPLEXITY AND ALGORITHMS

Consider a network G = (V,E) with distinguished vertices s and t, and with k different costs on every edge. We consider the problem of finding k disjoint paths from s to t such that the total cost of the paths is minimized, where the jth edge-cost is associated with the jth path. The problem has several variants: The paths may be vertex-disjoint or arc-disjoint and the network may be directed or undirected. We show that all four versions of the problem are strongly NP-complete even for k = 2. We describe polynomial time heuristics for the problem and a polynomial time algorithm for the acyclic directed case.