Simultaneous Network Design With Restricted Link Usage

Abstract

ABSTRACT Given a digraph with two terminal vertices and as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to find a minimum‐cost subset of the arcs such that its intersection with each color class contains an ‐ dipath. Problems of this type arise naturally in multi‐commodity network design settings where each commodity is restricted to use links of its own color only. We also consider undirected versions and stricter exact variants, in which the intersection with each color class must itself be the required ‐ dipath or path. We study several variants of the problem, deriving strong hardness results even for restricted cases, but we also identify cases that can be solved in polynomial time. The latter ones include the cases where the color classes form a laminar family, or where the underlying digraph is acyclic and the number of color classes is constant. We also present FPT algorithms parameterized by the number of multi‐colored arcs or edges: for the superset variants in general, for the undirected exact‐existence variant, and for the directed exact‐existence variant on planar digraphs.