The parameterized complexity of the survivable network design problem

Andreas Emil Feldmann*, Anish Mukherjee, Erik Jan van Leeuwen

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Article number103604
JournalJournal of Computer and System Sciences
Volume148
Early online date13 Nov 2024
DOIs
Publication statusE-pub ahead of print - 13 Nov 2024

Bibliographical note

Publisher Copyright:
© 2024 Elsevier Inc.

Keywords

  • Fixed-parameter tractability
  • Survivable network design

Fingerprint

Dive into the research topics of 'The parameterized complexity of the survivable network design problem'. Together they form a unique fingerprint.

Cite this