The Library
Parameterized algorithms for survivable network design with uniform demands
Tools
Bang-Jensen, Jørgen, Basavaraju, Manu, Vitting Klinkby, Kristine, Misra, Pranabendu, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket and Zehvi, Meirav (2018) Parameterized algorithms for survivable network design with uniform demands. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, Louisiana, USA, 7-10 Jan 2018. Published in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1-13. ISBN 9781611975031. doi:10.1137/1.9781611975031.180
|
PDF
WRAP-parameterized-algorithms-survivable-network-uniform-demands-Ramanujan-2018.pdf - Published Version - Requires a PDF viewer. Download (799Kb) | Preview |
|
PDF
WRAP-parameterized-algorithms-survivable-network-uniform-Ramanujan-2017.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (895Kb) |
Official URL: https://doi.org/10.1137/1.9781611975031.180
Abstract
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.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Computer networks., Computer algorithms., Computer science -- Statistical methods., Parameter estimation., Computational complexity. | ||||||||
Journal or Publication Title: | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||||
Publisher: | SIAM | ||||||||
ISBN: | 9781611975031 | ||||||||
Official Date: | 2018 | ||||||||
Dates: |
|
||||||||
Page Range: | pp. 1-13 | ||||||||
DOI: | 10.1137/1.9781611975031.180 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 28 November 2017 | ||||||||
Date of first compliant Open Access: | 19 January 2018 | ||||||||
RIOXX Funder/Project Grant: |
|
||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | New Orleans, Louisiana, USA | ||||||||
Date(s) of Event: | 7-10 Jan 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year