29 września 2026 10:45
[Seminarium ZOK] Paul Paschmanns: The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
The Steiner Tree problem asks for the cheapest way of
connecting a given subset of the vertices in an undirected graph. One
of the most prominent linear programming relaxations for Steiner Tree
is the Bidirected Cut Relaxation (BCR). Determining the integrality
gap of this relaxation is a long-standing open question. For several
decades, the best-known upper bound was 2, which is achievable by
standard techniques. Only very recently, Byrka, Grandoni, and Traub
[FOCS 2024] showed that the integrality gap of BCR is strictly below
2. We prove that the integrality gap of BCR is at most 1.898,
improving significantly on the previous bound of 1.9988. For the
important special case where a terminal minimum spanning tree is an
optimal Steiner tree,
we show that the integrality gap is at most 12/7 by providing a tight
analysis of the dual-growth procedure by Byrka et al. To obtain the
general bound of 1.898 on the integrality gap, we generalize their
dual growth procedure to a broad class of moat-growing algorithms.
Moreover,
we prove that no such moat-growing algorithm yields dual solutions
certifying an integrality gap below 12/7. Finally, we observe an
interesting connection to the Hypergraphic Relaxation.
Joint work with Vera Traub.