On the Bidirected Cut Relaxation for Steiner Forest
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913602985787392 |
|---|---|
| author | Byrka, Jarosław Grandoni, Fabrizio Traub, Vera |
| author_facet | Byrka, Jarosław Grandoni, Fabrizio Traub, Vera |
| contents | 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. The current best approximation factor for Steiner Forest is 2, which is achieved by the classical primal-dual algorithm; improving on this factor is a big open problem in the area.
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 16/9. To prove this result we introduce a novel recursive densest-subgraph contraction algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06518 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Bidirected Cut Relaxation for Steiner Forest Byrka, Jarosław Grandoni, Fabrizio Traub, Vera Data Structures and Algorithms Discrete Mathematics 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. The current best approximation factor for Steiner Forest is 2, which is achieved by the classical primal-dual algorithm; improving on this factor is a big open problem in the area. 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 16/9. To prove this result we introduce a novel recursive densest-subgraph contraction algorithm. |
| title | On the Bidirected Cut Relaxation for Steiner Forest |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2412.06518 |