On the Bidirected Cut Relaxation for Steiner Forest
Mathematical Programming · 12.08.2026
DOI: 10.1007/s10107-026-02407-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 12.08.2026. Verfasst von Jarosław Byrka und 2 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft, SNF, NCN.
Abstract (Originalsprache)
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.
Förderung
- Deutsche Forschungsgemeinschaft
- SNF
- NCN
Zitieren
APA
Byrka, J., Grandoni, F., & Traub, V. (2026). On the Bidirected Cut Relaxation for Steiner Forest. Mathematical Programming. https://doi.org/10.1007/s10107-026-02407-4
Vancouver
Byrka J, Grandoni F, Traub V. On the Bidirected Cut Relaxation for Steiner Forest. Mathematical Programming. 2026. doi:10.1007/s10107-026-02407-4
BibTeX
@article{Byrka2026,
author = {Byrka, Jarosław and Grandoni, Fabrizio and Traub, Vera},
title = {On the Bidirected Cut Relaxation for Steiner Forest},
journal = {Mathematical Programming},
year = {2026},
doi = {10.1007/s10107-026-02407-4}
}
EUVIMED