Laekhanukit, Bundit
Approximating Directed Steiner Problems via Tree Embedding
Abstract
Directed Steiner problems are fundamental problems in Combinatorial Optimization and Theoretical Computer Science. An important problem in this genre is the kedge connected directed Steiner tree (kDST) problem. In this problem, we are given a directed graph G on n vertices with edgecosts, a root vertex r, a set of h terminals T and an integer k. The goal is to find a mincost subgraph H subseteq G that connects r to each terminal t in T by k edgedisjoint r, tpaths. This problem includes as special cases the wellknown 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], by Laekhanukit [SODA'14] and in a survey by Kortsarz and Nutov [Handbook of Approximation Algorithms and Metaheuristics], there was no known nontrivial approximation algorithm for kDST for k >= 2 even in a 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 kDST is not known even for a very strict special case that k=2 and h=2.
In this paper, we make a progress toward developing a nontrivial approximation algorithm for kDST. We present an O(D*k^{D1}*log(n))approximation algorithm for kDST on directed acyclic graphs (DAGs) with D layers, which can be extended to a special case of kDST on "general graphs" when an instance has a Dshallow optimal solution, i.e., there exist k edgedisjoint r, tpaths, each of length at most D, for every terminal t in 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 quasipolynomialtime (due to the heightreduction of Zelikovsky [Algorithmica'97]). Our algorithm is based on an LPformulation that allows us to embed a solution to a treeinstance of GST, which does not preserve connectivity. We show, however, that one can randomly extract a solution of kDST from the treeinstance of GST.
Our algorithm is almost tight when k and D are constants since the case that k=1 and D=3 is NPhard to approximate to within a factor of O(log(h)), and our algorithm archives the same approximation ratio for this special case. We also remark that the k^{1/4epsilon}hardness instance of kDST is a DAG with 6 layers, and our algorithm gives O(k^5*log(n))approximation for this special case. Consequently, as our algorithm works for general graphs, we obtain an O(D*k^{D1}*log(n))approximation algorithm for a Dshallow instance of the k edgeconnected directed Steiner subgraph problem, where we wish to connect every pair of terminals by k edgedisjoint paths.
BibTeX  Entry
@InProceedings{laekhanukit:LIPIcs:2016:6210,
author = {Bundit Laekhanukit},
title = {{Approximating Directed Steiner Problems via Tree Embedding}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {74:174:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6210},
URN = {urn:nbn:de:0030drops62100},
doi = {10.4230/LIPIcs.ICALP.2016.74},
annote = {Keywords: Approximation Algorithms, Network Design, Graph Connectivity, Directed Graph}
}
2016
Keywords: 

Approximation Algorithms, Network Design, Graph Connectivity, Directed Graph 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 