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

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
RedaktørerArtur Czumaj
ForlagAssociation for Computing Machinery
Publikationsdato2018
Sider2838-2850
ISBN (Elektronisk)978-1-61197-503-1
DOI
StatusUdgivet - 2018
BegivenhedTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2-018 - New Orleans, New Orleans, USA
Varighed: 7. jan. 201810. jan. 2018
Konferencens nummer: 29
https://www.siam.org/meetings/da18/

Konference

KonferenceTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2-018
Nummer29
LokationNew Orleans
LandUSA
ByNew Orleans
Periode07/01/201810/01/2018
Internetadresse

Fingeraftryk

Dyk ned i forskningsemnerne om 'Parameterized Algorithms for Survivable Network Design with Uniform Demands'. Sammen danner de et unikt fingeraftryk.

Citationsformater