# Item

ITEM ACTIONSEXPORT

Released

Paper

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1811.03020.pdf

(Preprint), 502KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.

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.