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 j th edge‐cost is associated with the j th 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.