Approximating Directed Steiner Problems via Tree Embedding
Approximating Directed Steiner Problems via Tree Embedding
复制标题
通过树嵌入逼近定向斯坦纳问题
DOI：
10.4230/lipics.icalp.2016.74
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Bundit Laekhanukit
中科院分区：
文献类型：
--
作者：
Bundit Laekhanukit
在k-边连通有向Steiner树（k-DST）问题中，给定一个n阶有向图G，G的边代价为r，根点为r，终端数为h，k为整数。目标是找到G的一个最小代价子图H，它通过k条边不相交的r，t-路将r连接到每个终端t。这个问题包括作为特殊情况的著名的有向斯坦纳树（DST）问题（情况k = 1）和组斯坦纳树（GST）问题。尽管已经在文献中多次研究和提及，例如，由Feldman等人[SODA'09，JCSS'12]、Cheriyan等人[SODA'12，TALG'14]和Laekhanukit [SODA'14]，即使在输入图是有向无环的并且具有恒定层数的特殊情况下，也没有已知的用于k >= 2的k-DST的非平凡近似算法。如果输入图不是非循环的，则即使对于非常严格的特殊情况k= 2并且|不|= 2。
在本文中，我们取得了进展，发展一个非平凡的近似算法的k-DST。我们提出了具有D层的有向无环图（DAGs）上的k-DST的O（D k^{D-1} log n）-逼近算法，当实例具有D-浅最优解时，该算法可以扩展到“一般图”上k-DST的特殊情况，即，对于每个终端t，存在k条边不相交的r，t-路径，每条路径的长度至多为D。对于k= 1（DST）的情况，我们的算法产生了O（D log h）的近似比，因此意味着DST的O（log^3 h）近似算法在准多项式时间内运行（由于Zelikovsky的高度减少[Zelikica '97]）。因此，由于我们的算法适用于一般图，我们得到了一个O（Dk ^{D-1} log n）-近似算法的D-浅的情况下，k-边连接有向Steiner子图问题，我们希望连接每对终端的k-边不相交的道路。
In the k-edge connected directed Steiner tree (k-DST) problem, we are given a directed graph G on n vertices with edge-costs, a root vertex r, a set of h terminals T and an integer k. The goal is to find a min-cost subgraph H of G that connects r to each terminal t by k edge-disjoint r,t-paths. This problem includes as special cases the well-known directed Steiner tree (DST) problem (the case k = 1) and the group Steiner tree (GST) problem. Despite having been studied and mentioned many times in literature, e.g., by Feldman et al. [SODA'09, JCSS'12], by Cheriyan et al. [SODA'12, TALG'14] and by Laekhanukit [SODA'14], there was no known non-trivial approximation algorithm for k-DST for k >= 2 even in the special case that an input graph is directed acyclic and has a constant number of layers. If an input graph is not acyclic, the complexity status of k-DST is not known even for a very strict special case that k= 2 and |T| = 2.
In this paper, we make a progress toward developing a non-trivial approximation algorithm for k-DST. We present an O(D k^{D-1} log n)-approximation algorithm for k-DST on directed acyclic graphs (DAGs) with D layers, which can be extended to a special case of k-DST on "general graphs" when an instance has a D-shallow optimal solution, i.e., there exist k edge-disjoint r,t-paths, each of length at most D, for every terminal t. For the case k= 1 (DST), our algorithm yields an approximation ratio of O(D log h), thus implying an O(log^3 h)-approximation algorithm for DST that runs in quasi-polynomial-time (due to the height-reduction of Zelikovsky [Algorithmica'97]). Consequently, as our algorithm works for general graphs, we obtain an O(D k^{D-1} log n)-approximation algorithm for a D-shallow instance of the k-edge-connected directed Steiner subgraph problem, where we wish to connect every pair of terminals by k-edge-disjoint paths.