The Steiner Shortest Path Tree Problem⋆

Omer Asher1 , Yefim Dinitz1 , Shlomi Dolev1 ,

Li-on Raviv2 , and Baruch Schieber3
1
Dept. of CS, Ben-Gurion Univ. of the Negev, Beer-Sheva, Israel
2
Gilat, Israel
3
Dept. of CS, New Jersey Inst. of Technology, Newark, NJ, USA
arXiv:2509.06789v1 [cs.DS] 8 Sep 2025

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 in-
troduce 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 al-
gorithm for UVDST, and thus for SSPT for a restricted class of graphs.

1 Introduction

Given an undirected or directed graph with nonnegative edge weights and a

source vertex s, a shortest path tree from s can be found by classic algorithms.
We introduce the problem of finding a shortest path tree that spans a given
set of vertices, called terminals, while minimizing the number of nonterminal
vertices in the tree. This problem is closely related to the classical unweighted
Steiner Tree problem, but differs in that it designates a root vertex and enforces
that all paths from the root to each terminal are the shortest. Due to this
relation, we term the problem the Steiner Shortest Path Tree problem (SSPT).
This problem is motivated by scenarios where shortest-path connections from
a source are essential and where reducing the number of intermediate vertices
helps limit cost, complexity, or overhead.
⋆
Partially supported by the Rita Altura trust chair in computer science, Frankel
center for computer science, BGU-NJIT Inst. for Future Technologies, the Israeli
Smart Transportation Research Center (ISTRC), and Israeli Science Foundation
(Grant No. 465/22).
2 Asher, Dinitz, Dolev, Raviv, and Schieber

1.1 Motivation
SSPT is a fundamental graph problem that has some obvious applications. One
such application is multicasting from a source (root) to a given set of termi-
nal nodes, while simultaneously minimizing latency by restricting paths to the
shortest and reducing the total number of bits transmitted by limiting the use
of nonterminal nodes. In the context of secure communication, it is desirable to
minimize the number of nonterminal nodes exposed to the multicast message
while still achieving the fastest possible delivery.
An additional optimization application is in hierarchical supply chain man-
agement [10]. Consider an airplane manufacturer with service centers located
in select airports (terminals). To minimize the ground time of airplanes, these
service centers must ensure the timely availability of repair parts. To replenish
the repair parts in these service centers, the manufacturer may use hierarchical
hubs. When a part is needed in a service center, it checks its availability in the
nearest hub in the hierarchy, which may be used to replenish parts in several
service centers. Designing the most cost-effective hierarchical supply chain from
a given set of potential hubs gives rise to the SSPT problem.

1.2 Our Results and Solution Approach

We prove that SSPT is NP-Hard. To obtain an approximation, we first intro-
duce and study the concept of the subgraph of shortest paths of a weighted
graph, which is the union of all the shortest paths from the source. Using this
concept, we show an approximation-preserving reduction of SSPT to the uni-
form vertex-weighted variant of the Directed Steiner Tree (DST) problem [1],
termed UVDST. By this reduction, any approximation for UVDST implies a
similar approximation for SSPT.
In particular, the DST algorithm of [1] achieves an O(k ε )-approximation in
polynomial time for any fixed ε > 0, where k is the number of terminals. The
DST algorithm of [9] achieves an O(log2 k/ log log k)-approximation in quasi-
polynomial time. Thus, the same results hold for SSPT.
We suggest a polynomial polylog-approximation algorithm solving UVDST
on polylogarithmically shallow graphs. For logarithmically shallow graphs, our
algorithm achieves an O(log2 k)-approximation ratio. We note that random graphs,
expander graphs, and Small World graphs (i.e., the Internet network) are poly-
logarithmically shallow graphs. We extend these results to SSPT, in which case
we require that there exists a polylogarithmically (or logarithmically) shallow
shortest path tree rooted at the source vertex. We extend these algorithms to
apply to the general vertex-weighted variant of DST, as well as to the weighted
variant of SSPT, achieving comparable performance as above on specific classes
of graphs.

1.3 Related Work

Our problem shares conceptual connections with various Steiner tree variants.
In the shallow-light tree problem [6], given an undirected graph and a root, the
 Shallowest Shortest Path Tree 3

goal is to construct a spanning tree in which the distance from the root to every
vertex is at most an α-approximation of the original distance in the input graph,
while the total weight of the tree is at most β times the weight of a minimum
spanning tree. Similarly, the shallow-light Steiner tree problem [6] generalizes
this to a designated subset of terminal vertices, and further allows the distance
bounds to be specified by an arbitrary metric, while its total weight must be
within a factor of β of the optimal Steiner tree. While shallow-light variants
focus on bounding stretch and minimizing total edge weight, SSPT minimizes
the number of nonterminal vertices under strict path constraints, which sets it
apart from the shallow-light family.
A related but distinct variant is the hop-constrained Steiner tree problem [8]
that introduces a constraint on the number of edges allowed in the path from
the root to each terminal, while still aiming to minimize the total weight of
the resulting tree. However, unlike SSPT, it permits any paths that satisfy the
hop constraint, regardless of whether they are the shortest paths. SSPT is more
restrictive in this regard, as it permits only the shortest paths and still aims to
minimize the number of nonterminal vertices.

2 SSPT Problem Definition and Hardness

Let us define the Steiner Shortest Path Tree (SSPT) problem. Its instance
(G, s, X) is an undirected or directed nonnegatively weighted graph G = (V, E, w),
w : E → R+ , where a source vertex s and a subset of vertices X, s ∈ / X, called
terminals, are distinguished. The goal is to find a shortest path tree w.r.t. w
from s to the terminals that has the minimum number of nonterminal vertices.
Note that the undirected and directed versions of SSPT are somewhat similar
to the undirected and directed Steiner tree problems, but with the specifics of
requiring the paths in feasible trees to be shortest. The weighted variant of SSPT
is obtained by assigning weights to the non-terminals and modifying the objec-
tive to be finding a shortest path tree that minimizes the overall weight of the
non-terminals.
Next, we prove that SSPT is NP-Hard by a reduction from the classic Set
Cover problem. The input to the Set Cover problem consists of a universal set
U and a set of its subsets, denoted S. The goal is to find a minimum cardi-
nality subset of S that covers U . Given an instance of the Set Cover problem,
the corresponding SSPT instance is constructed as follows. Consider the usual
representation of I by the bipartite graph with the sides S and U and the edges
(S, x) for all S ∈ S, x ∈ S. We add to it the vertex s with the edges (s, S) for all
S ∈ S. All edges are of weight 1. Observe that any tree rooted at s with edges
from s to S and from S to U only is a shortest path tree in G, and vice versa.
Thus, the reduction provides a natural one-to-one correspondence between the
feasible solutions of the instances of Set Cover and SSPT, while maintaining
the objective function value. Clearly, this correspondence keeps the optimality
of solutions, as required. Note that the approximation ratios of feasible solutions
are kept as well.
4 Asher, Dinitz, Dolev, Raviv, and Schieber

3 Shortest Path Subgraph

Consider a weighted, undirected or directed graph G = (V, E, w) with a vertex

s distinguished as its source. Many problems related to the shortest paths from
s to other vertices were studied over several decades. A reasonable approach to
pruning the input of some of these problems is to introduce the shortest path
subgraph rooted at s. We suggest and study such an object in this section.
The layered network data structure of the unweighted shortest paths from
s to a target vertex t was introduced by Dinitz in [3] and used as the basis of
Dinitz’s network flow algorithm [3] and many following network flow algorithms.
Its generalization to the layered network data structure of the shortest paths
from s to all other vertices had been briefly described at the end of the original
paper [3] and was elaborated and widely developed by Goldberg and Tarjan as
the basis for the push-relabel network flow algorithm [7].
The generalization of the layered network to the case of weighted graphs was
suggested by Dinitz et al. in [4] for the shortest paths from s to a fixed vertex t.
Here, we generalize the approach of [4] to the shortest paths from s to all other
vertices of G. We consider G to be a directed graph (digraph). Note that this
also covers the case of undirected graphs, by the usual reduction that replaces
every undirected edge by the pair of oppositely directed edges between the same
vertices.
For any pair of vertices x and y, we denote by d(x, y) the distance, that is,
the length of the shortest path from x to y in G. We also use the abbreviation
d(v) = d(s, v). We define the shortest path subgraph rooted at s, G̃(s), as the
union of all shortest paths from s to all other vertices in G.

Theorem 1. 1. The subgraph G̃(s) consists of all vertices reachable from s in

G and all edges (u, v) ∈ E satisfying d(u) + w(u, v) = d(v).
2. Any path from vertex x to vertex y in G̃(s) has weight d(y) − d(x) and is a
shortest path from x to y in G.

Proof. (1) The substatement on the vertices of G̃(s) is straightforward. Any edge
(u, v) in a shortest path satisfies d(u)+w(u, v) = d(v) due to the known property
of any prefix of a shortest path from s being a shortest path to its end-vertex.
Suppose that (u, v) satisfies d(u) + w(u, v) = d(v). Let P be a shortest path
from s to u. Appending (u, v) to P , we obtain a path from s to v of length
d(u) + w(u, v) = d(v), which is a shortest one. Hence, the edge (u, v) is in G̃(s).
(2) Consider a path P in G̃(s) from x to y. Let P = (x = v0 , v1 , v2 , . . . , vk =
y). Then, w(P ) = w(v0 , v1 ) + w(v1 , v2 ) + · · · + w(vk−1 , vk ) = (d(v1 ) − d(v0 )) +
(d(v2 ) − d(v1 )) + · · · + d(vk ) − d(vk−1 ) = d(vk ) − d(v0 ) = d(y) − d(x), as required.
Assume, to contrary, that there is a path P ′ : w(P ′ ) < w(P ) = d(y) − d(x),
from x to y in G. Since x is reachable from s, there exists path Px : w(Px ) = d(x),
in G. Then, the concatenation of Px and P ′ is a path from s to y of weight
w(Px ) + w(P ′ ) < d(x) + (d(y) − d(x)) = d(y) in G, a contradiction to the
definition of d(y). ⊓
⊔
 Shallowest Shortest Path Tree 5

Let us describe some properties of the shortest path subgraph G̃(s). By The-
orem 1, G̃(s) can be constructed by the execution of algorithm Dijkstra and a
simple scan of G; thus, the construction time is dominated by the running time
of algorithm Dijkstra, which is known to be almost linear in the size of G (see a
recent algorithm in [5]).
Secondly, by Theorem 1(1), the condition on a path P from s to be shortest
in G is equivalent to the condition that P is in G̃(s). This relation can simplify
the shortest path-related problems. In particular, any instance (G, s, X) of the
SSPT problem is equivalent to finding, in the unweighted digraph G̃(s), a tree
rooted at s and spanning X with a minimum number of nonterminal vertices
in it. This equivalence gives rise to the reduction of SSPT that we present in
Section 4.1.
We can use a visual layout of G where each vertex v is placed at a plane
point with the horizontal coordinate d(v). Note that if all edge weights are 1,
then the graph G̃ is layered : the vertices are arranged in layers by the integer
horizontal coordinates and every edge goes from one layer to the next. If the
edge weights are positive, then every edge goes from left to right; consequently,
the graph G̃ is acyclic. It is also acyclic in the case where the edge weights are
nonnegative and there is no cycle consisting of edges with weights zero only in
G. In the general case, there may be nontrivial strongly-connected components
of G̃(s) containing edges of weight zero only.
We stress that the shortest path subgraph G̃(s) is a digraph even if G is
undirected. To see why, consider the following example. Let G be an undirected
4-cycle (s, v1 , v2 , v3 ) with all edge weights 1. Note that the two undirected paths
(s, v1 , v2 ) and (s, v3 , v2 ) are shortest. Thus, G̃(s) is composed of these two di-
rected paths. If we remove the edge directions, we could reach v3 via the path
(s, v1 , v2 , v3 ) in the updated G̃(s), but this path is not shortest, contradicting
Theorem 1(2).
We can refine the pruning of G to G̃(s) for some problems related to shortest
paths. In the case where only the shortest paths from s to the vertices in a
given subset X ⊂ V are of interest in a given problem, the further pruning of
G̃(s) to the union of all the shortest paths from s to the vertices in X, denoted
G̃(s, X), is applicable. Note that, given G̃(s), the subgraph G̃(s, X) ⊆ G̃(s) can
be constructed in linear time by running a DFS scan from the vertices in X in
G̃(s) with the reversed direction of all edges, followed by removing from G̃(s) all
the vertices not reached by this scan.

4 Approximations of the SSPT Problem

We first show that the SSPT can be reduced to the uniform vertex-weighted
version of the directed Steiner tree problem (UVDST), and that this reduction
preserves approximability. Thus, we can leverage the known approximation al-
gorithms for the directed Steiner tree problem. Next, we consider a special class
of graphs that we call polylogarithmically shallow graphs and show a polylog-
approximation algorithm for UVDST on this class. This also implies a polylog-
6 Asher, Dinitz, Dolev, Raviv, and Schieber

approximation algorithm for SSPT on the class of polylogarithmically shortest

path shallow graphs.

4.1 Reduction of SSPT to UVDST

The input to the directed Steiner tree problem (DST), studied in [1,9], is a
directed graph whose edges have non-negative weights, a source vertex s and a
subset of vertices X. The goal is to find a tree with the minimum total edge
weight rooted at s and spanning X. We can assume, w.l.o.g., that all vertices
are reachable from s (the unreachable ones may safely be removed).
We define two related problems on vertex-weighted graphs G = (V, E, W ),
W : V → R+ , W (t) = 0 for all t ∈ X, which are equivalent to variants of
DST. In the general variant, termed VDST, the weights are assigned to the
nonterminal vertices arbitrarily, and the goal is to find a tree with the minimum
total vertex weight rooted at s and spanning X. Note that VDST is equivalent
to the particular case of DST where the weights assigned to edges (u, v) are the
same for all edges incoming to v, for any v ∈ V . The uniform case of VDST
(UVDST) is given by fixing the weight of all non-terminals to 1. Thus, UVDST
is the minimum non-terminals directed Steiner tree problem defined as follows:
given a digraph, a source vertex s, and a set of terminals X, s ∈ / X, find a tree
rooted at s and spanning X with the minimum number of non-terminal vertices.
By the analysis in Section 3, the SSPT problem on (G, s, X) is equivalent
to the UVDST problem on (G̃(s), s, X) (or on (G̃(s, X), s, X)), keeping the ob-
jective function. Therefore, any α-approximation of the latter problem is an α-
approximation of the former problem. We thus arrive at the following reduction
yielding a family of approximation algorithms for the SSPT problem.

Theorem 2. Let A be any approximation algorithm solving the UVDST prob-

lem with approximation ratio α. Then, given an instance I = (G, s, X) of the
SSPT problem, running A on the instance (G̃(s, X), s, X) (or (G̃(s, X), s, X))
of UVDST returns a tree which is an α-approximation to the optimum for I,
keeping the same running time bound.

In particular, the quasi-polynomial O(log2 (|X|)/ log log |X|)-approximation

algorithm in [9] yields a quasi-polynomial O(log2 (|X|)/ log log |X|)-approximat-
ion algorithm for the SSPT problem.
Remark : To further compare the complexity of the problems discussed, we
review some additional observations on (approximation-preserving) reductions
among undirected SSPT (U-SSPT), directed SSPT (D-SSPT), and UVDST. The
general UVDST can be reduced to D-SSPT by setting all edge weights to be 0.
We are aware of a reduction from UVDST to U-SSPT only when the input
graph is acyclic. The reduction sets the weight of every edge (u, v) in the U-
SSPT instance to be D(s, v) − D(s, u), where D(s, x) is the maximum length of
a path from s to x. As for the comparison between U-SSPT and D-SSPT, the
reduction from U-SSPT to D-SSPT is straightforward, by replacing every edge
by the two oppositely directed edges between the same vertices. D-SSPT can be
 Shallowest Shortest Path Tree 7

reduced to U-SSPT if there are no zero cycles (cycles with edges of weight zero
only) in the graph, similarly to the reduction from UVDST to U-SSPT as above.

4.2 Polynomial Polylog Approximations for Polylogarithmically

Shallow Graphs

In this section, we suggest a polynomial polylog-approximation algorithm for the

UVDST problem on polylogarithmically shallow graphs (to be defined precisely
below). This implies, by Theorem 2, a similar result for the SSPT problem. By
saying that T is a tree, we mean a tree rooted at s whose edges are directed along
the paths from s. For any tree T , let nt(T ) denote the number of non-terminals
in T . We denote by OP T (I) the number of non-terminals in the optimal solution
to any problem instance I.
Our plan of approximating UVDST is as follows. Given an instance I =
(G, s, X) of UVDST, we first construct an instance I SC of Set Cover whose
optimum OP T (I SC ) lower bounds OP T (I). Based on the solution to I SC , we
generate a feasible solution of I whose objective function value is upper bounded
by a function of OP T (I SC ) and, thus, also by the same function of OP T (I).
Let G[X] be the subgraph of G induced by X (that is, composed of the
terminals and the edges between them). Consider the set of strongly-connected
components of G[X]. (Note that some of these components may be a single
terminal.) Define its subset S of source components to be those not reachable in
G[X] from any other component.

Lemma 1. There exists a linear time algorithm that, given any tree T spanning
at least one terminal in each component in S, builds a tree T ′ spanning the entire
X with nt(T ′ ) = nt(T ).

Proof. Let us choose one of the terminals spanned by T in every source com-
ponent. We construct a DFS forest F in G[X] from all these terminals. By
construction, F spans X. We build a tree T ′ as required by adding to T all
edges in F leading to the terminals not in T . Note that such edge additions do
not change the set of non-terminals in the tree. ⊔
⊓

We use the following observation in designing our approximation algorithm.

We show that in any tree T feasible for I, that is, spanning X, the set of edges
from non-terminals to terminals “covers” S, in a sense. We denote by P reS the
set of non-terminals {v ∈ V \ X : ∃(v, t) ∈ E, t ∈ S, S ∈ S} (that is, the vertices
in P reS are the non-terminals in G with outgoing edges to the terminals in the
source components of G[X]) . For any v ∈ P reS, let N (v) = {S ∈ S : ∃(v, t) ∈
E, t ∈ S}. We denote by I SC the instance of Set Cover defined by the subsets
{N (v) : v ∈ P reS} of S.

Lemma 2. For any instance I of UVDST, OP T (I SC ) is a lower bound on

OP T (I).
8 Asher, Dinitz, Dolev, Raviv, and Schieber

Proof. Consider any tree T feasible for I. Denote by V ′ (T ) the set of non-
terminals in T that are also in P reS. Let us show that for any source component
S, there exists an edge in T from V ′ (T ) to a terminal in S. Let t be any terminal
from S closest to s in T . Its parent v in T cannot be in S by our choice and
cannot be in another strongly-connected component of G[X] since S is a source
component. Hence, v is a non-terminal, and (v, t) is an edge as required.
Let tree T ∗ be optimal for I. By the above, {N (v) : v ∈ V ′ (T ∗ )} is a feasible
solution for I SC . Now, OP T (I SC ) ≤ |V ′ (T ∗ )| ≤ nt(T ∗ ) = OP T (I), as required.
⊔
⊓

Consider the following algorithm A = A(I) for the UVDST problem:

1. Construct I SC based on I.
2. Find an O(log |S|)-approximation of I SC by the algorithm in [2], denoted P .
Note that P is defined by VSC ⊆ P reS such that P = {N (v) : v ∈ VSC }.
3. Construct an edge set ESC by choosing for each S ∈ S, a single edge (v, t) ∈
E, where t ∈ S and v ∈ VSC .
4. Build a BFS tree TBF S from s to VSC in G.
5. Build a tree T by adding to TBF S all edges in ESC leading to the terminals
not in TBF S .
6. Return the tree T ′ obtained from T by expanding it as in the proof of
Lemma 1.

To analyze the approximation ratio of this algorithm, we define the notion of

shallowness. A digraph G with a source vertex s is R-shallow if for every v ∈ V ,
there exists a path from s to v that has no more than R edges. (Note that the
minimum possible value of such an R is the radius from s in G.)

Theorem 3. The algorithm A is polynomial and returns an O(R · log(|X|))-

approximation to the UVDST problem on R-shallow digraphs.

Proof. The algorithm is polynomial since all its steps and auxiliary objects are
polynomial in the input size. Step 3 of the algorithm is consistent, and the tree
T spans all components in S since P is a set cover of S. The tree T ′ is feasible
for I by Lemma 1. To prove the approximation ratio, we analyze the size of T ′ .
Note that TBF S is a union of paths with the minimum number of edges
from s to each of the vertices in VSC ; therefore, nt(TBF S ) is at most R · |VSC |.
By Lemmas 1 and 2, the objective function value of the returned solution
is nt(T ′ ) = nt(T ) = nt(TBF S ) ≤ R · |VSC | = R · O(log(|S|) · OP T (I SC ) =
O(R · log(|X|) · OP T (I), as required. ⊔
⊓

We say that a directed graph G with a source vertex s is polylogarithmically

shallow if it is R-shallow where R is polylogarithmic in |X|. Logarithmically
shallow digraphs are defined similarly.

Corollary 1. Algorithm A computes a polylog approximation of UVDST on

polylogarithmically shallow digraphs, and an O(log2 |X|)-approximation on log-
arithmically shallow digraphs.
 Shallowest Shortest Path Tree 9

For our SSPT result, we define shortest path shallowness. A graph G (either
undirected or directed) with a source vertex s is R-shortest path shallow if for
every v ∈ V there exists a shortest path from s to v with no more than R
edges. (Note that the minimum possible value of such an R is the radius from
s in G̃(s).) We say that G with a source vertex s is polylogarithmically shortest
path shallow if it is R-shortest path shallow where R is polylogarithmic in |V |.
Logarithmically shortest path shallow graphs are defined similarly.

Corollary 2. There exists a polynomial algorithm for the SSPT problem on

(undirected or directed) instances (G, s, X) that provides a polylog-approximation
when G is polylogarithmically shortest path shallow, and an O(log2 |X|)-approxim-
ation when G is a logarithmically shortest path shallow.

The following generalization of Corollary 1 to VDST and the according gen-

eralization of Corollary 2 to the weighted SSPT may be of some interest. To
analyze VDST, define the weight W (P ) of a path P to be the total weight of the
vertices in it, and the distance D(v) to be the minimum weight of a path from
s to v, v ∈ V . We modify algorithm A to AW by replacing the BFS tree in step
4 by the shortest path tree from s to VSC w.r.t. W . Note that the algorithm of
[2] provides an O(log |S|)-approximation solution also to the weighted Set Cover
problem, so algorithm AW is consistent with the VDST problem. Extending
straightforwardly the analysis in the proof of Theorem 3 to this problem, we
generalize Corollary 1 to:

Corollary 3. There exists a polynomial algorithm for the VDST problem on the
instances (G = (V, E, W ), s, X) that provides a polylog-approximation when the
ratio D(v)/W (v) is polylogarithmic in |X|, and an O(log2 |X|)-approximation
when the ratio D(v)/W (v) is logarithmic in |X|, for all v ∈ V \ X.

Recall that in the weighted variant of SSPT, the non-terminals are assigned
weights W (which differ from the weight w on the edges) and the goal is to
minimize the total weight of the non-terminals in a shortest path tree.

Corollary 4. There exists a polynomial algorithm for the weighted (undirected

or directed) variant of the SSPT problem on the instances (G = (V, E, w, W ), s, X)
that provides a polylog-approximation when, for any vertex v ∈ V , there exists a
shortest w.r.t. w path P from s to v with the ratio W (P )/W (v) polylogarithmic
in |X|, and an O(log2 |X|)-approximation when, for any vertex v ∈ V , there ex-
ists a shortest w.r.t. w path P from s to v with the ratio W (P )/W (v) logarithmic
in |X|.

References

1. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto
Guha, and Ming Li. Approximation algorithms for directed steiner problems. Jour-
nal of Algorithms, 33(1):73–91, 1999.
10 Asher, Dinitz, Dolev, Raviv, and Schieber

2. Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of

operations research, 4(3):233–235, 1979.
3. E. A. Dinic. An algorithm for the solution of the max-flow problem with the
polynomial estimation. Soviet Math. Dokl., 11(5):1277–1280, 1970.
4. Yefim Dinitz, Shlomi Dolev, and Manish Kumar. Polynomial time prioritized
multi-criteria k-shortest paths and k-disjoint all-criteria-shortest paths. CoRR,
abs/2101.11514, 2021.
5. Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin. Breaking the sort-
ing barrier for directed single-source shortest paths. In Proc. 57th ACM Symposium
on Theory of Computing, STOC ’25, pages 36––44, 2025.
6. Michael Elkin and Shay Solomon. Steiner shallow-light trees are exponentially
lighter than spanning ones. SIAM Journal on Computing, 44(4):996–1025, 2015.
7. Andrew V. Goldberg and Robert Endre Tarjan. A new approach to the maximum-
flow problem. J. ACM, 35(4):921–940, 1988.
8. Luis Gouveia, Luidi Simonetti, and Eduardo Uchoa. Modeling hop-constrained and
diameter-constrained minimum spanning tree problems as steiner tree problems
over layered graphs. Mathematical Programming, 128(1):123–148, 2011.
9. Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O(log2 k/ log log k)-
approximation algorithm for directed steiner tree: A tight quasi-polynomial time
algorithm. SIAM Journal on Computing, 52(2):STOC19–298–STOC19–322, 2023.
10. Tan Miller. Hierarchical Operations and Supply Chain Planning. Springer, 2002.