Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

Chao Liao, Qingyun Chen, Bundit Laekhanukit +1

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\in V$ a…