Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation...
summary
Claim: a quasi-polynomial-time algorithm achieves a polylogarithmic approximation for directed connectivity variants that require groups of terminals to reach a root (generalized directed Steiner/arborescence problems). It uses an LP relaxation with flow distributions, builds a metric-closure variant, applies probabilistic tree embedding and a dependent-rounding scheme to round fractional flows into trees, and maps those trees back to the original directed graph with bounded loss. The surprising point is polylog approximation in quasi‑polynomial time rather than polynomial time.
AI-written summary · about