FOCS Conference 2025 Conference Paper
Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest
- Ali Ahmadi
- Iman Gholami
- MohammadTaghi Hajiaghayi
- Peyman Jabbarzade
- Mohammad Mahdavi
The Steiner Forest problem, also known as the Generalized Steiner Tree problem, is a fundamental optimization problem on edge-weighted graphs where, given a set of vertex pairs, the goal is to select a minimum-cost subgraph such that each pair is connected. This problem generalizes the Steiner Tree problem, first introduced in 1811, for which the best known approximation factor is 1. 39 by [Byrka, Grandoni, Rothvoβ, and Sanità, 2010]. The celebrated work of [Agrawal, Klein, and Ravi, 1989], along with refinements by [Goemans and Williamson, 1992], established a 2-approximation for Steiner Forest over 35 years ago. Pioneering iterative rounding techniques by [Jain, 1998] later extended these results to higher connectivity settings. Despite the long-standing importance of this problem, breaking the approximation factor of 2 has remained a major challenge, raising suspicions that achieving a better factor might indeed be hard. In this paper, we break the approximation barrier of 2 by designing a novel deterministic algorithm that achieves a $\mathbf{2} \mathbf{- 1 0}^{\mathbf{- 1 1}}$ approximation for this fundamental problem. As a key component of our approach, we also introduce a novel dual-based local search algorithm for the Steiner Tree problem with an approximation guarantee of 1. 943, which is of independent interest.