A simple Path-based LP Relaxation for Directed Steiner Tree
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914365104455680 |
|---|---|
| author | Pashkovich, Kanstantsin Pozzi, Marta Sanità, Laura |
| author_facet | Pashkovich, Kanstantsin Pozzi, Marta Sanità, Laura |
| contents | We study the Directed Steiner Tree (DST) problem in layered graphs through a simple path-based linear programming relaxation. This relaxation achieves an integrality gap of O(l log k), where k is the number of terminals and l is the number of layers, which matches the best known bounds for DST previously obtained via lift-and-project hierarchies. Our formulation bypasses hierarchy machinery, offering a more transparent route to the state-of-the-art bound, and it can be exploited to provide an alternative simpler proof that O(l) rounds of the Sherali-Adams hierarchy suffice for reducing the integrality gap on layered instances of DST. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_02825 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A simple Path-based LP Relaxation for Directed Steiner Tree Pashkovich, Kanstantsin Pozzi, Marta Sanità, Laura Data Structures and Algorithms Primary: 90C27 Secondary: 68W25, 90C05 We study the Directed Steiner Tree (DST) problem in layered graphs through a simple path-based linear programming relaxation. This relaxation achieves an integrality gap of O(l log k), where k is the number of terminals and l is the number of layers, which matches the best known bounds for DST previously obtained via lift-and-project hierarchies. Our formulation bypasses hierarchy machinery, offering a more transparent route to the state-of-the-art bound, and it can be exploited to provide an alternative simpler proof that O(l) rounds of the Sherali-Adams hierarchy suffice for reducing the integrality gap on layered instances of DST. |
| title | A simple Path-based LP Relaxation for Directed Steiner Tree |
| topic | Data Structures and Algorithms Primary: 90C27 Secondary: 68W25, 90C05 |
| url | https://arxiv.org/abs/2603.02825 |