Bundit
Laekhanukit,
Institute
for
Theoretical
Computer
Science
Shanghai
University
of
Finance
and
Economics
In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G=(V,E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connectivity requirement k>0; the goal is to find a minimum-cost subgraph H of G such that H has k edge-disjoint paths from the root r to each terminal t in T. The k-DST problem is a natural generalization of the classical Directed Steiner Tree problem (DST) in the fault-tolerant setting in which the solution subgraph is required to have an r,t-path, for every terminal t, even after removing k-1 vertices or edges.
Despite being a classical problem, there are not many positive results on the problem, especially for the case k >= 3. In this talk, we will present an O(log k log q)-approximation algorithm for k-DST when an input graph is quasi-bipartite, i.e., when there is no edge joining two non-terminal vertices. To the best of our knowledge, our algorithm is the only known non-trivial approximation algorithm for k-DST, for k >= 3, that runs in polynomial-time regardless of the structure of the optimal solution. In addition, our algorithm is tight for every constant k, due to the hardness result inherited from the Set Cover problem.
This is a joint work Chun-Hsiang (Kenny) Chan, Hao-Ting Wei and Yuhao Zhang.