On the Bidirected Cut Relaxation for Steiner Forest

• 成果类型: Article; Early Access
• 署名作者: Byrka, Jaroslaw; Grandoni, Fabrizio; Traub, Vera
• 署名单位: University of Wroclaw; Universita della Svizzera Italiana; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02407-4
• 发表日期: 2026-08-12
• 关键词: approximation algorithms; tree problem

摘要

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 [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 169 . To prove this result we introduce a novel recursive densest-subgraph contraction algorithm.