### Abstract

We consider the problem of computing a Steiner tree of minimum cost under a

*k*-hop constraint which requires the depth of the tree to be at most*k*. Our main result is an exact algorithm for metrics induced by graphs of bounded treewidth that runs in time*n*^{O(k)}. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if*k*is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the*k*-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension.Original language | English |
---|---|

Place of Publication | Ithaca, NY |

Publisher | arXiv.org |

Publication status | Published - 12 Mar 2020 |

### Fingerprint

### Keywords

- k-hop Steiner tree
- Dynamic programming
- Network design

### Cite this

Böhm, M., Hoeksma, R., Megow, N., Nölke, L., & Simon, B. (2020).

*Computing a Minimum-Cost*. Ithaca, NY: arXiv.org.*k*-hop Steiner Tree in Tree-Like Metrics