The parameterized complexity of the survivable network design problem

Abstract

In the well-known SURVIVABLE NETWORK DESIGN PROBLEM (SNDP), we are given an undirected graph G with edge costs, a set R of terminal vertices, and an integer demand ds,t for every terminal pair s,t∈R. The task is to compute a subgraph H of G of minimum cost, such that for every terminal pair s,t∈R there are at least ds,t disjoint paths between s and t in H. Depending on the type of disjointness, we obtain several variants of SNDP that have been widely studied in the literature: if the paths are required to be edge-disjoint we obtain EC-SNDP, while if they must be internally vertex-disjoint we obtain VC-SNDP. Another important case is the element-connectivity variant (LC-SNDP), where the paths must be disjoint on edges and non-terminals, i.e., they may only share terminals. In this work we shed light on the parameterized complexity of the above problems. We consider several natural parameters, which include the solution size ℓ, the sum of demands D, the number of terminals k, and the maximum demand dmax.