Parameterized Algorithms for Survivable Network Design with Uniform Demands

Jørgen Bang-Jensen, Kristine Vitting Klinkby Knudsen, Saket Saurabh, Manu Basavaraju, Pranabebdu Misra, Meirav Zehavi, M.S. Ramanujan

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruυ for every pair of vertices u, υ ∊ V(G). The objective is to construct a subgraph H of minimum weight which contains ruυ edge-disjoint (or node-disjoint) u-υ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem.

An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-Edge Connected Subgraph (λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-Vertex Connected Subgraph (λ-VCS) problem.

We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k) |V(G)|O(1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that λ-Ves is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Publication date2018
ISBN (Electronic)978-1-61197-503-1
Publication statusPublished - 2018
EventTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2-018 - New Orleans, New Orleans, United States
Duration: 7. Jan 201810. Jan 2018
Conference number: 29


ConferenceTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2-018
LocationNew Orleans
Country/TerritoryUnited States
CityNew Orleans
Internet address


Dive into the research topics of 'Parameterized Algorithms for Survivable Network Design with Uniform Demands'. Together they form a unique fingerprint.

Cite this