Chan, ChunHsiang ;
Laekhanukit, Bundit ;
Wei, HaoTing ;
Zhang, Yuhao
Polylogarithmic Approximation Algorithm for kConnected Directed Steiner Tree on QuasiBipartite Graphs
Abstract
In the kConnected Directed Steiner Tree problem (kDST), 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 minimumcost subgraph H of G such that H has k edgedisjoint paths from the root r to each terminal in T. The kDST problem is a natural generalization of the classical Directed Steiner Tree problem (DST) in the faulttolerant setting in which the solution subgraph is required to have an r,tpath, for every terminal t, even after removing k1 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 paper, we present an O(log k log q)approximation algorithm for kDST when an input graph is quasibipartite, i.e., when there is no edge joining two nonterminal vertices. To the best of our knowledge, our algorithm is the only known nontrivial approximation algorithm for kDST, for k ≥ 3, that runs in polynomialtime Our algorithm is tight for every constant k, due to the hardness result inherited from the Set Cover problem.
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2020:12666,
author = {ChunHsiang Chan and Bundit Laekhanukit and HaoTing Wei and Yuhao Zhang},
title = {{Polylogarithmic Approximation Algorithm for kConnected Directed Steiner Tree on QuasiBipartite Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {63:163:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12666},
URN = {urn:nbn:de:0030drops126667},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.63},
annote = {Keywords: Approximation Algorithms, Network Design, Directed Graphs}
}
11.08.2020
Keywords: 

Approximation Algorithms, Network Design, Directed Graphs 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 