2018-12-27 | Bundit Laekhanukit:An O(log^2{k}/log log {k})-Approximation Algorithm for Directed Steiner: A Tight Quasi-Polynomial-Time Algorithm



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 [STOC’03], 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. [SODA’98; J. Algorithms’99] (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 Rothvoss [Preprint, 2011]. 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.


This is a joint work with Fabrizio Grandoni and Shi Li.






Bundit Laekhanukit is currently an Associate Professor in the Institute for Theoretical Computer Science at the Shanghai University of Finance and Economics. He is originally from Thailand. He completed his Ph.D. from the McGill University in 2014 under the supervision of Adrian Vetta. After the completion of his Ph.D., he had been at the Swiss AI Lab IDSIA as a postdoctoral researcher under the supervision of Fabrizio Grandoni. He joined the Simons Institute for the Theory of Computing as a research fellow twice in Fall 2014 and Fall 2017 under Simons-ICORE and Simons-MPI joint fellowship programs. He spent two years at the Weizmann Institute for Science under the Simons-ICORE joint fellowship program, hosted by Uriel Feige and Robert Krauthgamer, and he spent two semesters at the Max-Planck-Institut für Informatik under the Simons-MPI joint fellowship program, hosted by Kurt Mehlhorn before officially joining SUFE.


His research interests lie in the intersection between approximation algorithms, the hardness of approximations, parameterized complexity, and fine-grained complexity. Shortly, he is interested in (but not limited to) understanding the interaction between the running time of algorithms and the approximation guarantees ones can achieve with perhaps dependency on some parameters of an input.