2017/01/11 by Manu Basavaraju, Basavaraju, Manu, Pranabendu Misra +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1701.02853
openalex publication_date 2017/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u,v∈ V(G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. In this paper, we consider the version of the problem where we are given a λ-edge connected (di)graph G with a non-negative weight function w on the edges and an integer k, and the objective is to find a minimum weight spanning subgraph H that is also λ-edge connected, and has at least k fewer edges than G. In other words, we are asked to compute a maximum weight subset of edges, of cardinality up to k, which may be safely deleted from G. Motivated by this question, we investigate the connectivity properties of λ-edge connected (di)graphs and obtain algorithmically significant structural results. We demonstrate the importance of our structural results by presenting an algorithm running in time 2O(k log k) |V(G)|O(1) for λ-ECS, thus proving its fixed-parameter tractability. We follow up on this result and obtain the \em first polynomial compression for λ-ECS on unweighted graphs. As a consequence, we also obtain the first fixed parameter tractable algorithm, and a polynomial kernel for a parameterized version of the classic Mininum Equivalent Graph problem. We believe that our structural results are of independent interest and will play a crucial role in the design of algorithms for connectivity-constrained problems in general and the SNDP problem in particular.