On Hop-Constrained Steiner Trees in Tree-Like Metrics

Abstract

We consider the problem of computing a Steiner tree of minimum cost under a 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 with 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 and bounded doubling dimension. For non-metric graphs, we rule out an $o(\log n)$-approximation, assuming P$\ne$NP even when relaxing the hop constraint by any additive constant.

References in corpus (2)

• A $(1+\epsilon )$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees