2020/02/10 by Zeev Nutov, Nutov, Zeev
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2002.04048
openalex publication_date 2020/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. \bullet In the 1-Connectivity Augmentation problem the goal is to augment a connected graph by a min-size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural ratio of 2 for this problem and also for the more general Crossing Family Cover problem. \bullet In the 2-Connected Dominating Set problem we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm for this problem, with expected ratio O(σlog3 n), where σ=O(log n ⋅loglog n⋅(logloglog n)3). The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.