2017/02/09 by Ali Çivril, Çivril, Ali
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #VLSI and FPGA Design Techniques #cs.CC
paper · pdf · doi:10.48550/arxiv.1702.02882
openalex publication_date 2017/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The best algorithm for approximating Steiner tree has performance ratio ln(4)+ε≈ 1.386 [J. Byrka et al., Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 583-592], whereas the inapproximability result stays at the factor (96)/(95) ≈ 1.0105 [M. Chlebík and J. Chlebíková, 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 (19)/(18) ≈ 1.0555 unless \textsfP = NP. We also relate the problem to the Unique Games Conjecture by showing that it is \textsfUG-hard to find a constant approximation ratio better than (17)/(16) = 1.0625. In the special case of quasi-bipartite graphs, we prove an inapproximability factor of (25)/(24) ≈ 1.0416 unless \textsfP = NP, which improves upon the previous bound of (128)/(127) ≈ 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.