{"id":"arxiv:2509.06789","kind":"preprint","title":"The Steiner Shortest Path Tree Problem","authors":["Omer Asher","Yefim Dinitz","Shlomi Dolev","Li-on Raviv","Baruch Schieber"],"author_count":5,"year":2025,"published":"2025-09-08","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2509.06789","nct_id":null,"source_url":"https://arxiv.org/abs/2509.06789","archive_url":"https://space-kitty.com/papers/arxiv:2509.06789","updated":"2025-09-08","pmid":null,"pmcid":null,"openalex_id":"W4415056944","pdf_url":"https://arxiv.org/pdf/2509.06789","abstract":"We introduce and study a novel problem of computing a shortest path tree with a minimum number of non-terminals. It can be viewed as an (unweighted) Steiner Shortest Path Tree (SSPT) that spans a given set of terminal vertices by shortest paths from a given source while minimizing the number of nonterminal vertices included in the tree. This problem is motivated by applications where shortest-path connections from a source are essential, and where reducing the number of intermediate vertices helps limit cost, complexity, or overhead. We show that the SSPT problem is NP-hard. To approximate it, we introduce and study the shortest path subgraph of a graph. Using it, we show an approximation-preserving reduction of SSPT to the uniform vertex-weighted variant of the Directed Steiner Tree (DST) problem, termed UVDST. Consequently, the algorithm of [Grandoni et al., 2023] approximating DST implies a quasi-polynomial polylog-approximation algorithm for SSPT. We present a polynomial polylog-approximation algorithm for UVDST, and thus for SSPT, for a restricted class of graphs.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}