TY - GEN
T1 - Brief Announcement
T2 - 27th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS2025
AU - Asher, Omer
AU - Dinitz, Yefim
AU - Dolev, Shlomi
AU - Raviv, Li On
AU - Schieber, Baruch
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
PY - 2026
Y1 - 2026
N2 - We introduce and study a novel problem of computing a shortest path tree with the 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.
AB - We introduce and study a novel problem of computing a shortest path tree with the 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.
UR - https://www.scopus.com/pages/publications/105023159901
UR - https://www.scopus.com/pages/publications/105023159901#tab=citedBy
U2 - 10.1007/978-3-032-11127-2_7
DO - 10.1007/978-3-032-11127-2_7
M3 - Conference contribution
AN - SCOPUS:105023159901
SN - 9783032111265
T3 - Lecture Notes in Computer Science
SP - 76
EP - 81
BT - Stabilization, Safety, and Security of Distributed Systems - 27th International Symposium, SSS 2025, Proceedings
A2 - Bonomi, Silvia
A2 - Mandal, Partha Sarathi
A2 - Robinson, Peter
A2 - Sharma, Gokarna
A2 - Tixeuil, Sebastien
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 9 October 2025 through 11 October 2025
ER -