Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Chalermsook, Parinya; Das, Syamantak; Even, Guy; Laekhanukit, Bundit; Vaz, Daniel http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-94127
URL:

; ; ; ;

Survivable Network Design for Group Connectivity in Low-Treewidth Graphs

pdf-format:


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 minimum-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 S_i has a demand k_i in [k], k in N, and we wish to find a minimum-cost 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 Label-Cover hard, and for the vertex-weighted version, the hardness holds even when k=2 (it is widely believed that there is no subpolynomial approximation for the Label-Cover problem [Bellare et al., STOC 1993]). More precisely, the problem admits no 2^{log^{1-epsilon}n}-approximation unless NP subseteq DTIME(n^{polylog(n)}). 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 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 non-trivial approximation algorithm known for edge-weighted 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 non-trivial 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 high-connectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in low-treewidth 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 Low-Treewidth Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9412},
  URN =		{urn:nbn:de:0030-drops-94127},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.8},
  annote =	{Keywords: Approximation Algorithms, Hardness of Approximation, Survivable Network Design, Group Steiner Tree}
}

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: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI