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.
Original language | English |
---|---|
Article number | 103604 |
Journal | Journal of Computer and System Sciences |
Volume | 148 |
Early online date | 13 Nov 2024 |
DOIs | |
Publication status | E-pub ahead of print - 13 Nov 2024 |
Bibliographical note
Publisher Copyright:© 2024 Elsevier Inc.
Keywords
- Fixed-parameter tractability
- Survivable network design