Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest

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 [Byrka, Grandoni, Rothvoß, and Sanità, 2010] (Best Paper award, STOC 2010).

The celebrated work of [Agrawal, Klein, and Ravi, 1989] (30-Year Test-of-Time award, STOC 2023), along with refinements by [Goemans and Williamson, 1992] (SICOMP'95), established a 2-approximation for Steiner Forest over 35 years ago. Jain's (FOCS'98) pioneering iterative rounding techniques 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-similar to Vertex Cover-might indeed be hard. Notably, fundamental works, including those by Gupta and Kumar (STOC'15) and Groß et al. (ITCS'18), introduced 96-and 69-approximation algorithms, possibly with the hope of paving the way for a breakthrough in achieving a constant-factor approximation below 2 for the Steiner Forest problem.

In this paper, we break the approximation barrier of 2 by designing a novel deterministic algorithm that achieves a 2 -10 -11 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.