1 of 32

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

FOCS 2025, Best Paper Award

Peyman Jabbarzade

Ali Ahmadi

Iman Gholami

Mohammad T. Hajiaghayi

Mohammad Mahdavi

2 of 32

Steiner Forest

Given a weighted graph
And a set of pairs of vertices

{(v₁, u₁), (v₂, u₂), (v₃, u₃), …}

v₁

u₁

v₂

u₂

u₃

v₃

3 of 32

Steiner Forest

Given a weighted graph
And a set of pairs of vertices

{(v₁, u₁), (v₂, u₂), (v₃, u₃), …}

Select a subset of edges to connect vertices in each pair

Minimize the total cost of selected edges

Generalization of Steiner Tree

v₁

u₁

v₂

u₂

u₃

v₃

4 of 32

Steiner Tree

Given a weighted graph
And a set of vertices as terminals

5 of 32

Steiner Tree

Given a weighted graph
And a set of vertices as terminals
Select a subset of edges to span the terminals

Minimize the total cost of selected edges

Generalization of MST

6 of 32

Previous Results

Steiner Tree

Trivial 2-approximation
11/6-approx. [Zel, Algorithmica’93]
1.65-approx. [KZ, J. Comb. Optim.’97]
1.55-approx. [RZ, SIAM J. Discret. Math.’05]
1.39-approx. [BGRS, STOC’10]

Steiner Forest

2-approx. [AKR, STOC’91]

Generalization and refinement [GW, SODA.’92]

96-approx. Greedy [GK, STOC’15]
69-approx. Local Search [GGKMSSV, ITCS’18]

7 of 32

Our Contribution

Steiner Tree

Trivial 2-approx.
11/6-approx. [Zel, Algorithmica’93]
1.65-approx. [KZ, J. Comb. Optim.’97]
1.55-approx. [RZ, SIAM J. Discret. Math.’05]
1.39-approx. [BGRS, STOC’10]

Steiner Forest

2-approx. [AKR, SIAM J. Comput’95]

Generalization and refinement [GW, SIAM J. Comput.’95]

96-approx. Greedy [GK, STOC’15]
69-approx. Local Search [GGKMSSV, ITCS’18]

Steiner Tree

1.94-approx. [AGHJM’25]

Steiner Forest

(2-10^-11)-approx. [AGHJM’25]

8 of 32

Our Algorithm Outline

9 of 32

Legacy Moat Growing Algorithm

The primal-dual 2-approximation algorithm

10 of 32

Basics

Edges are curves with length=cost
Maintain a forest

Initially empty

Active sets

Connected components need to extend

Active sets

Inactive sets

11 of 32

Moat Growing

Active sets color their adjacent edges

Edges with exactly one endpoint in them

Once an edge becomes fully colored

Add the edge to our forest

12 of 32

Moat Growing

Active sets color their adjacent edges

Edges with exactly one endpoint in them

Once an edge becomes fully colored

Add the edge to our forest
Merge its endpoints connected components
Continue grow together (if still active)

13 of 32

Pruning Phase

Remove redundant edges

14 of 32

Analysis

R: Total growth duration across all active sets
Optimal solution is at least R
Our solution is at most 2R
It is a 2-approximate solution

15 of 32

How to Improve the Result?

R: Total growth duration across all active sets
Optimal solution is at least R -> improve to (1+ε)R
Our solution is at most 2R -> improve to (2-ε)R
It is a 2-approximate solution -> (2-ε)-approximate solution
Reduce the total growth to obtain

Total growth < (1-ε)OPT

2OPT

OPT

total growth

our solution

16 of 32

Local Search

Incremental reduction on total growth

17 of 32

Boost Action

Select a vertex and a specific time

Let the vertex remains active until that time

Valuable boost action

Reduction in total growth is significantly larger than the boost amount

Apply any valuable boost action while one exists

Rerun the moat growing algorithm after each step

18 of 32

An Example on Steiner Tree

1+ε

19 of 32

Claw Property

For any set of three vertices

Upper bound the total growth corresponding to them
By (1-⍺) times the cost of any claw connecting them

Here, we are interested in a subtree of OPT

Proof

Boost action on the root is not valuable

2OPT

OPT

total growth

our solution

20 of 32

Generalized Claw Property

Generalize it to any number of vertices
Upper bound total growth corresponding to any set of vertices
By (1-⍺) times the cost of any tree connecting them

The subtree of the optimal solution

Only works if the vertices are connected in OPT and ours
For Steiner Tree

All terminals are connected in both solutions
Local search achieves 1.94-approximate solution

21 of 32

What About Stiner Forest?

If our components are similar to OPT

Each component is like a Steiner Tree instance
Everything is fine

Under-connectivity: We may connect less vertices than OPT

Extension

Over-connectivity: We may connect more vertices than OPT

Autarkic pairs

22 of 32

Extension

When vertices are under-connected

23 of 32

Extension

24 of 32

How Does It Help?

If under-connectivity fixed

Run Local Search
Use generalized claw property

Otherwise

Vertices in the same component of OPT must be far
The cost of OPT is already larger than the total growth

25 of 32

Autarkic Pairs

When vertices are over-connected

26 of 32

Example

n pairs

Cost: n+10

Cost: 2n+1

27 of 32

Autarkic Pair

Two group of unsatisfied vertices
Pair of each other
Vertices in each group grow only with each other
Their distance almost match their growth

28 of 32

Algorithm

Find autarkic pairs
Connect one pair of vertices from each group
Add a zero-cost edge
Rerun Legacy Moat Growing algorithm

29 of 32