Help Privacy Policy Disclaimer
  Advanced SearchBrowse





O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm


Laekhanukit,  Bundit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 502KB

Supplementary Material (public)
There is no public supplementary material available

Grandoni, F., Laekhanukit, B., & Li, S. (2018). O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm. Retrieved from http://arxiv.org/abs/1811.03020.

Cite as: https://hdl.handle.net/21.11116/0000-0002-A880-F
In the Directed Steiner Tree (DST) problem we are given an $n$-vertex
directed edge-weighted graph, a root $r$, and a collection of $k$ terminal
nodes. Our goal is to find a minimum-cost arborescence that contains a directed
path from $r$ to every terminal. We present an $O(\log^2
k/\log\log{k})$-approximation algorithm for DST that runs in
quasi-polynomial-time. By adjusting the parameters in the hardness result of
Halperin and Krauthgamer, we show the matching lower bound of
$\Omega(\log^2{k}/\log\log{k})$ for the class of quasi-polynomial-time
algorithms. This is the first improvement on the DST problem since the
classical quasi-polynomial-time $O(\log^3 k)$ approximation algorithm by
Charikar et al. (The paper erroneously claims an $O(\log^2k)$ approximation due
to a mistake in prior work.)
Our approach is based on two main ingredients. First, we derive an
approximation preserving reduction to the Label-Consistent Subtree (LCST)
problem. The LCST instance has quasi-polynomial size and logarithmic height. We
remark that, in contrast, Zelikovsky's heigh-reduction theorem used in all
prior work on DST achieves a reduction to a tree instance of the related Group
Steiner Tree (GST) problem of similar height, however losing a logarithmic
factor in the approximation ratio. Our second ingredient is an LP-rounding
algorithm to approximately solve LCST instances, which is inspired by the
framework developed by Rothvo{\ss}. We consider a Sherali-Adams lifting of a
proper LP relaxation of LCST. Our rounding algorithm proceeds level by level
from the root to the leaves, rounding and conditioning each time on a proper
subset of label variables. A small enough (namely, polylogarithmic) number of
Sherali-Adams lifting levels is sufficient to condition up to the leaves.