Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
复制标题
超越度量嵌入：在有界树宽图上近似群 Steiner 树
DOI：
10.1137/1.9781611974782.47
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Daniel Vaz
中科院分区：
文献类型：
--
作者：
Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Daniel Vaz
施泰纳树（GST）问题是组合优化和理论计算机科学的经典问题。边缘成本C：E→ℝ≥0，一个源顶点和一个称为组的子集的集合。 g每个组的si = 1，2。与节点相关的目标是找到一个最小成本节点集X v，使得[X]将每个组连接到源时。 o（log n log k）近似由于[Garg等，Soda'98和J.算法]的第二个结果，log2-n的匹配硬度甚至是EW-GST和NW-GST [Halperin和Krauthgamer Stoc' 03]。 96; Fakcharoenphol等人，focs'03和JCSS]。在某些输入图上是必要的（例如，网格和扩展器）。比率，但没有一个在多项式时间内实现多项式的近似值。 ）不适用），即使是多项式时期的多项式近似算法，我们在本文中都知道O（log n log k）近似算法，该算法在时间NO（TW（g）2）中运行NW-GST和EW-GST1都表示TW（g）表示Graph G的树宽。这两种结果的关键是不同类型的“ Tree-embedding”，它会产生更大尺寸的树，但不会导致任何尺寸近似因素的损失。
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 → ℝ≥ 0, a source vertex s and a collection of subsets of vertices, called groups, S1, . . . , Sk ⊆ 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 admit 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 approximation 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 embedding does not apply), not even a polynomial-time polylogarithmic approximation algorithm is known. In this paper, we present O(log n log k) approximation algorithms that run in time nO(tw(G)2) 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.