An $n^{0.3+\epsilon }$-Approximation for Steiner $k$-Forest

Abstract

We give an $n^{0.3+\epsilon }$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\epsilon >0$. As a function of $n$, this improves over the $O(\min \{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt{k})$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\epsilon >0$, an $O(k^{1/2-\epsilon })$-approximation for Steiner $k$-Forest would surpass known degree-$n^{\Omega ({\epsilon }^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.