2018/02/28 by Chalermsook, Parinya, Das, Syamantak, Even, Guy +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1802.10403
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph G=(V,E) on n vertices, a root vertex r and a collection of groups \Si\i∈[h]: Si⊆ V(G). The goal is to find a min-cost subgraph H that connects the root to every group. We consider a fault-tolerant variant of GST, which we call Restricted (Rooted) Group SNDP. In this setting, each group Si has a demand ki∈[k],k∈\mathbb N, and we wish to find a min-cost H⊆ G such that, for each group Si, there is a vertex in Si connected to the root via ki (vertex or edge) disjoint paths. While GST admits O(log2 nlog h) approximation, its high connectivity variants are Label-Cover hard, and for the vertex-weighted version, the hardness holds even when k=2. Previously, positive results were known only for the edge-weighted version when k=2 [Gupta et al., SODA 2010; Khandekar et al., Theor. Comput. Sci., 2012] and for a relaxed variant where the disjoint paths may end at different vertices in a group [Chalermsook et al., SODA 2015]. Our main result is an O(log nlog h) approximation for Restricted Group SNDP that runs in time nf(k, w), where w is the treewidth of G. This nearly matches the lower bound when k and w are constant. The key to achieving this result is a non-trivial extension of the framework in [Chalermsook et al., SODA 2017], which embeds all feasible solutions to the problem into a dynamic program (DP) table. However, finding the optimal solution in the DP table remains intractable. We formulate a linear program relaxation for the DP and obtain an approximate solution via randomized rounding. This framework also allows us to systematically construct DP tables for high-connectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in low-treewidth graphs.