Abstract
In the koutconnected directed Steiner tree problem (kDST), we are given an nvertex directed graph G = (V,E) with edge costs, a connectivity requirement k, a root r ∈ V and a set of terminals T ⊆ V. The goal is to find a minimumcost subgraph H ⊆ G that has k edgedisjoint paths from the root vertex r to every terminal t ∈ T. The problem is NPhard, and inapproximability results are known in several parameters, e.g., hardness in terms of n: log^{2ε}nhardness for k = 1 [Halperin and Krauthgamer, STOC'03], 2^{log^{1ε}n}hardness for general case [Cheriyan, Laekhanukit, Naves and Vetta, SODA'12], hardness in terms of k [Cheriyan et al., SODA'12; Laekhanukit, SODA'14; Manurangsi, IPL'19] and hardness in terms of T [Laekhanukit, SODA'14].
In this paper, we show the approximation hardness of kDST for various parameters.
 Ω(T/log T)approximation hardness, which holds under the standard complexity assumption NP≠ ZPP. The inapproximability ratio is tightened to Ω(T) under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021]. The latter hardness result matches the approximation ratio of T obtained by a trivial approximation algorithm, thus closing the longstanding open problem.
 Ω(2^{k/2} / k)approximation hardness for the general case of kDST under the assumption NP≠ZPP. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in k.
 Ω((k/L)^{L/4})approximation hardness for kDST on Llayered graphs for L ≤ O(log n). This almost matches the approximation ratio of O(k^{L1}⋅ L ⋅ log T) achieved in O(n^L)time due to Laekhanukit [ICALP'16].
We further extend our hardness results in terms of T to the undirected cases of kDST, namely the singlesource kvertexconnected Steiner tree and the kedgeconnected group Steiner tree problems. Thus, we obtain Ω(T/log T) and Ω(T) approximation hardness for both problems under the assumption NP≠ ZPP and the Strongish Planted Clique Hypothesis, respectively. This again matches the upper bound obtained by trivial algorithms.
BibTeX  Entry
@InProceedings{liao_et_al:LIPIcs.ICALP.2022.89,
author = {Liao, Chao and Chen, Qingyun and Laekhanukit, Bundit and Zhang, Yuhao},
title = {{Almost Tight Approximation Hardness for SingleSource Directed kEdgeConnectivity}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {89:189:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16430},
URN = {urn:nbn:de:0030drops164309},
doi = {10.4230/LIPIcs.ICALP.2022.89},
annote = {Keywords: Directed Steiner Tree, Hardness of Approximation, FaultTolerant and Survivable Network Design}
}
Keywords: 

Directed Steiner Tree, Hardness of Approximation, FaultTolerant and Survivable Network Design 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 