Survivable network design for group connectivity in low-treewidth graphs

Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

4 Sitaatiot (Scopus)
46 Lataukset (Pure)


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 {St}iϵ[h] : St ∪ 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 Si has a demand ki2 [k], k2 N, and we wish to find a minimum-cost subgraph H ∪ G such that, for each group Si, there is a vertex in the group that is connected to the root via ki (vertex or edge) disjoint paths. While GST admits O(log2 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 2log1-n-approximation unless NP ∪ DTIME(npolylog(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 ki 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 k3, 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 nf(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.

OtsikkoApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
ISBN (painettu)9783959770859
DOI - pysyväislinkit
TilaJulkaistu - 1 elok. 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems - Princeton, Yhdysvallat
Kesto: 20 elok. 201822 elok. 2018
Konferenssinumero: 21


NimiLeibniz International Proceedings in Informatics
KustantajaSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
ISSN (elektroninen)1868-8969


WorkshopInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems


Sukella tutkimusaiheisiin 'Survivable network design for group connectivity in low-treewidth graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä