The Parameterized Complexity of the Survivable Network Design Problem

Andreas Emil Feldmann, Anish Mukherjee, Erik Jan van Leeuwen

For 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 $d_{s,t}$ fo…