Improved Inapproximability Results for Steiner Tree via Long Code Based Reductions

Abstract

The best algorithm for approximating Steiner tree has performance ratio $\ln (4)+\epsilon \approx 1.386$ [J. Byrka et al., \textit{Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC)}, 2010, pp. 583-592], whereas the inapproximability result stays at the factor $\frac{96}{95}\approx 1.0105$ [M. Chlebík and J. Chlebíková, \textit{Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT)}, 2002, pp. 170-179]. In this article, we take a step forward to bridge this gap and show that there is no polynomial time algorithm approximating Steiner tree with constant ratio better than $\frac{19}{18}\approx 1.0555$ unless \textsf{P = NP}. We also relate the problem to the Unique Games Conjecture by showing that it is \textsf{UG}-hard to find a constant approximation ratio better than $\frac{17}{16}=1.0625$. In the special case of quasi-bipartite graphs, we prove an inapproximability factor of $\frac{25}{24}\approx 1.0416$ unless \textsf{P = NP}, which improves upon the previous bound of $\frac{128}{127}\approx 1.0078$. The reductions that we present for all the cases are of the same spirit with appropriate modifications. Our main technical contribution is an adaptation of a Set-Cover type reduction in which the Long Code is used to the geometric setting of the problems we consider.

arXiv commentThis was an early and insufficiently verified attempt. Errors affecting the main results were later identified, and the manuscript has been withdrawn