Chalermsook, Parinya ;
Das, Syamantak ;
Even, Guy ;
Laekhanukit, Bundit ;
Vaz, Daniel
Survivable Network Design for Group Connectivity in LowTreewidth Graphs
Abstract
In the Group Steiner Tree problem (GST), we are given a (edge or vertex)weighted graph G=(V,E) on n vertices, together with a root vertex r and a collection of groups {S_i}_{i in [h]}: S_i subseteq V(G). The goal is to find a minimumcost subgraph H that connects the root to every group. We consider a faulttolerant variant of GST, which we call Restricted (Rooted) Group SNDP. In this setting, each group S_i has a demand k_i in [k], k in N, and we wish to find a minimumcost subgraph H subseteq G such that, for each group S_i, there is a vertex in the group that is connected to the root via k_i (vertex or edge) disjoint paths.
While GST admits O(log^2 n log h) approximation, its higher connectivity variants are known to be LabelCover hard, and for the vertexweighted version, the hardness holds even when k=2 (it is widely believed that there is no subpolynomial approximation for the LabelCover problem [Bellare et al., STOC 1993]). More precisely, the problem admits no 2^{log^{1epsilon}n}approximation unless NP subseteq DTIME(n^{polylog(n)}). Previously, positive results were known only for the edgeweighted version when k=2 [Gupta et al., SODA 2010; Khandekar et al., Theor. Comput. Sci., 2012] and for a relaxed variant where k_i disjoint paths from r may end at different vertices in a group [Chalermsook et al., SODA 2015], for which the authors gave a bicriteria approximation. For k >= 3, there is no nontrivial approximation algorithm known for edgeweighted Restricted Group SNDP, except for the special case of the relaxed variant on trees (folklore).
Our main result is an O(log n log h) approximation algorithm for Restricted Group SNDP that runs in time n^{f(k, w)}, where w is the treewidth of the input graph. Our algorithm works for both edge and vertex weighted variants, and the approximation ratio nearly matches the lower bound when k and w are constants. The key to achieving this result is a nontrivial extension of a framework introduced in [Chalermsook et al., SODA 2017]. This framework first 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 highconnectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in lowtreewidth graphs.
BibTeX  Entry
@InProceedings{chalermsook_et_al:LIPIcs:2018:9412,
author = {Parinya Chalermsook and Syamantak Das and Guy Even and Bundit Laekhanukit and Daniel Vaz},
title = {{Survivable Network Design for Group Connectivity in LowTreewidth Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {8:18:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9412},
URN = {urn:nbn:de:0030drops94127},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.8},
annote = {Keywords: Approximation Algorithms, Hardness of Approximation, Survivable Network Design, Group Steiner Tree}
}
13.08.2018
Keywords: 

Approximation Algorithms, Hardness of Approximation, Survivable Network Design, Group Steiner Tree 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Issue date: 

2018 
Date of publication: 

13.08.2018 