Beyond metric embedding: Approximating group steiner trees on bounded treewidth graphs

Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

6 Sitaatiot (Scopus)


The Group Steiner Tree (GST) problem is a classical problem in combinatorial optimization and theoretical computer science. In the Edge-Weighted Group Steiner Tree (EW- GST) problem, we are given an undirected graph G = (V;E) on n vertices with edge costs c : E , a source vertex s and a collection of subsets of vertices, called groups, S1S V . The goal is to find a minimum-cost tree H G that connects s to some vertex from each group Si, for all i = 1; 2 k. The Node-Weighted Group Steiner Tree (NW-GST) problem has the same setting, but the costs are associated with nodes. The goal is to find a minimum- cost node set X V such that G[X] connects every group to the source. When G is a tree, both EW-GST and NW-GST ad- mit a polynomial-time O(log n log k) approximation algorithm due to the seminal result of [Garg et al., SODA'98 and J. Algorithm]. The matching hardness of log2 n is known even for tree instances of EW-GST and NW-GST [Halperin and Krauthgamer STOC'03]. In general graphs, most of polynomial-time approximation algorithms for EW- GST reduce the problem to a tree instance using the metric- tree embedding, incurring a loss of O(log n) on the ap- proximation factor [Bartal, FOCS'96; Fakcharoenphol et al., FOCS'03 and JCSS]. This yields an approximation ratio of O(log2 n log k) for EW-GST. Using metric-tree embedding, this factor cannot be improved: The loss of (log n) is necessary on some input graphs (e.g., grids and expanders). There are alternative approaches that avoid metric-tree embedding, e.g., the algorithm of [Chekuri and Pal, FOCS'05], which gives a tight approximation ratio, but none of which achieves polylogarithmic approximation in polynomial-time. This state of the art shows a clear lack of understanding of GST in general graphs beyond the metric-tree embedding technique. For NW-GST (for which the metric-tree embed- ding does not apply), not even a polynomial-time polyloga- rithmic approximation algorithm is known. In this paper, we present O(log n log k) approximation algorithms that run in time n for both NW-GST and EW-GST1, where tw(G) denotes the treewidth of graph G. The key to both results is a different type of tree- embedding that produces a tree of much bigger size, but does not cause any loss on the approximation factor. Our embedding is inspired by dynamic programming, a technique which is typically not applicable to Group Steiner problems.

Otsikko28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
ISBN (elektroninen)9781611974782
TilaJulkaistu - 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM-SIAM Symposium on Discrete Algorithms - Barcelona, Espanja
Kesto: 16 tammik. 201719 tammik. 2017
Konferenssinumero: 28


ConferenceACM-SIAM Symposium on Discrete Algorithms


Sukella tutkimusaiheisiin 'Beyond metric embedding: Approximating group steiner trees on bounded treewidth graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä