2022/02/26 by Liao, Chao, Chen, Qingyun, Laekhanukit, Bundit +1
#68Q17 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2202.13088
In the k-connected directed Steiner tree problem (k-DST), we are given an n-vertex 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 minimum-cost subgraph H⊆ G that has k internally disjoint paths from the root vertex r to every terminal t∈ T. In this paper, we show the approximation hardness of k-DST for various parameters, which thus close some long-standing open problems. - Ω(|T|/log |T|)-approximation hardness, which holds under the standard 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 long-standing open problem. - Ω(√(2)k / k)-approximation hardness for the general case of k-DST under the assumption NP\neqZPP. 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 k-DST on L-layered graphs for L≤ O(log n). This almost matches the approximation ratio of O(kL-1⋅ L ⋅ log |T|) achieving in O(nL)-time due to Laekhanukit [ICALP`16].