arXiv:1611.01644v1 [] 5 Nov 2016

Surviving in Directed Graphs:
A Polylogarithmic Approximation for
Two-Connected Directed Steiner Tree
Fabrizio Grandoni∗

Bundit Laekhanukit†

November 8, 2016

Abstract
Real-word networks are often prone to failures. A reliable network needs to cope with this situation
and must provide a backup communication channel. This motivates the study of survivable network
design, which has been a focus of research for a few decades. To date, survivable network design
problems on undirected graphs are well-understood. For example, there is a 2 approximation in the case
of edge failures [Jain, FOCS’98/Combinatorica’01]. The problems on directed graphs, in contrast, have
seen very little progress. Most techniques for the undirected case like primal-dual and iterative rounding
methods do not seem to extend to the directed case. Almost no non-trivial approximation algorithm is
known even for a simple case where we wish to design a network that tolerates a single failure.
In this paper, we study a survivable network design problem on directed graphs, 2-Connected Directed Steiner Tree (2-DST): given an n-vertex weighted directed graph, a root r, and a set of h terminals
S, find a min-cost subgraph H that has two edge/vertex disjoint paths from r to any t ∈ S. 2-DST is
a natural generalization of the classical Directed Steiner Tree problem (DST), where we have an additional requirement that the network must tolerate one failure. No non-trivial approximation is known
for 2-DST. This was left as an open problem by Feldman et al., [SODA’09; JCSS] and has then been
studied by Cheriyan et al. [SODA’12; TALG] and Laekhanukit [SODA’14]. However, no positive result
was known except for the special case of a D-shallow instance [Laekhanukit, ICALP’16].
We present an O(D3 log D · h2/D · log n) approximation algorithm for 2-DST that runs in time
O(nO(D) ), for any D ∈ [log2 h]. This implies a polynomial-time O(hε log n) approximation for any
constant ε > 0, and a poly-logarithmic approximation running in quasi-polynomial time. We remark that
this is essentially the best-known even for the classical DST, and the latter problem is O(log2−ε n)-hard
to approximate [Halperin and Krauthgamer, STOC’03]. As a by product, we obtain an algorithm with
the same approximation guarantee for the 2-Connected Directed Steiner Subgraph problem, where the
goal is to find a min-cost subgraph such that every pair of terminals are 2-edge/vertex connected.
Our approximation algorithm is based on a careful combination of several techniques. In more detail,
we decompose an optimal solution into two (possibly not edge disjoint) divergent trees that induces two
edge disjoint paths from the root to any given terminal. These divergent trees are then embedded into
a shallow tree by means of Zelikovsky’s height reduction theorem. On the latter tree we solve a 2Connected Group Steiner Tree problem and then map back this solution to the original graph. Crucially,
our tree embedding is achieved via a probabilistic mapping guided by an LP: This is the main technical
novelty of our approach, and might be useful for future work.
∗
IDSIA, University of Lugano, Switzerland, fabrizio@idsia.ch. Partially supported by the ERC Starting Grant
NEWNET 279352 and the SNSF Grant APPROXNET 200021 159697/1.
†
Weizmann Institute of Science, Israel, bundit.laekhanukit@weizmann.ac.il. Partially supported by the ISF (grant
No. 621/12) and by the I-CORE Program (grant No. 4/11).

1 Introduction
Real-world networks are often prone to link or node failures. A reliable network needs to cope with this
situation and must provide a backup communication channel. In mathematical terms, ones wish to design a
network that provides a pre-specified number of edge/vertex disjoint paths between given pairs of terminals.
This motivates the study of survivable network design, which has been a focus of research for a few decades
[45, 18, 23, 28].
To date, the survivable network design problems on undirected graphs are well-understood, and many
powerful techniques have been developed to solve this class of problems. For example, in the edge failure
case, there is a 2-approximation algorithm by Jain [28] for the most general version of the problem, Generalized Steiner Network. In contrast, there has been very slow progress on survivable network design in
directed graphs. Most of the standard techniques like primal-dual and iterative rounding methods do not
seem to extend to the directed case. Positive results are known only for very restricted cases (see, e.g.,
[12, 37, 20, 36]). In fact, there are almost no positive results for survivable network design on directed
graphs in the present of Steiner vertices.
In this paper, we focus on arguably one of the simplest survivable network design problems in directed
graphs, namely, 2-Connected Directed Steiner Tree (2-DST):
Definition 1. In the 2-connected Directed Steiner Tree problem (2-DST), we are given an n-vertex directed
graph G = (V, E) with edge-costs {ce }e∈E , a root vertex r and a set of h terminals S ⊆ V − {r}. The goal
is to find a min-cost subgraph H that has at least 2 edge disjoint paths from r to each t ∈ S.
Intuitively, the goal of 2-DST is to design a network that can function in the event of one edge failure
(thus, it must provide a backup path). 2-DST is a natural generalization of the classical Directed Steiner
Tree problems (DST), where only one r, t-path for each t ∈ S is required to exist in H. Feldman et al. [16]
left approximating 2-DST as an open problem (see also the earlier work in [12]), and the problem has later
been studied in the work of Cheriyan et al. [8] and Laekhanukit [34, 36]. However, there was no known
non-trivial approximation algorithm for 2-DST except for the special case of D-shallow instances (where
the length of any root-to-terminal path in the optimal solution is at most D 1 ) [36].
Here we define 2-DST in terms of edge-connectivity. The vertex-connectivity version is defined analogously, but we are asked for vertex-disjoint instead of edge-disjoint paths. The two variants share the same
approximability in directed graphs. There is a simple reduction that reduces the vertex-connectivity version
to edge-connectivity version2 and vice versa. We will therefore focus only on the edge connectivity case.

1.1 Our Results and Techniques
The main contribution of this paper is a non-trivial approximation algorithm for 2-DST.
Theorem 2. For any D ∈ [log2 h], there exists a randomized O(D 3 log D · h2/D · log n) approximation
algorithm for 2-DST that runs in nO(D) time.
1
A D-shallow instance is an instance that has an optimal solution H such that, for every terminal t, H has k edge-disjoint
r, t-paths in which each path has length at most D (i.e., all the k paths are short). This imitates the notion of the height of a tree,
but it allows H to contain a directed cycle.
2
In more detail, split each vertex v into v in and v out , add a zero-cost edge v in v out , and then re-wire each edge entering and
leaving v to v in and v out , respectively. A source-sink pairs (s, t) is then replaced by the pair (sout , tin ). The number of pairs does
not change, and the number of vertices grows by a factor 2.

1

In particular, Theorem 2 implies a polynomial-time O(hε log n) approximation for any constant ε > 0,
and a quasi-polynomial-time O(log n log3 h log log h) approximation algorithm. We remark that, up to
poly-logarithmic factors, this is the best known even for the simpler case of DST [6].
Approximation algorithms for 2-DST can be used to approximate with the same asymptotic approximation factor the more general problem, namely 2-DSS, described in [11, 35, 41] (see Appendix A for more
details).
Definition 3. In the 2-Connected Directed Steiner Subgraph problem (2-DSS), we are given a directed graph
G = (V, E) with edge-costs {ce }e∈E and a set of terminals S ⊆ V . The goal is to find a min-cost subgraph
H of G such that, for every pair of vertices s, t ∈ S, H has 2 edge-disjoint paths from s to t.
As a corollary of Theorem 2, we obtain the following result.
Corollary 4. For any D ∈ [log2 h], there exists a randomized O(D 3 log D · h2/D · log n) approximation
algorithm for 2-DSS that runs in nO(D) time.
Our approach is rather sophisticated, and involves several logical steps. The starting point is the following decomposition theorem3 .
Theorem 5 (Divergent Steiner Trees Theorem [22, 33]). Let H be a feasible solution to a 2-DST instance
with a root r and terminals S. Then H can be decomposed into two (possibly overlapping) arborescences
(divergent Steiner trees) T1 and T2 rooted at r and spanning S such that, for every terminal t ∈ S, the
unique r-t paths P1 in T1 and P2 in T2 are edge disjoint.
Intuitively, T1 and T2 are two solutions to the DST problem on the same instance with the extra property
of being edge disjoint “from the point of view” of a single terminal. We remark that this is the only part of
our approach that does not directly generalize to connectivity k ≥ 3 because the decomposition does not
exist for k ≥ 3 [27, 3]. (See the discussion in Section 5.)
The second main tool from the literature that we wish to exploit is the Zelikovsky’s height-reduction
theorem [26, 46] that is used in approximating DST.
Theorem 6 (Height Reduction Theorem [26, 46]). Consider an edge weighted arborescence T rooted at r
and spanning S. Then, for any D ∈ [log2 |S|], in the metric completion of T , there exists an arborescence
T D of depth at most D rooted at r and spanning S together with a mapping ψ that maps each vertex of T D
to a vertex of T and a mapping φ that maps each edge ê = ûv̂ ∈ E(T D ) to a ψ(û), ψ(v̂) path φ(ê) in T so
that the following bounded congestion property holds:
|ê ∈ E(T D ) : e ∈ φ(ê))}| ≤ β ′ = O(D · |S|1/D ) ∀e ∈ E(T ).
In particular, the cost of T D is at most β ′ times the cost of T .
We remark that the Height Reduction Theorem was originally stated in terms of cost (which is implied
by our version). Here we extract the bounded congestion property that is implicit in the proof.
The main difficulty that we have to face is how to apply these two tools. In DST approximation, Theorem 6 is typically applied by considering the metric closure of the input graph. This is not applicable to
our case since the metric closure might destroy the connectivity properties of the input graph. Moreover,
we cannot directly apply the theorem to the divergent Steiner trees because they are a decomposition of an
optimal solution that we wish to compute.
3

There also exists a vertex-connectivity analogue of this theorem, but we omit it here since it is not necessary for our goals.

2

We solve these issues by defining an ILP that mimics the decomposition of the optimal solution into
divergent Steiner trees T1 and T2 (as in Theorem 5) and the following application of Theorem 6 to these
trees to obtain D-shallow trees T1D and T2D . In more detail, we define a D-shallow tree that incorporates
(twice) all the possible paths of length D starting from the root (analogously to [36]). This shallow tree
implicitly includes T1D and T2D . We encode the mapping of each edge of T1D ∪ T2D into the associated paths
in T1 ∪ T2 using flow constraints. We also add constraints that encode the bounded congestion property
from Theorem 6 (crucial to bound the cost of the approximate solution) and the divergency property from
Theorem 5 (crucial to achieve a feasible solution).
Rounding a fractional solution to the linear relaxation is a non-trivial task. We observe that each terminal
t ∈ S is associated with a subset of vertices Ŝt in the shallow tree, and the edges of T1D ∪ T2D must contain
two edge disjoint paths from the root r̂ to Ŝt . In other words, the latter edges induce a feasible solution
to a tree instance of 2-Edge Connected Group Steiner Tree (2-GST) with root r̂ and groups {Ŝt }t∈S (more
details in related work). This allows us to add the standard LP constraints for 2-GST on a tree to our linear
relaxation, and use the GKR rounding algorithm by Garg et al. [21] to round the corresponding variables to
an integral 2-GST solution in the shallow tree.
The last obstacle that we need to face is that we need to map back each chosen edge ê of the shallow tree
to a path φ(ê) of the original graph. The LP solution provides a fractional mapping in the form of a flow.
We interpret this flow as a distribution over paths and sample one path φ(ê) according to this distribution. In
order to show that the solution is feasible (with large enough probability), we exploit an argument similar in
spirit to the one used by Chalermsook et al. [5] in the framework of k-Edge Connected Group Steiner Tree
(k-GST) approximation. However, our probabilistic mapping makes the analysis slightly more involving.
Shortly, we argue that for any given edge e of the original graph, GKR rounding has sufficiently large
probability to select paths using only edges ê of the shallow tree whose associated probabilistic mapping has
low chance to use the edge e. The claim then follows by a cut argument as in [5].

1.2 Related Work
In the Directed Steiner Tree problem (DST), we are given an n-vertex directed edge weighted graph, a
root r and a collection of h terminal vertices S. The goal is to find a min-cost arborescence rooted at r
and spanning S. DST is one of the most fundamental network design problems in directed graphs. DST
admits, for any positive integer D, an O(Dh1/D log2 h) approximation running in time nO(D) [6, 46]. In
particular, this implies a polynomial-time O(hε ) approximation for any constant ε > 0, and an O(log3 h)
approximation running in quasi-polynomial time.
k-DST and k-DSS are the natural generalization of 2-DST and 2-DSS, respectively, with connectivity
k. These problems have been a subject of study since early 90’s [12] and have been subsequently studied in
[8, 34, 36]. Cheriyan et al. [8] showed that k-DST is at least as hard as the Directed Steiner Forest problem
1−ε
and the Label-Cover problem. Thus, k-DST admits no 2log n -approximation algorithm, for any ε > 0,
unless NP ⊆ DTIME(2polylog(n) ). For small k, they showed that k-DST admits no kσ -approximation
algorithm for some fixed σ > 0 unless P = NP. If k is large enough, then k-DST is NP-hard even when we
have only two terminals, and they further proved that k-DST when h and k are constants is polynomial-time
solvable in directed acyclic graphs. However, if the input graph contains a cycle, the complexity status of
k-DST is not clear even for k = h = 2. Laekhanukit refined the hardness result of k-DST in [34] and
showed that k-DST admits no k1/2−ε -approximation algorithm, for any constant ε > 0, unless NP = ZPP.
In a subsequent work, Laekhanukit [36] presented an LP-based O(kD−1 D log n)-approximation algorithm
for D-shallow instances of k-DST and k-DSS running in time nO(D) . It seems that his approach cannot be
generalized to arbitrary instances (although we will exploit part of his ideas).

3

A well-studied special case of DST is the Group Steiner Tree problem (GST). Here we are given
an undirected weighted graph, a root vertex r, and a collection of h groups Si ⊆ V . The goal is to
compute the cheapest tree that spans r and at least one vertex from each group Si . The best-known
polynomial-time approximation factor for GST is O(log2 h log n) due to Garg et al. [21]. Their algorithm uses probabilistic distance-based tree embeddings [2, 15] as a subroutine. Chekuri and Pal [7] presented an O(log2 h) approximation that runs in quasi-polynomial time. On the negative side, Halperin and
Krauthgamer [25] showed that GST admits no log2−ε n-approximation algorithm, for any constant ε > 0,
unless NP ⊆ ZPTIME(2polylog(n) ). This implies the same hardness for DST, hence for 2-DST and 2-DSS.
The high-connectivity version of GST, namely, the k-Edge Connected Group Steiner Tree problem
(k-GST), was studied in [5, 24, 29]. Here the goal is to find a min-cost subgraph that contains k edgedisjoint paths between the root and each group. For k = 2, the best approximation ratio is Õ(log3 n log h)
due to the work of Gupta et al. [24]. If the size of any group is bounded by α, then there is an O(α log2 n)approximation algorithm by Khandekar et al. [29]. For k ≥ 3, there is no known non-trivial approximation
algorithm for k-GST. Chalermsook et al. [5] presented an LP-rounding bicriteria approximation algorithm
that returns a subgraph with cost O(log2 n log h) times the optimum while guarantees a connectivity of at
least Ω(k/ log n). Their algorithm uses the probabilistic cut-based tree embeddings by Räcke [43] as a subroutine (as opposed to distance-based ones in [24]). We will exploit part of their ideas in our rounding algorithm (although a probabilistic tree embedding for directed graphs is not available for us). Chalermsook et al.
also showed that k-GST is hard to approximate to within a factor of kσ , for some fixed constant σ > 0, and
if k is large enough, then the problem is at least as hard as the Label-Cover problem, meaning that k-GST
1−ε
admits no 2log n -approximation algorithm, for any constant ε > 0, unless NP ⊆ DTIME(2polylog(n) ).
As already mentioned, survivable network design is well studied in undirected (weighted) graphs. First,
consider the edge connectivity version. The earliest work is initiated in early 80’s by Frederickson and
JáJá [18], where the authors studied the 2-Edge Connected Subgraph problem in both directed and undirected graphs. In the most general form of the problem, also known as the Steiner Network problem, we are
given non-negative integer requirements ku,v for all pairs of vertices u, v, and the goal is to find a min-cost
subgraph that has ku,v edge-disjoint paths between u and v. Jain [28] devised a 2-approximation algorithm
for this problem. We remark that 2 is the best known approximation factor even for ku,v ∈ {0, 1} [1],
which is known as the Steiner forest problem. The classical Steiner tree problem is a special case of Steiner
forest where all pairs share one vertex. Here the best known approximation factor is 1.39 due to the work of
Byrka et al. [4].
Concerning vertex connectivity, two of the most well-studied problems are the k-Vertex Connected
Steiner Tree (k-ST) and k-Vertex Connected Steiner Subgraph (k-SS) problems, i.e., the undirected versions
of k-DST and k-DSS, respectively. There are 2-approximation algorithms for 2-ST and 2-SS by Fleischer et al. [17] using the iterative rounding method. For k ≥ 3, Nutov devised an O(k log k)-approximation
algorithm for k-ST in [40] and an O(min{|S|2 , k log2 k})-approximation algorithm for k-SS in [41] (also,
see [35]). A special case of k-SS with metric-costs is studied by Cheriyan and Vetta in [11] who gave an
O(1)-approximation algorithm for the problem. The most extensively studied special case of k-SS is when
all vertices are terminals, namely the k-Vertex Connected Spanning Subgraph problem, which has been
studied, e.g., in [10, 31, 14, 42, 9]. The current best approximation guarantees are O(log(n/(n − k)) log k)
[42], and 6 for the case n ≤ 2k3 [9, 19]. More references can be found in [32, 38, 39].
Notation. We use standard graph terminologies. For any graph G, we denote vertex and edge sets of G by
V (G) and E(G), respectively. For any subset of vertices S ⊆ V (G) (or a single vertex S = v), we denote
in (S) and denote the set of edges leaving S by δ out (S).
the set of edges of G entering S by δG
G

4

2 Embedding into a Shallow Tree
Our LP-relaxation is defined based on the existence an embedding of an optimal 2-DST solution H in the
original graph into an auxiliary D-shallow tree Ĥ (i.e., a tree of depth at most D), where D > 0 is an integer
given as parameter. Our embedding is obtained by applying the Height Reduction to Divergent Steiner Trees.
We start by decomposing Ĥ into two divergent Steiner trees T1 and T2 using the Divergent Steiner Tree
Theorem (Theorem 5). Then we apply the Height Reduction Theorem (Theorem 6) to each such Ti , hence
getting a D-shallow tree TiD in the metric closure of Ti together with mappings ψi and φi . The final step
is to unify the roots of T1D and T2D , hence getting a tree Ĥ rooted at r̂. We also merge the two mappings
in a natural way, thus getting ψ : V (Ĥ) → V (H) and φ : E(Ĥ) → 2E(H) . Let ψ −1 (v) be the set of
vertices v̂ ∈ V (Ĥ) with ψ(v̂) = v. Note also that each simple û, v̂-path P̂ in Ĥ defines a ψ(û), ψ(v̂) path
P = φ(P̂ ) in H.
By construction, it is not hard to see that (Ĥ, ψ, φ) has the following properties:
1. (divergency) for any terminal t ∈ S, there exist two vertices t̂1 , t̂2 ∈ ψ −1 (t) such that the following
holds. Let P̂i be the r̂-t̂i path in Ĥ for i = 1, 2. Then φ(P̂1 ) and φ(P̂2 ) are two edge-disjoint r-t paths
in H (and consequently also in Ĥ).
2. (bounded congestion) For any edge e ∈ E(H), |ê ∈ E(Ĥ) : e ∈ φ(ê)| ≤ β := 2β ′ = O(D|S|1/D ).
Note that we do not know an optimal solution, and consequently the two trees T1 , T2 that are needed to
define the above embedding. In the next section, we define an LP relaxation that, in some fractional sense,
achieves this goal.

3 An LP-relaxation for 2-DST
In this section, we present an ILP formulation of 2-DST, and the corresponding LP relaxation.
The first step in the definition of our ILP is to build a proper D-shallow tree T̂ = (V̂ , Ê) that contains the
tree Ĥ (defined in the previous section) as a subgraph. To this end, we list twice all the possible sequences
of at most D + 1 distinct vertices of G starting with the root r. The prefix tree of these sequences (rooted at
r̂ = r) is our tree T̂ . That is, each vertex v̂ of T̂ is associated with a vertex v in the input graph G, and each
rooted-path in T̂ corresponds to each sequence we listed. It is not hard to see that Ĥ can be mapped to a
subtree of T̂ . Let ψ : V̂ → V be the corresponding mapping of vertices. With the same notation as before,
we define Ŝt := ψ −1 (t) to be the set of vertices in T̂ corresponding to terminal t ∈ S (the group of t). The
notion of group will be needed later to define a proper 2-GST instance.
We have all the ingredients for formulating our ILP. We define indicator variables xe ∈ {0, 1} for all
e ∈ E, which take value xeP
= 1 iff e ∈ H (H is an optimal solution to 2-DST). The objective function
that we wish to minimize is e∈E ce xe . Similarly, we define indicator variables x̂e ∈ {0, 1} for all e ∈ Ê,
which take value x̂e = 1 iff e ∈ E(Ĥ).
Now we define our constraints. First we define a set of linear constraints, denoted by LPgst , which
models the fact that, for each t ∈ S, Ĥ must contain two edge disjoint paths from r̂ to the group Ŝt . So, we
introduce flow variables fˆêt ∈ {0, 1} for all ê ∈ Ê and all terminals t ∈ S. The constraints LPgst are given
in Figure 1. We remark that LPgst are the linear constraints of the standard LP relaxation for the 2-GST
problem with the root r̂ and groups Ŝt for t ∈ S in which the underlying graph is a tree. This is a crucial
part of our formulation because this LP has a large integrality gap on general graphs [47].
Next we define the set of constraints LPcong that formulates (implicitly) a mapping φ : Ê → 2E of edges
ê = ûv̂ of T̂ into ψ(û), ψ(v̂) paths of G. We introduce the following new flow variables: fê,e ∈ {0, 1}, for
5

Fig. 1 The LPgst constraints.
ˆt
X fê ≤ x̂êX
fˆêt =

ê∈δout (v̂)

ê∈δin (v̂)
T̂
X

∀ê ∈ Ê, ∀t ∈ S
∀t ∈ S, ∀v̂ ∈ V̂ − (Ŝt ∪ {r̂})

fˆêt

T̂

fˆêt

≥ 2

∀t ∈ S

ê∈δin (Ŝt )
T̂

all ê ∈ Ê and e ∈ E. Intuitively, the set of edges e ∈ E with fê,e = 1 form the path φ(ê). Clearly one
has fê,e ≤ xe . In order to satisfy the bounded congestion property, we impose that, for a given e ∈ E, the
sum of variables fê,e is upper bounded by β · xe , where β = O(D|S|1/D ) comes from the Height Reduction
Theorem (Theorem 6). These LP constraints are given in Figure 2.
Fig. 2 The constraints LPcong .
X

fê,e
fê,e

≤
=

xe
x̂ê

∀ê = ûv̂ ∈ Ê, ∀e ∈ E
∀ê = ûv̂ ∈ Ê

fê,e

=

0

∀ê = ûv̂ ∈ Ê

fê,e

=

out (u),u=ψ(û)
e∈δG

X

in (u),u=ψ(û)
e∈δG

X

fê,e

∀ê = ûv̂ ∈ Ê, ∀w ∈ V − {ψ(û), ψ(v̂)}

out (w)
e∈δG

in (w)
e∈δG

X

X

fê,e

≤

β · xe

∀e ∈ E

ê∈Ê

t ∈ {0, 1},
It remains to enforce the divergency property. We introduce a final set of new variables: fê,e
t = 1 indicate whether e is part of
for all ê ∈ Ê, e ∈ E, and t ∈ S. Intuitively, the edges e ∈ E with fê,e
one of the two edge disjoint paths in H from r to t. In an integral solution, for a given e ∈ E(H) and t, at
t can be set to 1. This guarantees that the mapping φ maps two r̂-Ŝ edge-disjoint paths in the
most one fê,e
t
shallow tree into two edge disjoint paths in the original graph from r to t. The set of constraints LPdiv is
described in Figure 3.
By relaxing the integrality constraints on the variables, we obtain an LP relaxation LP-2-DST for 2-DST,
presented in Figure 4.

4 Approximation Algorithm: Rounding via Tree Embedding
In this section, we present our approximation algorithm for 2-DST. Our algorithm starts by solving LPt }
2-DST. Denote by {xe , x̂ê , fˆêt , fê,e , fê,e
e∈E,ê∈Ê,t∈S an optimal fractional solution. We then execute for
O(D log n) times a rounding procedure, consisting of two main steps: the GST rounding and the path
mapping. The union of all the solutions obtained is the approximate solution, which is feasible w.h.p.
In more detail, consider a given iteration j. The variables {x̂ê }ê∈Ê provide a feasible solution to the standard LP for 2-GST on trees. In the GST rounding step, we apply the rounding algorithm by Garg et al. [21],
which we refer to as GKR rounding, to round these variables. This gives us a subtree Ĥj = (V̂j , Êj ) of T̂ .
6

Fig. 3 The constraints LPdiv
X

t
fê,e
t
fê,e

≤
=

fê,e
fˆt

∀e ∈ E, ∀ê ∈ Ê, ∀t ∈ S
∀ê = ûv̂ ∈ Ê, ∀t ∈ S

t
fê,e

=

0

∀ê = ûv̂ ∈ Ê, ∀t ∈ S

t
fê,e

=

ê

out (u),u=ψ(û)
e∈δG

X

in (u),u=ψ(û)
e∈δG

X

t
fê,e

∀ê = ûv̂ ∈ Ê, ∀t ∈ S, ∀w ∈ V − {ψ(û), ψ(v̂)}

out (w)
e∈δG

in (w)
e∈δG

X

X

t
fê,e

≤

xe

∀e ∈ E, ∀t ∈ S

ê∈Ê

Fig. 4 LP relaxation LP-2-DST.
X
min
ce xe
e∈E

s.t.

LPgst
LPcong
LPdiv
t
≤1
0 ≤ xe , x̂ê , fê,e , fˆêt , fê,e

∀ê ∈ Ê, ∀e ∈ E, ∀t ∈ S

In the path mapping step, we consider each edge ê = ûv̂ ∈ Êj , where u = ψ(û) and v = ψ(v̂).
We randomly map ê to a u, v-path in G. To this aim, we interpret variables {fˆê,e }e∈E as a distribution Pê
over u, v-paths, and we sample according to this distribution. We repeat this sampling O(β log D) many
times to guarantee that we have the desired properties (which will be discussed later) with sufficiently large
probability.
Our main algorithm is presented in Algorithm 1.
Algorithm 1 Round 2-DST
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

t }
Solve LP-2-DST and obtain a fractional solution {xe , x̂ê , fˆêt , fê,e , fê,e
e∈E,ê∈Ê,t∈S .
for j = 1 to 20D ln n do
Round variables x̂ê using GKR Rounding, and obtain a subtree Ĥj = (V̂j , Êj ) of T̂ .
for each ê = ûv̂ ∈ Êj , u = ψ(û) and v = ψ(v̂) do
for ℓ = 1 to (4β + 2) ln D do
Sample a u, v-path Pℓê in G from the distribution Pê .
end for
end for
Let Hj be the union of all sampled paths
end for
return H := ∪j Hj .

The GKR Rounding algorithm is discussed in Section 4.1. The construction of path distributions is
presented in Section 4.2. We then analyze our algorithm in Section 4.3.

7

4.1 GKR Rounding
Let T̂ be the shallow tree. We may think that each edge is directed from the root. Let ρ(ê) denote a parent
of an edge ê ∈ Ê, i.e., ρ(ê) is an edge adjacent to ê that is closer to the root. Consider the constrains LPgst
on variables x̂ê and fˆêt . This is indeed the standard LP for 2-GST. Hence, we can apply GKR rounding.
Assume w.l.o.g. that x̂ê ≤ x̂ρ(ê) . GKR algorithm considers edges in order of increasing distance from the
root. Each edge ê = r̂v̂ incident to the root r̂ is marked independently with probability x̂ê . Any other edge
ê ∈ Ê whose parent edge has been marked is marked independently with probability x̂ê /x̂ρ(ê) . Each marked
edge is added to the output tree. In our case, this gives the graph Ĥj .
Next lemma summarizes the properties of GKR Rounding that we will need in the analysis.
Lemma 7 ([21, 44]). Consider the run of GKR rounding algorithm on a D-shallow tree T̂ with variables
{x̂ê , fˆêt }ê∈Ê,t∈S given by a fractional solution to the standard GST LP. Let Ĥ be the solution sampled by the
P
algorithm, t ∈ S, and µt :=
fˆt . Then
in
ê∈δ

T̂

(Ŝt ) ê

Pr[ê ∈ Ĥ] = x̂ê

and

Pr[Ĥ contains an r̂, Ŝt -path] ≥

µt
.
2D

4.2 Constructing Path Distributions
Now we discuss how to construct a path distribution Pê on each edge ê = ûv̂ ∈ Ê. Let u = ψ(û) and
v = ψ(v̂). Observe that the variables F = {fê,e }e∈E form a u, v-flow. Thus, we can decompose F into a
collection of flow paths, say {fPê }P ∈Puv , where Puv is the set of all u, v-paths in G, so that
X
fPê = fê,e .
P ∈Puv :e∈E(P )

ê
The value of the flow F is x̂ê =
out (u) fê,e . Thus, {fP /x̂ê }P ∈Puv gives a collection of flow paths
e∈δG
whose total flows is one, and we can interpret this as a distribution over flow paths. This implies the
following lemma.

P

Lemma 8. Consider an edge ê = ûv̂ ∈ Ê and its corresponding variables {fê,e }e∈E . Let u = ψ(û) and
v = ψ(v̂). Then there exists a distribution of u, v-paths Pê such that for all e ∈ E:
Pr [e ∈ E(P )] =

P ∼Pê

1
· fê,e
x̂ê

4.3 Analysis
Next we analyze Algorithm 1. We start with the simpler part of our analysis, namely bounding the expected
cost of H.
P
Lemma 9. The expected cost of H is O(D 3 h2/D log D log n) · e∈E ce xe .

Proof. Let us bound the expected cost of Hj = (Vj , Ej ). For each edge e ∈ E,



(4β+2) ln D
i
 
X h
[
Pr[e ∈ Ej ]
≤
Pr ê ∈ Êj · Pr e ∈
E Pℓê  ê ∈ Êj 
ℓ=1

ê∈Ê

Lem. 7 and 8

≤

X

x̂ê · O(β log D) ·

ê∈Ê

8

fê,e
x̂ê

by LPcong

≤

O(β 2 log D) · xe

Thus, the expected cost of Hj is O(β 2 log D) times the LP value. The claim follows since there are
O(D log n) iterations and β = O(Dh1/D ).
We next show that our algorithm gives a feasible solution to 2-DST with high probability. This is the
most complicated part of the analysis.
The initial part of our analysis resembles the analysis in [5] for k-GST. We prove feasibility using
Menger’s theorem and a cut argument. By Menger’s theorem, the solution subgraph H ⊆ G contains two
edge disjoint r, t-paths if and only if H − {e} contains an r, t-path for every edge e ∈ E(H). Therefore, we
will focus on a given such pair (e, t). Our goal is to show that our rounding algorithm buys with sufficiently
high probability an r, t-path not using the edge e. For this purpose, we exploit the fact that, according to
Lemma 7, if we reduce the flow associated to some group Ŝt , GKR algorithm will still connect r̂ to Ŝt with
sufficiently large probability provided that the residual amount of flow µ′t from r̂ to Ŝt is large enough.
At this point, we might try to reduce the flow by the amount fê,e for each edge ê ∈ Ê. One can show
that µ′t would remain large enough, but unfortunately this in not sufficient in our case. Indeed, we might
still have a fairly high probability to use the edge e due to the probabilistic distribution over paths: for any
given ê, the sampled path Pℓê contains e with probability fê,e /x̂ê . So, we can “safely” use the edge ê only if
the complementary probability (x̂ê − fê,e )/x̂ê is sufficiently large. We say that an edge of the latter type is
good, and we wish to use only good edges.
Formally, we say that an edge ê ∈ Ê is good against e if
x̂ê − fê,e ≥

1
· fê,e .
2β

Otherwise, we say that ê is bad against e. If the edge e is clear from the context, we will simply say that ê is
bad (respectively, good). Similarly, we say that a path P̂ in T̂ is good (against e) if all edges of P̂ are good.
Otherwise, we say that P̂ is bad.
We claim that we can route an r̂, Ŝt -flow of value at least 1/2 using only good edges and even after
decreasing the capacity of edge ê by fê,e . In particular, we prove the following lemma.
Lemma 10. Let e ∈ E and t ∈ S. Let Êbad ⊆ Ê be the subset of bad edges against e, and Êgood =
Ê − Êbad . Consider the shallow tree T̂ ′ = T̂ − Êbad with capacities {x̂′ê }ê∈Ê , where x̂′ê = x̂ê − fê,e for all
edges ê ∈ T̂ . Then T̂ ′ supports an r̂, Ŝt -flow of value at least 1/2.
Proof. Recall that {fˆêt }ê∈Ê supports an r̂, St -flow of value at least 2 on T̂ . Thus, for any cut Û that separates
r̂ and Ŝt , (i.e., Û ⊆ V̂ , r̂ ∈ Û and Ŝt ⊆ (V̂ − Û )), we must have
X
fˆêt ≥ 2.
ê∈δout (Û )
T̂

We will prove later the following inequality
t
fˆêt − fê,e
≤ x̂ê − fê,e for any edge ê ∈ Ê.

9

(1)

Now we consider the capacities of edges leaving Û in the absence of bad edges.
X
X
X
X
x̂ê′ =
(x̂ê − fê,e ) =
(x̂ê − fê,e ) −

ê∈δout (Û )∩Êgood
T̂

ê∈δout (Û )∩Êgood

ê∈δout (Û )

T̂

By (1)

≥

T̂

t
(fˆêt − fê,e
)−

X

ê∈δout (Û )
T̂
by LPgst

≥

2−

≥

2−

X

t
fê,e
−

X

t
−
fê,e

1
2β

X

(x̂ê − fê,e )

2 − xe −

X

fê,e ≥ 2 −

ê∈δout (Û )∩Êbad

1 X
fê,e
2β

by LPcong

≥

2 − xe −

ê∈Ê

X

t
−
fê,e

ê∈Ê

T̂

T̂

≥

(x̂ê − fê,e )

ê∈δout (Û )∩Êbad
T̂

ê∈δout (Û )
by LPdiv

T̂

X

ê∈δout (Û )∩Êbad
T̂

ê∈δout (Û )
T̂
by def. bad

(x̂ê − fê,e )

ê∈δout (Û )∩Êbad

1 X
fê,e
2β
ê∈Ê

xe ≤1 1
1
· βxe ≥
2β
2

Thus, by the Max-Flow-Min-Cut Theorem, the network T̂ ′ with capacities {x̂′ê }ê∈Ê supports an r̂, Ŝt -flow
of value at least 1/2.
t = 0. So, let us assume
It remains to prove (1). The claim is trivially true if fê,e = 0 since it implies fê,e
that e belongs to the support of {fê,e′ }e′ ∈E . Again, we use the Max-Flow-Min-Cut Theorem. Consider
ê = ûv̂ ∈ Ê, and let u = ψ(û) and v = ψ(v̂). By the constraints of LPcong , the graph G with capacities
{fê,e′ }e′ ∈E supports a u, v-flow of value x̂ê . There must exist a minimum u, v-cut U ∗ that contains the edge
e, provided that fê,e > 0. To see this, observe that {fê,e′ }e′ ∈E induces a minimal flow network (as it is
a flow itself), i.e., decreasing the capacity of any edge decreases the value of maximum flow by the same
amount. So, every edge with positive capacity must contain in some minimum cut. Consequently, we have


X
X
x̂ê − fê,e = 
fê,e′  − fê,e =
fê,e′
out (U ∗ )
e′ ∈δG

By LPdiv

≥

X

out (U ∗ )−e)
e′ ∈(δG

out (U ∗ )−{e})
e′ ∈(δG



t
fê,e
′ = 

X

out (U ∗ )
e′ ∈δG



t
t
t 
≥ fˆêt − fê,e
− fê,e
fê,e
′

This completes the proof.
Next consider any good path against e in T̂ , say P̂ ⊆ T̂ , that connects r̂ to a group Ŝt . Then P̂ maps to
an r, t-path in the original graph G that does not use e with probability at least 1 − 1/D.
Lemma 11. Let e ∈ E and P̂ ⊆ T̂ be a good r̂, Ŝt -path against e. Suppose we map P̂ to a subgraph Q ⊆ G
by sampling (4β + 2) ln D paths from the distribution Pê for each ê ∈ E(P̂ ). Then Q − {e} contains an
r, t-path with probability at least 1 − 1/D.
Proof. Consider an edge ê = ûv̂ ∈ E(P̂ ). By Lemma 8, we have that any path P sampled from Pê contains
e with probability
fê,e def.good
1
≤ 1−
Pr [e ∈ E(P )] ≤
P ∼Pê
x̂ê
2β + 1
10

Since we sample (4β + 2) ln D paths from Pâ , the probability that all the sampled paths contain e is at most

2(2β+1) ln D  2 ln D
1
1
1
Pr[all paths P sampled from Pê contain e] ≤ 1 −
≤
≤ 2
2β + 1
e
D
(here e is the base of the natural logarithm.) We recall that P̂ has length at most D. Thus, by the union
bound,
1
1
Pr[∃ê ∈ E(P̂ ) s.t. all the paths P sampled from Pê contain e] ≤ D · 2 = .
D
D
We conclude that, with probability at least 1 − 1/D, for each ê ∈ E(P̂ ) we sample at least one path in G
that avoids e: the union of such avoiding paths forms a (possibly non-simple) r-t path that avoids e.
Now are ready to prove the feasibility of our solution H obtained from Algorithm 1.
Lemma 12. The subgraph H returned from Algorithm 1 is a feasible 2-DST solution w.h.p.
Proof. By Menger’s theorem, H is a feasible 2-DST solution iff for every edge e ∈ E and terminal t ∈ S,
H − {e} contains an r, t-path.
We claim that each subgraph Hj − {e} contains an r, t-path with probability at least 1/(5D). First
observe that, by Lemma 10, the capacities {x̂′ê }ê∈Ê support an r̂, Ŝt -flow of value at least 1/2 through good
paths. Thus, by Lemma 7, the GKR rounding algorithm guarantees that Ĥj contains a good r̂, Ŝt -path with
probability at least 1/(4D). Given the existence of a good path in Ĥj , by Lemma 11, Hj contains an r, tpath avoiding e with probability at least (1 − 1/D). Altogether, Hj contains such a path with probability at
least (1 − 1/D)/(4D) ≥ 1/(5D).
Since H is a union of 20D ln n subgraphs Hj ’s sampled independently, the probability that no subgraphs
Hj contain an r, t-path is at most


1
1 20D ln n
≤ 4.
1−
5D
n
As we have at most n terminals and at most n2 edges, it follows by the union bound that H − {e} contains
an r, t-paths, for every edge e ∈ E and every terminal t ∈ S, with probability at least 1 − 1/n.

5 Conclusions
We presented a non-trivial approximation algorithm for 2-DST on general graphs. Our approach crucially
relies on a decomposition of a feasible solution into two divergent Steiner trees. It is known that an analogous
decomposition does not exist for connectivity k ≥ 3 [27, 3]. However, weaker decomposition theorems
would be sufficient to exploit our basic approach. For example, is it possible to decompose a feasible
solution to k-DST into a collection of f (k) · polylog(n, h) trees so that, for each terminal t ∈ S and for
any edge-cut F of size k − 1, there exists some tree in the collection that connects r to t using no edges
from F ? Such a result could be combined with our LP-rounding technique to achieve similar approximation
ratios for any constant k. We are not aware of any such result nor of any counter-example. To support
our conjecture, we show in Appendix B the existence of a weaker decomposition in undirected graphs that
supports connectivity ⌈k/2⌉. Such decomposition allows us to design a bi-criteria approximation algorithm
for a variant of k-GST, namely k-GST*, where all the k edge-disjoint paths must end at the same vertex.
Achieving a sub-polynomial approximation for 2-DST in polynomial time is another obvious open problem. However, this has been a major open problem for decades even for DST. On the positive side, it is
likely that any future progress on DST can be extended to 2-DST via our approach.
11

Acknowledgment. We thank R. Ravi for suggesting the variant of k-GST.

References
[1] A. Agrawal, P. N. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440–456, 1995.
[2] Y. Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In FOCS,
pages 184–193, 1996.
[3] K. Bérczi and E. R. Kovács. A note on strongly edge-disjoint arborescences. In Proceedings of the 7th
Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, June, 2011, Kyoto,
Japan., pages 10–18, June 2011.
[4] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. Steiner tree approximation via iterative randomized
rounding. Journal of the ACM, 60(1):6, 2013.
[5] P. Chalermsook, F. Grandoni, and B. Laekhanukit. On survivable set connectivity. In SODA, pages
25–36, 2015.
[6] M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li. Approximation algorithms
for directed Steiner problems. Journal of Algorithms, 33(1):73–91, 1999.
[7] C. Chekuri and M. Pál. A recursive greedy algorithm for walks in directed graphs. In FOCS, pages
245–253, 2005.
[8] J. Cheriyan, B. Laekhanukit, G. Naves, and A. Vetta. Approximating rooted steiner networks. ACM
Transactions on Algorithms, 11(2):8:1–8:22, 2014.
[9] J. Cheriyan and L. A. Végh. Approximating minimum-cost k-node connected subgraphs via
independence-free graphs. SIAM Journal on Computing, 43(4):1342–1362, 2014.
[10] J. Cheriyan, S. Vempala, and A. Vetta. An approximation algorithm for the minimum-cost k-vertex
connected subgraph. SIAM J. Comput., 32(4):1050–1055, 2003. Preliminary version in STOC’02.
[11] J. Cheriyan and A. Vetta. Approximation algorithms for network design with metric costs. SIAM
Journal on Discrete Mathematics, 21(3):612–636, 2007.
[12] G. Dahl. Directed steiner problems with connectivity constraints. Discrete Applied Mathematics,
47(2):109–128, 1993.
[13] J. Edmonds. Edge-disjoint branchings. Combinatorial algorithms, 9(91-96):2, 1973.
[14] J. Fakcharoenphol and B. Laekhanukit. An o(log2k) -approximation algorithm for the k-vertex connected spanning subgraph problem. SIAM Journal on Computing, 41(5):1095–1109, 2012.
[15] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree
metrics. Journal of Computer and System Sciences, 69(3):485–497, 2004.
[16] M. Feldman, G. Kortsarz, and Z. Nutov. Improved approximation algorithms for directed Steiner
forest. Journal of Computer and System Sciences, 78(1):279–292, 2012.
12

[17] L. Fleischer, K. Jain, and D. P. Williamson. Iterative rounding 2-approximation algorithms for
minimum-cost vertex connectivity problems. Journal of Computer and System Sciences, 72(5):838–
867, 2006.
[18] G. N. Frederickson and J. JáJá. Approximation algorithms for several graph augmentation problems.
SIAM J. Comput., 10(2):270–283, 1981.
[19] T. Fukunaga, Z. Nutov, and R. Ravi. Iterative rounding approximation algorithms for degree-bounded
node-connectivity network design. SIAM J. Comput., 44(5):1202–1229, 2015. Preliminary version in
FOCS’12.
[20] H. N. Gabow. On the linfinity -norm of extreme points for crossing supermodular directed network lps.
Math. Program., 110(1):111–144, 2007.
[21] N. Garg, G. Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group Steiner
tree problem. Journal of Algorithms, 37(1):66–84, 2000.
[22] L. Georgiadis and R. E. Tarjan. Dominator tree certification and divergent spanning trees. ACM
Transactions on Algorithms, 12(1):11, 2016. Preliminary version in SODA’05.
[23] M. X. Goemans, A. V. Goldberg, S. A. Plotkin, D. B. Shmoys, É. Tardos, and D. P. Williamson.
Improved approximation algorithms for network design problems. In Proceedings of the Fifth Annual
ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia., pages 223–
232, 1994.
[24] A. Gupta, R. Krishnaswamy, and R. Ravi. Tree embeddings for two-edge-connected network design.
In SODA, pages 1521–1538, 2010.
[25] E. Halperin and R. Krauthgamer. Polylogarithmic inapproximability. In STOC, pages 585–594, 2003.
[26] C. S. Helvig, G. Robins, and A. Zelikovsky. An improved approximation scheme for the group Steiner
problem. Networks, 37(1):8–20, 2001.
[27] A. Huck. Disproof of a conjecture about independent branchings in k-connected directed graphs.
Journal of Graph Theory, 20(2):235–239, 1995.
[28] K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001.
[29] R. Khandekar, G. Kortsarz, and Z. Nutov. Approximating fault-tolerant group-steiner problems. Theorerical Computer Science, 416:55–64, 2012.
[30] S. Khuller and B. Raghavachari. Improved approximation algorithms for uniform connectivity problems. Journal of Algorithms, 21(2):434–450, 1996.
[31] G. Kortsarz and Z. Nutov. Approximating k-node connected subgraphs via critical graphs. SIAM J.
Comput., 35(1):247–257, 2005. Preliminary version in STOC’04.
[32] G. Kortsarz and Z. Nutov. Approximating minimum-cost connectivity problems. In Handbook of
Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC, 2007.

13

[33] E. R. Kovács. Network coding. Master’s thesis, Eötvös Loránd University, Budapest, 2007. (in
Hungary).
[34] B. Laekhanukit. Parameters of two-prover-one-round game and the hardness of connectivity problems.
In SODA, pages 1626–1643, 2014.
[35] B. Laekhanukit. An improved approximation algorithm for the minimum cost subset k-connected
subgraph problem. Algorithmica, 72(3):714–733, 2015.
[36] B. Laekhanukit. Approximating directed Steiner problems via tree embedding. ICALP, pages 74:1–13,
2016.
[37] V. Melkonian and É. Tardos. Algorithms for a network design problem with crossing supermodular
demands. Networks, 43(4):256–265, 2004.
[38] Z. Nutov.
Approximability status of survivable network problems.
http://www.openu.ac.il/home/nutov/SN.pdf.

Preprint available at

[39] Z. Nutov.
Approximability status of survivable network problems.
http://www.openu.ac.il/home/nutov/kCS.pdf.

Preprint available at

[40] Z. Nutov. Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM
Transactions on Algorithms, 9(1):1, 2012.
[41] Z. Nutov. Approximating subset k-connectivity problems. Journal of Discrete Algorithms, 17:51–59,
2012.
[42] Z. Nutov. Degree constrained node-connectivity problems. Algorithmica, 70(2):340–364, 2014.
[43] H. Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In STOC,
pages 255–264, 2008.
[44] T. Rothvoß. Directed Steiner tree and the Lasserre hierarchy. CoRR, abs/1111.5473, 2011.
[45] K. Steiglitz, P. Weiner, and D. Kleitman. The design of minimum-cost survivable networks. IEEE
Transactions on Circuit Theory, 16(4):455–460, 1969.
[46] A. Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem.
Algorithmica, 18(1):99–110, 1997.
[47] L. Zosin and S. Khuller. On directed Steiner trees. In Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 59–63,
2002.

14

A

A Reduction from 2-DSS to 2-DST

It is known that an approximation algorithm for k-DST implies an approximation algorithm for k-DSS for
both edge and vertex connectivity versions [30, 35, 41]. The reductions of these two cases are slightly
different, but they are based on the same technique.
Edge-Connectivity. We first consider the edge-connectivity version of 2-DSS and 2-DST. It is known that
an α-approximation algorithm for k-DST yields an approximation algorithm for k-DSS with a loss of factor
two [30]. To be precise, let G be an input graph of k-DSS and S ⊆ V (G) be a set of terminals, and let A
be an α-approximation algorithm for k-DST. We form an instance of k-DST by taking an arbitrary terminal
r ∈ S as a root vertex of k-DST and taking S ′ = S − {r} as a set of terminals. Then we solve in-rootedversion and out-rooted-version of k-DST, separately, and take the union of the two solutions. Thus, every
terminal t ∈ S − {r} has k edge-disjoint paths to and from the root. It then follows by the transitivity of
edge-connectivity that there are k edge-disjoint paths joining every pair of terminals. Therefore, this gives a
2α-approximation algorithm for k-DSS.
Vertex-Connectivity. Now, we consider the case of vertex-connectivity of k-DSS and k-DST. The reduction is more involved than the case of edge-connectivity since vertex-connectivity does not have the
transitivity property. Here we need to pay an extra factor of k2 . In particular, as shown in [30, 35, 41], an
α-approximation algorithm for k-DST implies (2α + k2 )-approximation algorithm for k-DSS.
The reduction is as follows. Let G be an input graph of k-DSS and S ⊆ V (G) be a set of terminals, and
let A be an α-approximation algorithm for k-DST. First, we take any subset R of k vertices from S. The
we apply any (efficient) min-cost k-flow algorithms on every pair of vertices in R and obtain an set of edges
E ′ . We then form an instance of the vertex-connectivity version of k-DST by adding an auxiliary vertex r
as a root and joining it to every vertex of R, and then taking S ′ = S − R as a set of terminals. We apply the
algorithm for k-DST for both in-version and out-version and then take the union of these solutions with E ′
(that we obtained from the min-cost k-flow algorithm). It is not hard to see that the cost of the solution is at
most (α + k2 ) times the optimum, and the feasibility can be verified using a cut-based argument. (See [35]
for more details.)

B Bicriteria Approximation Algorithm for a Variant of k-GST
In this section, we present an application of our algorithm for 2-DST to a variant of k-GST proposed by
Gupta et al. [24]. Recall that in k-GST we wish to find a min-cost subgraph H of a weighted undirected
graph G = (V, E) that has k edge-disjoint paths from a given root r to each group St ⊆ V , t = 1, 2, . . . , h.
In the mentioned variant, we require that all such paths end at the same vertex st ∈ St . We refer to
this problem as k-GST*. Gupta et al. presented an O(log3 n logh log log n) approximation for the case
of 2-GST*, and the algorithm of Chalermsook et al.[5] gives a bicriteria approximation algorithm4 that
provides connectivity Ω(k/ log n). We present an alternative bicriteria approximation algorithm that outputs
a solution with cost at most O(k · D 3 log D · h2/D · log n) times the optimum and provides connectivity at
least ⌈k/2⌉.
Our algorithm is now based on decomposing the optimal solution to k-GST* into a collection of k trees
T1 , . . . , Tk such that for any set of edges F of size ⌈k/2⌉− 1 in G, there exists a tree Ti that contains no edge
in F . The algorithm and analysis then follow along the same line as that for 2-DST. But, we need to run the
4

In [5], the authors considered the standard version of k-GST, but the algorithm also works for the variant of k-GST*.

15

outer loop of the rounding procedure (Step 2 of Algorithm 1) for O(kD ln n) times instead of O(D ln n)
because the number of edge-cuts that we have to consider is now nO(k) . This incurs an extra factor of O(k)
in the approximation guarantee.
It remains to show that the above decomposition exists. Observe that an optimal solution H to k-GST
forms a graph that is k-edge-connected on the set S ∗ = {r, s1 , . . . , sh }. Thus, if we replace each undirected
edge {u, v} by two directed edges uv and vu, then we have a directed graph Ĥ such that S ∗ is k (strongly)
edge-connected on Ĥ. We may apply a splitting-off theorem to get rid of all the Steiner vertices (vertices in
V (H) − S ∗ ), resulting in a directed k-edge-connected graph Ĥ ′ whose vertex-set is S ∗ . Then, by Edmonds’
Disjoint Arborescence Packing Theorem [13], we know that Ĥ ′ contains k edge-disjoint (out) spanning
arborescences T̂1′ , . . . , T̂k′ . Mapping them back to the original graph H, we have a collection of k trees
T = {T1 , . . . , Tk } such that any undirected edge {u, v} is contained in at most two trees in T. So, for any
set of ⌈k/2⌉ − 1 edges F ⊆ E(H), there must exist a tree Ti ∈ T that contains no edge of F and connects
every terminal to the root. Therefore, we have the decomposition as claimed.
Note that this is an evidence that a weaker version of the decomposition theorem (Theorem 5) might
exist. The decomposition implies the following theorem.
Theorem 13 (Bicriteria k-GST*). For any D ∈ [log2 h], there exists a randomized approximation algorithm
that runs in nO(D) time and outputs a feasible solution H to k-GST* with cost O(k · D 3 log D · h2/D · log n)
times the optimum and provides connectivity at least ⌈k/2⌉.
Remark. For the case of 2-GST, our algorithm gives a “true” approximation algorithm for both 2-GST and
2-GST*. To see this, we split each (undirected) edge {u, v} of the input graph into two directed edges uv
and vu with the same cost. We then add a terminal st for each group Ŝt and joining each vertex v ∈ Ŝt
to st by a (directed) edge vst with zero-cost. This reduces 2-DST to 2-GST, but we have a small issue
that the composition in Theorem 5 may give trees T1 and T2 such that the corresponding two edge-disjoint
r, st -paths P1 and P2 contain both uv and vu edges. However, we may use a stronger form of Theorem 5
where we additionally require that the paths P1 and P2 are strongly divergent, i.e., only one of uv and uv can
be contained in E(P1 ) ∪ E(P2 ) [22, 33]. Our approximation guarantee matches the results in [24] (albeit,
with worse running time).

16

