On the Bidirected Cut Relaxation for Steiner Forest

Abstract The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of vertices. The task is to compute a cheapest forest with the property that the elements of each pair belong to the same connected component of the forest. For a long time the best known approximation factor for Steiner Forest was 2, which is achieved by the classical primal-dual algorithm. Only very recently, the approximation ratio was improved to $$2-10^{-11}$$ 2 - 10 - 11 [Ahmadi, et al. FOCS’25], but the existence of an LP relaxation with better than 2 integrality gap remains open. Motivated by this open problem, we study an LP relaxation for Steiner Forest that generalizes the well-studied Bidirected Cut Relaxation for Steiner Tree. We prove that this relaxation has several promising properties. Among them, it is possible to round any half-integral LP solution to a Steiner Forest instance while increasing the cost by at most a factor $$\frac{16}{9}$$ 16 9 . To prove this result we introduce a novel recursive densest-subgraph contraction algorithm.