EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the Bidirected Cut Relaxation for Steiner Forest

Jarosław Byrka, Fabrizio Grandoni, Vera Traub

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →