arXiv:1606.01342v2 [cs.DS] 27 Aug 2016

Recoverable robust spanning tree problem under interval
uncertainty representations
Mikita Hradovich† , Adam Kasperski‡ , Pawel Zieliński†
†

Faculty of Fundamental Problems of Technology,
Wroclaw University of Technology, Wroclaw, Poland
‡
Faculty of Computer Science and Management,
Wroclaw University of Technology, Wroclaw, Poland
{mikita.hradovich,adam.kasperski,pawel.zielinski}@pwr.edu.pl

Abstract
This paper deals with the recoverable robust spanning tree problem under interval
uncertainty representations. A strongly polynomial time, combinatorial algorithm for the
recoverable spanning tree problem is first constructed. This problem generalizes the incremental spanning tree problem, previously discussed in literature. The algorithm built
is then applied to solve the recoverable robust spanning tree problem, under the traditional interval uncertainty representation, in polynomial time. Moreover, the algorithm
allows to obtain several approximation results for the recoverable robust spanning tree
problem under the Bertsimas and Sim interval uncertainty representation and the interval
uncertainty representation with a budget constraint.

Keywords: robust optimization; interval data; recovery; spanning tree

1

Introduction

Let G = (V, E), |V | = n, |E| = m, be an undirected graph and let Φ be the set of all spanning
trees of G. In the minimum spanning tree problem, a cost is specified for each edge, and we
seek a spanning tree in G of the minimum total cost. This problem is well known and can be
solved efficiently by using several polynomial time algorithms (see, e.g., [1, 18]).
In this paper, we first study the recoverable spanning tree problem (Rec ST for short).
Namely, for each edge e ∈ E, we are given a ﬁrst stage cost Ce and a second stage cost ce
(recovery stage cost). Given a spanning tree X ∈ Φ, let ΦkX be the set of all spanning trees
Y ∈ Φ such that |Y \ X| ≤ k (the recovery set), where k is a fixed integer in [0, n − 1], called
the recovery parameter. Note that ΦkX can be seen as a neighborhood of X containing all
spanning trees which can be obtained from X by exchanging up to k edges. The Rec ST
problem can be stated formally as follows:
!
X
X
Rec ST : min
Ce + min
(1)
ce .
X∈Φ

e∈X

Y ∈ΦkX

e∈Y

We thus seek a first stage spanning tree X ∈ Φ and a second stage spanning tree Y ∈ ΦkX , so
that the total cost of X and Y for Ce and ce , respectively, is minimum. Notice that Rec ST
1

generalizes the following incremental spanning tree problem, investigated in [8]:
X
Inc ST : min
ce ,
Y ∈Φkb

X

(2)

e∈Y

b ∈ Φ is a given spanning tree. So, we wish to find an improved spanning tree Y
where X
b determined by Φk . Several interesting
with the minimum cost, within a neighborhood of X
b
X
practical applications of the incremental network optimization were presented in [8]. It is
worth pointing out that Inc ST can be seen as the Rec ST problem with a fixed first
b whereas in Rec ST both the first and the second stage trees are
stage spanning tree X,
unknown. It has been shown in [8] that Inc ST can be solved in strongly polynomial time
by applying the Lagrangian relaxation technique. On the other hand, no strongly polynomial
time combinatorial algorithm for Rec ST has been known to date. Thus proposing such an
algorithm for this problem is one of the main results of this paper.
The Rec ST problem, beside being an interesting problem per se, has an important connection with a more general problem. Namely, it is an inner problem in the recoverable robust
model with uncertain recovery costs, discussed in [4, 5, 6, 7, 15, 17]. Indeed, the recoverable
spanning tree problem can be generalized by considering its robust version. Suppose that
the second stage costs ce , e ∈ E, are uncertain and let U contain all possible realizations of
the second stage costs, called scenarios. We will denote by cSe the second stage cost of edge
e ∈ E under scenario S ∈ U , where S = (cSe )e∈E is a cost vector. In the recoverable robust
spanning tree problem (Rob Rec ST
P for short), we choose an initial spanning tree X in the
first stage, with the cost equal to e∈X Ce . Then, after scenario S ∈ U reveals, X can be
k
modified by exchanging at most k edges, obtaining
Pa newS spanning tree Y ∈ ΦX . The second
stage cost of Y under scenario S ∈ U is equal to e∈Y ce . Our goal is to find a pair of trees
X andPY such that
P |X \ Y | ≤ k, which minimizes the sum of the first and the second stage
costs e∈X Ce + e∈Y cSe in the worst case. The Rob Rec ST problem is defined formally
as follows:
!
X
X
(3)
cSe .
Ce + max min
Rob Rec ST : min
X∈Φ

e∈X

S∈U Y ∈Φk
X

e∈Y

If Ce = 0 for each e ∈ E and k = 0, then Rob Rec ST is equivalent to the following
min-max spanning tree problem, examined in [2, 13, 12], in which we seek a spanning tree
that minimizes the largest cost over all scenarios:
X
Min-Max ST : min max
cSe .
(4)
X∈Φ S∈U

e∈X

If Ce = 0 for each e ∈ E and k = n − 1, then Rob Rec ST becomes the following
adversarial problem [17] in which an adversary wants to find a scenario which leads to the
greatest increase in the cost of the minimum spanning tree:
X
Adv ST : max min
cSe .
(5)
S∈U Y ∈Φ

e∈Y

We now briefly recall the known complexity results on Rob Rec ST. It turns out that
its computational complexity highly relies on the way of defining the scenario set U . There
are two popular methods of representing U , namely the discrete and interval uncertainty
representations. For the discrete uncertainty representation (see, e.g., [13]), scenario set,
2

denoted by U D , contains K explicitly listed scenarios, i.e. U D = {S1 , S2 , . . . , SK }. In this
case, the Rob Rec ST problem is known to be NP-hard for K = 2 and any constant k [11].
Furthermore, it becomes strongly NP-hard and not at all approximable when both K and k
are a part of the input [11]. It is worthwhile to mention that Min-Max ST is NP hard even
when K = 2 and becomes strongly NP-hard and not approximable within O(log1−ǫ n) for
any ǫ > 0 unless NP ⊆ DTIME(npoly log n ), when K is a part of input [13, 12]. It admits an
FPTAS, when K is a constant [2] and is approximable within O(log2 n), when K is a part of
the input [12]. The Adv ST problem, under scenario set U D , is polynomially solvable, since
it boils down to solving K traditional minimum spanning tree problems.
For the interval uncertainty representation, which is considered in this paper, one assumes
that the second stage cost of each edge e ∈ E is known to belong to the closed interval
[ce , ce + de ], where ce is a nominal cost of e ∈ E and de ≥ 0 is the maximum deviation of the
cost of e from its nominal value. In the traditional case U , denoted by U I , is the Cartesian
product of all these intervals [13], i.e.
U I = {S = (cSe )e∈E : cSe ∈ [ce , ce + de ], e ∈ E}.

(6)

In [4] a polynomial algorithm for the recoverable robust matroid basis problem under
scenario set U I was constructed, provided that the recovery parameter k is constant. In consequence, Rob Rec ST under U I is also polynomially solvable for constant k. Unfortunately,
the algorithm proposed in [4] is exponential in k. Interestingly, the corresponding recoverable
robust version of the shortest path problem (Φ is replaced with the set of all s − t paths in G)
has been proven to be strongly NP-hard and not at all approximable even if k = 2 [5]. It has
been recently shown in [10] that Rob Rec ST under U I is polynomially solvable when k is a
part of the input. In order to prove this result, a technique called the iterative relaxation of
a linear programming formulation, whose framework was described in [14], has been applied
This technique, however, does not imply directly a strongly polynomial algorithm for Rob
Rec ST, since it requires the solution of a linear program.
In [3] a popular and commonly used modification of the scenario set U I has been proposed.
The new scenario set, denoted as U1I (Γ), is a subset of U I such that under each scenario in
U1I (Γ), the costs of at most Γ edges are greater than their nominal values ce , where Γ is
assumed to be a fixed integer in [0, m]. Scenario set U1I (Γ) is formally defined as follows:
X
δe ≤ Γ}.
(7)
U1I (Γ) = {S = (cSe )e∈E : cSe ∈ [ce , ce + δe de ], δe ∈ {0, 1}, e ∈ E,
e∈E

The parameter Γ allows us to model the degree of uncertainty. When Γ = 0, then we get
Rec ST (Rob Rec ST with one scenario S = (ce )e∈E ). On the other hand, when Γ = m,
then we get Rob Rec ST under the traditional interval uncertainty U I . It turns out that
the Adv ST problem under U1I (Γ) is strongly NP-hard (it is equivalent to the problem of
finding Γ most vital edges) [17, 16, 9]. Consequently, the more general Rob Rec ST problem
is also strongly NP-hard. Interestingly, the corresponding Min-Max ST problem with U1I (Γ)
is polynomially solvable [3].
Yet another interesting way of defining scenario set, which allows us to control the amount
of uncertainty, is called the scenario set with a budget constraint (see, e.g,. [17]). This scenario
set, denoted as U2I (Γ), is defined as follows:
X
U2I (Γ) = {S = (cSe )e∈E : cSe = ce + δe , δe ∈ [0, de ], e ∈ E,
δe ≤ Γ},
(8)
e∈E

3

where Γ ≥ 0 is a a fixed parameter that can be seen as a budget of an adversary, and represents
the maximum total increase of the edge costs from their nominal values. Obviously, if Γ is
sufficiently large, then U2I (Γ) reduces to the traditional interval uncertainty representation U I .
The computational complexity of Rob Rec ST for scenario set U2I is still open. We only know
that its special cases, namely Min-Max ST and Adv ST, are polynomially solvable [17].
In this paper we will construct a combinatorial algorithm for Rec ST with strongly
polynomial running time. We will apply this algorithm for solving Rob Rec ST under
scenario set U I in strongly polynomial time. Moreover, we will show how the algorithm for
Rec ST can be used to obtain several approximation results for Rob Rec ST, under scenario
sets U1I (Γ) and U2I (Γ). This paper is organized as follows. Section 2 contains the main result
of this paper – a combinatorial algorithm for Rec ST with strongly polynomial running time.
Section 3 discusses Rob Rec ST under the interval uncertainty representations U I , U1I (Γ),
and U2I (Γ).

2

The recoverable spanning tree problem

In this section we construct a combinatorial algorithm for Rec ST with strongly polynomial
running time. Since |X| = n − 1 for each X ∈ Φ, Rec ST (see (1)) is equivalent to the
following mathematical programming problem:
X
X
ce
Ce +
min
e∈Y

e∈X

(9)

|X ∩ Y | ≥ L,
X, Y ∈ Φ,

s.t.

where L = n − 1 − k. Problem (9) can be expressed as the following MIP model:
X
X
Opt = min
Ce xe +
ce ye
e∈E

s.t.

X

(10)

e∈E

xe = n − 1,

(11)

e∈E

X

xe ≤ |U | − 1,

∀U ⊂ V,

(12)

e∈E(U )

X

ye = n − 1,

(13)

e∈E

X

ye ≤ |U | − 1,

∀U ⊂ V,

(14)

xe − ze ≥ 0,

∀e ∈ E,

(15)

ye − ze ≥ 0,
X
ze ≥ L,

∀e ∈ E,

(16)

e∈E(U )

(17)

e∈E

xe , ye , ze ≥ 0, integer

∀e ∈ E,

(18)

where E(U ) stands for the set of edges that have both endpoints in U ⊆ V . We first apply the
Lagrangian relaxation (see, e.g., [1]) to (10)-(18) by relaxing the cardinality constraint (17)

4

with a nonnegative multiplier θ. We also relax the integrality constraints (18). We thus get
the following linear program (with the corresponding dual variables which will be used later):
X
X
X
φ(θ) = min
Ce xe +
ce ye − θ
ze + θL
(19)
e∈E

s.t.

X

e∈E

−

e∈E

e∈E

xe = n − 1,
X

[µ],

xe ≥ −(|U | − 1),

∀U ⊂ V,

[wU ],

e∈E(U )

X

e∈E

−

ye = n − 1,
X

[ν],

ye ≥ −(|U | − 1),

∀U ⊂ V,

[vU ],

xe − ze ≥ 0,

∀e ∈ E,

[αe ],

ye − ze ≥ 0,

∀e ∈ E,

[βe ],

xe , ye , ze ≥ 0,

∀e ∈ E.

e∈E(U )

For any θ ≥ 0, the Lagrangian function φ(θ) is a lower bound on Opt. It is well-known
that φ(θ) is concave and piecewise linear. By the optimality test (see, e.g., [1]), we obtain the
following theorem:
Theorem 1. Let (xe , ye , ze )e∈E be an optimal solution to (19) for
Psome θ ≥ 0, feasible
to (11)-(18) and satisfying the complementary slackness condition θ( e∈E ze − L) = 0. Then
(xe , ye , ze )e∈E is optimal to (10)-(18).
Let (X, Y ), X, Y ∈ Φ, be a pair of spanning trees of G (a pair for short). This pair
corresponds to a feasible 0 − 1 solution to (19), defined as follows: xe = 1 for e ∈ X,
ye = 1 for e ∈ Y , and ze = 1 for e ∈ X ∩ Y ; the values of the remaining variables are
set to 0. From now on, by a pair (X, Y ) we also mean a feasible solution to (19) defined
as above. Given a pair (X, Y ) with the corresponding solution (xe , ye , ze )e∈E , let us define
the partition (EX , EY , EZ , EW ) of the set of the edges E in the following way: EX = {e ∈
E : xe = 1, ye = 0}, EY = {e ∈ E : ye = 1, xe = 0}, EZ = {e ∈ E : xe = 1, ye = 1}
and EW = {e ∈ E : xe = 0, ye = 0}. Thus equalities: X = EX ∪ EZ , Y = EY ∪ EZ and
EZ = X ∩ Y hold. Our goal is to establish some sufficient optimality conditions for a given
pair (X, Y ) in the problem (19). The dual to (19) has the following form:
X
X
φD (θ) = max −
(|U | − 1)wU + (n − 1)µ −
(|U | − 1)vU + (n − 1)ν + θL
(20)
U ⊂V

s.t. −

X

U ⊂V

wU + µ ≤ Ce − αe ,

∀e ∈ E,

vU + ν ≤ ce − βe ,

∀e ∈ E,

{U ⊂V : e∈E(U )}

−

X

{U ⊂V : e∈E(U )}

αe + βe ≥ θ,

∀e ∈ E,

wU , vU ≥ 0,

U ⊂ V,

αe , βe ≥ 0,

∀e ∈ E.
5

Lemma 1. The dual problem (20) can be rewritten as follows:
φD (θ) =

max

{αe ≥0,βe ≥0 : αe +βe ≥θ, e∈E}

min

X∈Φ

X

(Ce − αe ) + min

Y ∈Φ

e∈X

X

!

(ce − βe )

e∈Y

+ θL.

(21)

Proof. Fix some αe and βe such that αe + βe ≥ θ for each e ∈ E in (20). For
P these constant
values ofPαe and βe , e ∈ E, using the dual to (20), we arrive to minX∈Φ e∈X (Ce − αe ) +
minY ∈Φ e∈Y (ce − βe ) + θL and the lemma follows.
Lemma 1 allows us to establish the following result:

Theorem 2 (Sufficient pair optimality conditions). A pair (X, Y ) is optimal to (19)
for a ﬁxed θ ≥ 0 if there exist αe ≥ 0, βe ≥ 0 such that αe + βe = θ for each e ∈ E and
(i) X is a minimum spanning tree for the costs Ce − αe , Y is a minimum spanning tree for
the costs ce − βe ,
(ii) αe = 0 for each e ∈ EX , βe = 0 for each e ∈ EY .
Proof. By the primal-dual relation, the inequality φD (θ) ≤ φ(θ) holds. Using (21), we obtain
X
X
X
X
X
φD (θ) ≥
(Ce − αe ) +
(ce − βe ) + θL =
Ce +
ce +
(Ce + ce − θ) + θL
e∈X

=

X

Ce +

e∈EX

=

X

e∈X

Ce +

X

e∈EZ

X

e∈Y

Ce +

X

e∈EY

ce +

X

e∈EX

e∈EY

e∈EZ

ce − θ|EZ | + θL

e∈EZ

ce − θ|EZ | + θL = φ(θ).

e∈Y

The Weak Duality Theorem implies the optimality of (X, Y ) in (19) for a fixed θ ≥ 0.
Lemma 2. A pair (X, Y ), which satisﬁes the suﬃcient pair optimality conditions for θ = 0,
can be computed in polynomial time.
Proof. Let X be a minimum spanning tree for the costs Ce and Y be a minimum spanning
tree for the costs ce , e ∈ E. Since θ = 0, we set αe = 0, βe = 0 for each e ∈ E. It is clear that
(X, Y ) satisfies the sufficient pair optimality conditions.
Assume that (X, Y ) satisfies the sufficient pair optimality conditions for some θ ≥ 0. If,
for this pair, |EZ | ≥ L and θ(|EZ | − L) = 0, then we are done, because by Theorem 1, the
pair (X, Y ) is optimal to (10)-(18). Suppose that |EZ | < L ((X, Y ) is not feasible to (10)-(18)).
We will now show a polynomial time procedure for finding a new pair (X ′ , Y ′ ), which satisfies
the sufficient pair optimality conditions and |EZ ′ | = |EZ | + 1. This implies a polynomial
time algorithm for the problem (10)-(18), since it is enough to start with a pair satisfying
the sufficient pair optimality conditions for θ = 0 (see Lemma 2) and repeat the procedure at
most L times, i.e. until |EZ ′ | = L.
Given a spanning tree T in G = (V, E) and edge e = {k, l} 6∈ T , let us denote by PT (e)
the unique path in T connecting nodes k and l. It is well known that for any f ∈ PT (e),
T ′ = T ∪ {e} \ {f } is also a spanning tree in G. We will say that T ′ is the result of a move
on T .
6

Consider a pair (X, Y ) that satisfies the sufficient pair optimality conditions for some fixed
θ ≥ 0. Set Ce∗ = Ce − αe and c∗e = ce − βe for every e ∈ E, where αe and βe , e ∈ E, are
the numbers which satisfy the conditions in Theorem 2. Thus, by Theorem 2(i) and the path
optimality conditions (see, e.g., [1]), we get the following conditions which must be satisfied
by (X, Y ):
for every e ∈
/X

Ce∗ ≥ Cf∗

for every f ∈ PX (e),

(22a)

for every e ∈
/Y

c∗e

for every f ∈ PY (e).

(22b)

≥

c∗f

We now build a so-called admissible graph GA = (V A , E A ) in two steps. We first associate
with each edge e ∈ E a node ve and include it to V A , |V A | = |E|. We then add arc (ve , vf )
to E A if e ∈
/ X, f ∈ PX (e) and Ce∗ = Cf∗ . This arc is called an X-arc. We also add arc
(vf , ve ) to E A if e ∈
/ Y , f ∈ PY (e) and c∗e = c∗f . This arc is called an Y -arc. We say that
ve ∈ V A is admissible if e ∈ EY , or ve is reachable from a node vg ∈ V A , such that g ∈ EY ,
by a directed path in GA . In the second step we remove from GA all the nodes which are not
admissible, together with their incident arcs. An example of an admissible graph is shown in
Figure 1. Each node of this admissible graph is reachable from some node vg , g ∈ EY . Note
that the arcs (ve7 , ve6 ) and (ve7 , ve10 ) are not present in GA , because ve7 is not reachable from
any node vg , g ∈ EY . These arcs have been removed from GA in the second step.
Observe that each X-arc (ve , vf ) ∈ E A represents a move on X, namely X ′ = X ∪{e}\{f }
is a spanning tree in G. Similarly, each Y -arc (ve , vf ) ∈ E A represents a move on Y , namely
Y ′ = Y ∪ {f } \ {e} is a spanning tree in G. Notice that the cost, with respect to Ce∗ , of X ′
is the same as X and the cost, with respect to c∗e , of Y ′ is the same as Y . So, the moves
indicated by X-arcs and Y -arcs preserve the optimality of X and Y , respectively. Observe
that e ∈
/ X or e ∈ Y , which implies e ∈
/ EX . Also f ∈ X or f ∈
/ Y , which implies f ∈
/ EY .
Hence, no arc in E A can start in a node corresponding to an edge in EX and no arc in E A
can end in a node corresponding to an edge in EY . Observe also that (ve , vf ) ∈ E A can be
both X-arc and Y -arc only if e ∈ EY and f ∈ EX . Such a case is shown in Figure 1 (see the
arc (ve1 , ve2 )). Since each arc (ve , vf ) ∈ E A represents a move on X or Y , e and f cannot
both belong to EW or EZ .
(a)

(b)
e1 (2; 2)

e6 (2; 3)

(Ce∗ ; c∗e )

ve1 EY
X; Y

X

X

v e2

Y
e10
(2; 2)

e7

e5

e3

(2; 2)

(2; 3)

(2; 3)

v e3 E Z

EX

Y

e2

X

(2; 2)

X

v e8

e4 (1; 5)

e8

v e6
e9

Y

EW

(2; 3)

EX

(5; 0)

v e5 E Y

X
X

ve10
EZ

Figure 1: (a) A pair (X, Y ) such that X = {e2 , e3 , e4 , e6 , e10 } and Y = {e1 , e3 , e5 , e9 , e10 }.
(b) The admissible graph GA for (X, Y ).
We will consider two cases: EX ∩{e ∈ E : ve ∈ V A } =
6 ∅ and EX ∩{e ∈ E : ve ∈ V A } = ∅.
The first case means that there is a directed path from ve , e ∈ EY , to a node vf , f ∈ EX ,
7

in the admissible graph GA and in the second case no such a path exists. We will show that
in the first case it is possible to find a new pair (X ′ , Y ′ ) which satisfies the sufficient pair
optimality conditions and |EZ ′ | = |EZ | + 1. The idea will be to perform a sequence of moves
on X and Y , indicated by the arcs on some suitably chosen path from ve , e ∈ EY , to vf ,
f ∈ EX in the admissible graph GA . Let us formally handle this case.
Lemma 3. If EX ∩ {e ∈ E : ve ∈ V A } =
6 ∅, then there exists a pair (X ′ , Y ′ ) with |EZ ′ | =
|EZ | + 1, which satisﬁes the suﬃcient pair optimality conditions for θ.
Proof. We begin by introducing the notion of a cycle graph G(T ) = (V T , AT ), corresponding
to a given spanning tree T of graph G = (V, A). We build G(T ) as follows: we associate with
each edge e ∈ E a node ve and include it to V T , |E| = |V T |; then we add arc (ve , vf ) to AT
if e 6∈ T and f ∈ PT (e). An example is shown in Figure 2.
(a)

(b)
f1
f2

f4
f3

e1
f5
f6

ve2

ve1

e2

vf1

vf6

vf7

vf5

vf2

vf3

vf4

e3
f7

ve3

Figure 2: (a) A graph G with a spanning tree T (the solid lines). (b) The cycle graph G(T ).
Claim 1. Given a spanning tree T of G, let F = {(ve1 , vf1 ), (ve2 , vf2 ), . . . , (veℓ , vfℓ )} be a
subset of arcs of G(T ), where all vei and vfi (resp. ei and fi ), i ∈ [ℓ], are distinct. If
T ′ = T ∪ {e1 , . . . , eℓ } \ {f1 , . . . , fℓ } is not a spanning tree, then G(T ) contains a subgraph
depicted in Figure 3, where {j1 , . . . , jκ } ⊆ [ℓ].
vej1

vfjκ

vfj1

vej2

vfj3

vejκ

vfj2

vej3

Figure 3: A subgraph of G(T ) from Claim 1.
Let us illustrate Claim 1 by using the sample graph in Figure 2. Suppose that F =
{(ve1 , vf5 ), (ve2 , vf2 ), (ve3 , vf3 )}. Then T ′ = T ∪ {e1 , e2 , e3 , } \ {f5 , f2 , f3 } is not a spanning tree
and G(T ) contains the subgraph composed of the following arcs (see Figure 2):
(ve1 , vf2 ), (ve2 , vf2 ), (ve2 , vf3 ), (ve3 , vf3 ), (ve3 , vf5 ), (ve1 , vf5 ).
Proof of Claim 1. We form T ′ by performing a sequence of moves consisting in adding edges ei
and removing edges fi ∈ PT (ei ), i ∈ [ℓ]. Suppose that, at some step, a cycle appears, which
is formed by some edges from {e1 , . . . , eℓ } and the remaining edges of T (not removed from
T ). Such a cycle must appear, since otherwise T ′ would be a spanning tree. Let us relabel
the edges so that {e1 , . . . , es } are on this cycle, i.e. the first s moves consisting in adding
8

ei and removing fi create the cycle, i ∈ [s]. An example of such a situation for s = 4
is shown in Figure 4. The cycle is formed by the edges e1 , . . . , e4 and the paths Pv2 v3 ,
Pv4 v5 and Pv1 v6 in T . Consider the edge e1 = {v1 , v2 }. Because T is a spanning tree,
PT (e1 ) ⊆ Pv2 v3 ∪ PT (e2 ) ∪ PT (e3 ) ∪ Pv4 v5 ∪ PT (e4 ) ∪ Pv1 v6 . Observe that f1 ∈ PT (e1 ) cannot
belong to any of Pv2 v3 , Pv4 v5 and Pv1 v6 . If it would be contained in one of these paths, then
no cycle would be created. Hence, f1 must belong to PT (e2 ) ∪ PT (e3 ) ∪ PT (e4 ). The above
argument is general and, by using it, we can show that for each i ∈ [s], fi ∈ PT (ej ) for some
j ∈ [s] \ {i}.
(a)

(b)
f2
PT (e2 )

Pv 2 v 3

v f1
f1 2 PT (e1 )
f1 2 PT (e2 )

v e2

v f2
f2 2 PT (e2 )
f2 2 PT (e3 )

v e3

v f3
f3 2 PT (e3 )
f3 2 PT (e2 )

v3

v2
e1

e2

v1
e3

Pv 1 v 6
v6 e4

v e1

v5

PT (e3 ) f3

v4
Pv 4 v 5

PT (e4 )
f4

Figure 4: Illustration for the proof of Claim 1. (a) The bold lines represent paths in T
(not necessarily disjoint); f1 ∈ PT (e2 ) ∪ PT (e3 ) ∪ PT (e4 ). (b) The subgraph G′ (T ) with the
corresponding cycle.
We are now ready to build a subgraph depicted in Figure 3. Consider a subgraph G′ (T )
of the cycle graph G(T ) built as follows. The nodes of G′ (T ) are ve1 , . . . , ves , vf1 , . . . , vfs .
Observe that G′ (T ) has exactly 2s nodes, since all the edges e1 , . . . , es , f1 , . . . , fs are distinct
by the assumption of the claim. For each i ∈ [s] we add to G′ (T ) two arcs, namely (vei , vfi ),
fi ∈ PT (ei ) and (vej , vfi ), fi ∈ PT (ej ) for j ∈ [s] \ {i} (see Figure 4). The resulting graph
G′ (T ) is bipartite and has exactly 2s arcs. In consequence G′ (T ) (and thus G(T )) must
contain a cycle which is of the form depicted in Figure 3.
After this preliminary step, we can now return to the main proof. If EX ∩ {e ∈ E : ve ∈
V A} =
6 ∅, then, by the construction of the admissible graph, there exists a directed path in
A
G from a node ve , e ∈ EY , to a node vf , f ∈ EX . Let P be a shortest such a path from
ve to vf , i.e. a path consisting of the fewest number of arcs, called an augmenting path. We
need to consider the following cases:
1. The augmenting path P is of the form:
EY
ve

EX
→ vf

If (ve , vf ) is X-arc, then X ′ = X ∪ {e} \ {f } is an updated spanning tree of G such that
|X ′ ∩ Y | = |EZ | + 1. Furthermore X ′ is a minimum spanning tree for the costs Ce∗ and
the new pair (X ′ , Y ) satisfies the sufficient pair optimality conditions (EX ′ ⊆ EX , so
9

condition (ii) in Theorem 2 is not violated). If (ve , vf ) is Y -arc, then Y ′ = Y ∪ {f } \ {e}
is an updated spanning tree of G such that |X ∩ Y ′ | = |EZ | + 1. Also Y ′ is a minimum
spanning tree for the costs c∗e and the new pair (X, Y ′ ) satisfies the sufficient pair
optimality conditions. An example can be seen in Figure 1. There is a path ve1 → ve2
in the admissible graph. The arc (ve1 , ve2 ) is both X-arc and Y -arc. We can thus choose
one of the two possible moves X ′ = X ∪ {e1 } \ {e2 } or Y ′ = Y ∪ {e2 } \ {e1 }, which
results in (X ′ , Y ) or (Y ′ , X).
2. The augmenting path P is of the form:
EY

EZ
X

EW
Y

(a) ve1 → vf1 → ve2

EZ
X

EW
Y

→ vf 2 → ve 3

EZ
X

EW
Y

Y

→ vf 3 → · · · → ve ℓ

EZ
X

EX
Y

→ vfℓ → veℓ+1
EX
X

→ vf ℓ

(b)

Let X ′ = X ∪ {e1 , . . . , eℓ } \ {f1 , . . . , fℓ }. Let Y ′ = Y ∪ {e2 , . . . , eℓ+1 } \ {f1 , . . . fℓ } for case
(a), and Y ′ = Y ∪ {e2 , . . . , eℓ } \ {f1 , . . . fℓ−1 } for case (b). We now have to show that the
resulting pair (X ′ , Y ′ ) is a pair of spanning trees. Suppose that X ′ is not a spanning tree.
Observe that the X-arcs (ve1 , vf1 ), . . . , (veℓ , vfℓ ) belong to the cycle graph G(X). Thus,
by Claim 1, the cycle graph G(X) must contain a subgraph depicted in Figure 3, where
{j1 , . . . , jκ } ⊆ [ℓ]. An easy verification shows that all edges ei , fi , i ∈ {j1 , . . . , jκ } must
have the same costs with respect to Ce∗ . Indeed, if some costs are different, then there
exists an edge exchange which decreases the cost of X. This contradicts our assumption
that X is a minimum spanning tree with respect to Ce∗ . Finally, there must be an arc
(vei′ , vfi′′ ) in the subgraph such that i′ < i′′ . Since Ce∗i′ = Cf∗ ′′ , the arc (vei′ , vfi′′ ) is
i
present in the admissible graph GA . This leads to a contradiction with our assumption
that P is an augmenting path. Now suppose that Y ′ is not a spanning tree. We consider
only the case (a) since the proof of case (b) is just the same. For a convenience, let us
number the nodes vei on P from i = 0 to ℓ, so that Y ′ = {e1 , . . . , eℓ } \ {f1 , . . . , fℓ }. The
arcs (ve1 , vf1 ), . . . , (veℓ , vfℓ ), which correspond to the Y -arcs (vf1 , ve1 ), . . . , (vfℓ , veℓ ) of
P , belong to the cycle graph G(Y ). Hence, by Claim 1, G(Y ) must contain a subgraph
depicted in Figure 3, where {i1 , . . . , iκ } ⊆ [ℓ]. The rest of the proof is similar to the
proof for X. Namely, the edges ei and fi for i ∈ {i1 , . . . , iκ } must have the same costs
with respect to c∗e . Also, there must exist an arc (vei′ , vfi′′ ) in the subgraph such that
i′ > i′′ . In consequence, the arc (vfi′′ , vei′ ) belongs to the admissible graph, which
contradicts the assumption that P is an augmenting path.
An example of the case (a) is shown in Figure 5. Thus X ′ = X ∪ {e1 , e2 , e3 , e4 } \
{f1 , f2 , f3 , f4 } and Y ′ = Y ∪ {e2 , e3 , e4 , e5 } \ {f1 , f2 , f3 , f4 }. An example of the case
(b) is shown in Figure 6. In this example X ′ is the same as in the previous case and
Y ′ = Y ∪ {e2 , e3 , e4 } \ {f1 , f2 , f3 }.
It is easy to verify that |EZ ′ | = |X ′ ∩ Y ′ | = |EZ | + 1 holds (see also the examples in
Figures 5 and 6). The spanning trees X ′ and Y ′ are optimal for the costs Ce∗ and c∗e ,
respectively. Furthermore, EX ′ ⊆ EX and EY ′ ⊆ EY , so (X ′ , Y ′ ) satisfies the sufficient
pair optimality conditions (the condition (ii) in Theorem 2 is not violated).

10

(2,0)

(2,0)

(2,0)

(Ce∗ ; c∗e )
X

(0,2)

e1

f2 (1,1)

f1 (1,1)

Y

e2 (1,1)

(1,0)

e3 (1,1)

v e1 X

EZ

v f1

f4 (1,1)

(0,1)

e5

e4 (1,1)
(2,0)

(0,2)
EY

f3 (1,1)

EZ

EW

v e2 X

Y

(0,2)

v f2

(0,2)

EW

EZ

v e3 X

Y

v f3 Y

EW

v e4 X

EZ

v f4 Y

EX

v e5

Figure 5: A pair (X, Y ) and the corresponding admissible graph for the case 2a.
(2,0)

(2,0)

(2,0)

(Ce∗ ; c∗e )
X

(0,2)

f1 (1,1)

Y

f3 (1,1)

f2 (1,1)

f4 (1,2)
e2 (1,1)

(1,0)

e3 (1,1)

e4 (1,1)

e1
(0,2)
EY

ve1 X

EZ

EW

Y

v f1

v e2 X

(0,2)
EZ

v f2

Y

(0,2)

EW

EZ

v e3 X

EW

v e4 X

v f3 Y

EX

v f4

Figure 6: A pair (X, Y ) and the corresponding admissible graph for the case 2b.
3. The augmenting path P is of the form
EY

EW
Y

(a) ve1 → vf1

EZ
X

EW
Y

→ ve2 → vf2

EZ
X

EW
Y

→ ve 3 → vf 3

EZ
X

X

EW
Y

EX
X

→ . . . → veℓ → vfℓ → veℓ+1
EX
Y

→ vf ℓ

(b)

Let X ′ = X ∪ {f1 , . . . , fℓ } \ {e2 , . . . , eℓ+1 } for the case (a) and X ′ = X ∪ {f1 , . . . , fℓ−1 } \
{e2 , . . . eℓ } for the case (b). Let Y ′ = Y ∪ {f1 , . . . , fℓ } \ {e1 , . . . eℓ }. The proof that
X ′ and Y ′ are spanning trees follows by the same arguments as for the symmetric
case described in point 2. An example of the case (a) is shown in Figure 7. Thus
X ′ = X ∪ {f1 , f2 , f3 , f4 } \ {e2 , e3 , e4 , e5 } and Y ′ = Y ∪ {f1 , f2 , f3 , f4 } \ {e1 , e2 , e3 , e4 }.
An example for the case (b) is shown in Figure 8. The spanning tree Y ′ is the same
as in the previous case and X ′ = X ∪ {f1 , f2 , f3 } \ {e2 , e3 , e4 }. The equality |EZ ′ | =
|X ′ ∩ Y ′ | = |EZ | + 1 holds. Also, the trees X ′ and Y ′ are optimal for the costs Ce∗ and
c∗e , respectively, EX ′ ⊆ EX , EY ′ ⊆ EY , so (X ′ , Y ′ ) satisfies the sufficient pair optimality
conditions.

11

(0,2)

(0,2)

(0,2)

(Ce∗ ; c∗e )
X

(0,0)

f1 (1,1)

Y

e3 (1,1)

e2 (1,1)

(2,1)

f3 (1,1)

f2 (1,1)

e4

f4 (1,1)
(1,1)

e1

(0,0)
(2,0)

(2,0)
EY

EW

v e1 Y

v f1

(1,0)

e5

EZ

X

v e2

Y

(2,0)

EZ

EW

EW

v e3 Y

v f2 X

v f3 X

EZ

v e4

Y

EW

v f4 X

EX

v e5

Figure 7: A pair (X, Y ) and the corresponding admissible graph for the case 3a.
(0,2)

(0,2)

(0,2)

(Ce∗ ; c∗e )
X

(0,0)

Y

f1 (1,1)

f2 (1,1)

f3 (1,1)

e3

e4

f4 (1,1)
e1

e2 (1,1)

(2,1)

(1,1)

(2,0)

(2,0)
EY

v e1 Y

EW

v f1

X

EZ

v e2 Y

EW

v f2

X

EZ

v e3 Y

(1,1)

(2,0)
EW

v f3

X

EZ

v e4

EX

Y

v f4

Figure 8: A pair (X, Y ) and the corresponding admissible graph for the case 3b.
We now turn to the case EX ∩ {e ∈ E : ve ∈ V A } = ∅. Fix δ > 0 (the precise value of δ
will be specified later) and set:
Ce (δ) = Ce∗ − δ,
Ce (δ) =

Ce∗ ,

ce (δ) = c∗e
ce (δ) =

c∗e

ve ∈ V A ,
−δ

A

ve ∈
/V .

(23a)
(23b)

Lemma 4. There exists a suﬃciently small δ > 0 such that the costs Ce (δ) and ce (δ) satisfy
the path optimality conditions for X and Y , respectively, i.e:
for every e ∈
/X

Ce (δ) ≥ Cf (δ)

for every f ∈ PX (e),

(24a)

for every e ∈
/Y

ce (δ) ≥ cf (δ)

for every f ∈ PY (e).

(24b)

Proof. If Ce∗ > Cf∗ (resp. c∗e > c∗f ), e ∈
/ X, f ∈ PX (e) (resp. e ∈
/ Y, f ∈ PY (e)), then there
is δ > 0, such that after setting the new costs (23) the inequality Ce (δ) ≥ Cf (δ) (resp.
ce (δ) ≥ cf (δ)) holds. Hence, one can choose a sufficiently small δ > 0 such that after setting
12

the new costs (23), all the strong inequalities are not violated. Therefore, for such a chosen δ
it remains to show that all originally tight inequalities in (22) are preserved for the new costs.
Consider a tight inequality of the form:
/ X, f ∈ PX (e).
Ce∗ = Cf∗ , e ∈

(25)

On the contrary, suppose that Ce (δ) < Cf (δ). This is only possible when Ce (δ) = Ce∗ − δ and
Cf (δ) = Cf∗ . Hence and from the construction of the new costs, we have vf ∈
/ V A (see (23b))
A
A
A
and ve ∈ V (see (23a)). By (25), we obtain (ve , vf ) ∈ E . Thus vf ∈ V , a contradiction.
Consider a tight inequality of the form:
/ Y, f ∈ PY (e).
c∗e = c∗f , e ∈

(26)

On the contrary, suppose that ce (δ) < cf (δ). This is only possible when ce (δ) = c∗e − δ and
/ V A and vf ∈ V A (see (23)). From (26), it follows that
cf (δ) = c∗f . Thus we deduce that ve ∈
(vf , ve ) ∈ E A and so ve ∈ V A , a contradiction.
We are now ready to give the precise value of δ. We do this by increasing the value of δ
until some inequalities, originally not tight in (22), become tight. Namely, let δ∗ > 0 be the
smallest value of δ for which an inequality originally not tight becomes tight. Obviously, it
/ Y , e ∈ PY (f ).
/ X, f ∈ PX (e) or c∗f − δ∗ = c∗e for f ∈
occurs when Ce∗ − δ∗ = Cf∗ for e ∈
A
A
∗
By (23), ve ∈ V and vf ∈
/ V . Accordingly, if δ = δ , then at least one arc is added to GA .
Observe also that no arc can be removed from GA - the admissibility of the nodes remains
unchanged. It follows from the fact that each tight inequality for ve ∈ V A and vf ∈ V A is
still tight. This leads to the following lemma.
Lemma 5. If EX ∩{e ∈ E : ve ∈ V A } = ∅, then (X, Y ) satisﬁes the suﬃcient pair optimality
conditions for each θ ′ ∈ [θ, θ + δ∗ ].
Proof. Set θ ′ = θ + δ, δ ∈ [0, δ∗ ]. Lemma 4 implies that X is optimal for Ce (δ) and Y
is optimal for ce (δ). From (23) and the definition of the costs Ce∗ and c∗e , it follows that
Ce (δ) = Ce − α′e and ce (δ) = ce − βe′ , where α′e = αe + δ and βe′ = βe for each ve ∈ V A ,
α′e = αe and βe′ = βe + δ for each ve ∈
/ V A . Notice that α′e + βe′ = αe + βe + δ = θ + δ = θ ′ for
each e ∈ E. By (23), ce (δ) = ce for each e ∈ EY (recall that e ∈ EY implies ve ∈ V A ), and
thus βe = 0 for each e ∈ EY . Since EX ∩ {e ∈ E : ve ∈ V A } = ∅, Ce (δ) = Ce∗ = Ce holds for
each e ∈ EX , and so αe = 0 for each e ∈ EX . We thus have shown that there exist α′e , βe′ ≥ 0
such that α′e + βe′ = θ ′ for each e ∈ E satisfying the conditions (i) and (ii) in Theorem 2,
which completes the proof.
We now describe a polynomial procedure that, for a given pair (X, Y ) satisfying the
sufficient pair optimality conditions for some θ ≥ 0, finds a new pair of spanning trees (X ′ , Y ′ ),
which also satisfies the sufficient pair optimality conditions with |EZ′ | = |EZ | + 1. We start
by building the admissible graph GA = (V A , E A ) for (X, Y ). If this graph contains an
augmenting path, then by Lemma 3, we are done. Otherwise, we determine δ∗ and modify
the costs by using (23). Lemma 5 shows that (X, Y ) satisfies the sufficient pair optimality
conditions for θ + δ∗ . For δ∗ some new arcs are added to the admissible graph GA (all the
previous arcs must be still present in GA ). Thus GA is updated and we set Ce∗ := Ce (δ∗ ),
c∗e := ce (δ∗ ) for each e ∈ E, and θ := θ + δ∗ . We repeat this until there is an augmenting path
in GA = (V A , E A ). Note that such a path must appear after at most m = |E| iterations,
13

(Ce∗ ; c∗e )
X
Y

e4
(0,9)

(8,3)
e8
(2,5)
e5
e3 (8,3)
e7 (2,3)
(1,2)
(1,1)
e9
e2
(3,2)
(0,6)
e10 (5,9)
e6
(7,2)
e11
e1

(a)
θ=0

EY
v e8 Y

EW
v e7

EY
ve11
EY
v e3

e4
(0,8)

(7,3)
e8
(2,4)
e5
e3 (7,3)
e7 (1,3)
(1,1)
(1,0)
e9
e2
(3,1)
(0,5)
e10 (5,8)
1; θ = 1
e6
(6,2)
e11
e1

(b)
δ∗ =

EY
v e8 Y

EW
EZ
v e7 X v e5

EY
ve11
EY
v e3

e4
(0,7)

(6,3)
e8
(2,3)
e5
e3 (6,3)
e7 (0,3)
(0,1)
(1,-1)
e9
e2
(3,0)
(0,4)
e10 (5,7)
e6
1; θ = 2
(5,2)
e11
e1

(c)

δ∗ =

EY Y
v e8

EW
v e7 X

EY X
ve11

EX
ve10

EY
v e3 Y

EW
v e1

X

EZ
v e5
EX
v e6

Figure 9: Sample computations, X = {e2 , e4 , e5 , e6 , e9 , e10 } and Y = {e2 , e3 , e5 , e8 , e9 , e11 }.
which follows from the fact that at some step a node ve such that e ∈ EX must appear in
GA .
Sample computations are shown in Figure 9. We start with the pair (X, Y ), where
X = {e2 , e4 , e5 , e6 , e9 , e10 } and Y = {e2 , e3 , e5 , e8 , e9 , e11 }, which satisfies the sufficient pair
optimality conditions for θ = 0 (see Figure 9a). Observe that in this case it is enough to check
that X is optimal for the costs Ce∗ = Ce and Y is optimal for the costs c∗e = ce , e ∈ E. For
θ = 0, the admissible graph does not contain any augmenting path. We thus have to modify
the costs Ce∗ and c∗e , according to (23). For δ∗ = 1, a new inequality becomes tight and one
arc is added to the admissible graph (see Figure 9b). The admissible graph still does not have
an augmenting path, so we have to again modify the costs. For δ∗ = 1 some new inequalities become tight and three arcs are added to the admissible graph (see Figure 9c). Now
the admissible graph has two augmenting paths (cases 1 and 3a, see the proof of Lemma 3).
Choosing one of them, and performing the modification described in the proof of Lemma 3
we get a new pair (X ′ , Y ′ ) with |EZ ′ | = |EZ | + 1.
Let us now estimate the running time of the procedure. The admissible graph has at most
m nodes and at most mn arcs. It can be built in O(nm) time. The augmenting path in
the admissible graph can be found in O(nm) time by applying the breath first search. Also
the number of inequalities which must be analyzed to find δ∗ is O(nm). Since we have to
update the cost of each arc of the admissible graph at most m times, until an augmenting
path appears, the required time of the procedure is O(m2 n). We thus get the following result.
14

Theorem 3. The Rec ST problem is solvable in O(Lm2 n) time, where L = n − 1 − k.

3

The recoverable robust spanning tree problem

In this section we are concerned with the Rob Rec ST problem under the interval uncertainty representation, i.e. for the scenario sets U I , U1I (Γ), and U2I (Γ). Using the polynomial
algorithm for Rec ST, constructed in Section 2, we will provide a polynomial algorithm for
Rob Rec ST under U I and some approximation algorithms for a wide class of Rob Rec
ST under U1I (Γ) and U2I (Γ). The idea will be to solve Rec ST for a suitably chosen second
stage costs. Let
X
F (X) =
Ce + max min f (Y, S),
e∈X

S∈U Y ∈Φk
X

e∈X

Y ∈ΦkX

P
where f (Y, S) = e∈Y cSe . It is worth pointing out that under scenario sets U I and U2I (Γ),
the value of F (X), for a given spanning tree X, can be computed in polynomial time [8, 17].
On the other hand, computing F (X) under U1I (Γ) turns out to be strongly NP-hard [17, 9].
Given scenario S = (cSe )e∈E , consider the following Rec ST problem:
!
X
Ce + min f (Y, S) .
(27)
min
X∈Φ

Problem (27) is equivalent to the formulation (1) for S = (ce )e∈E and it is polynomially
solvable, according to the result obtained in Section 2. As in the previous section, we denote
by pair (X, Y ) a solution to (27), where X ∈ Φ and Y ∈ ΦkX . Given S, we call (X, Y ) an
optimal pair under S if (X, Y ) is an optimal solution to (27).
The Rob Rec ST problem with scenario set U I can be rewritten as follows:
!
!
X
X
X
X
Ce + min
cSe = min
(ce + de ) .
(28)
min
Ce + max min
X∈Φ

e∈X

S∈U I Y ∈ΦkX

e∈Y

X∈Φ

e∈X

Y ∈ΦkX

e∈E

Thus (28) is (27) for S = (ce + de )e∈E ∈ U I . Hence and from Theorem 3 we immediately get
the following theorem:
Theorem 4. For scenario set U I , the Rob Rec ST problem is solvable in O((n − 1− k)m2 n)
time.
We now address Rob Rec ST under U1I (Γ) and U2I (Γ). Suppose that ce ≥ α(ce + de )
for each e ∈ E, where α ∈ (0, 1] is a given constant. This inequality means that for each
edge e ∈ E the nominal cost ce is positive and ce + de is at most 1/α greater than ce . It is
reasonable to assume that this condition will be true in many practical applications for not
very large value of 1/α.
Lemma 6. Suppose that ce ≥ α(ce + de ) for each e ∈ E, where α ∈ (0, 1], and let (X̂, Ŷ ) be
an optimal pair under S = (ce )e∈E . Then for the scenario sets U1I (Γ) and U2I (Γ) the inequality
F (X̂) ≤ α1 F (X) holds for any X ∈ Φ.
Proof. We give the proof only for the scenario set U1I (Γ). The proof for U2I (Γ) is the same.
Let X ∈ Φ. The following inequality is satisfied:
X
X
X
F (X) =
Ce + max min f (Y, S) =
Ce + f (Y ∗ , S ∗ ) ≥
Ce + f (Y ∗ , S).
e∈X

S∈U1I (Γ) Y ∈ΦkX

e∈X

15

e∈X

Clearly, (X, Y ∗ ) is a feasible pair to (27) under S. From the definition of (X̂, Ŷ ) we get
X
X
X
X
X
X
F (X) ≥
Ce + f (Ŷ , S) =
Ce +
ce ≥
Ce +
α(ce + de ) =
Ce + αf (Ŷ , S),
e∈X̂

e∈X̂

e∈Ŷ

e∈X̂

e∈Ŷ

e∈X̂

(29)

where S = (ce + de )e∈E . Hence
X
X
F (X) ≥
Ce + α max f (Ŷ , S) ≥
Ce + α max
S∈U1I (Γ)

e∈X̂



≥ α

X

Ce + max

e∈X̂

e∈X̂



X̂

min f (Y, S) = αF (X̂)

S∈U1I (Γ) Y ∈Φk

X̂

and the lemma follows.

min f (Y, S)

S∈U1I (Γ) Y ∈Φk

The condition ce ≥ α(ce + de ), e ∈ E, in Lemma 6, can be weakened and, in consequence,
the set of instances to which the approximation ratio of the algorithm applies can be extended.
Indeed, from inequality (29) it follows
that the
P
P bounds of the uncertainty intervals are only
required to meet the condition e∈Ŷ ce ≥ α e∈Ŷ (ce + de ). This condition can be verified
efficiently, since Ŷ can be computed in polynomial time. P
We now focus on Rob Rec ST for U2I (Γ). Define D = e∈E de and suppose that D > 0
(if D = 0, then the problem is equivalent to Rec ST for the second stage costs ce , e ∈ E).
′
Consider scenario S ′ under which cSe = min{ce + de , ce + Γ dDe } for each e ∈ E. Obviously,
P
P
de
S ′ ∈ U2I (Γ), since
e∈E δe ≤
e∈E Γ D ≤ Γ. The following theorem provides another
approximation result for Rob Rec ST with scenario set U2I (Γ):

Lemma 7. Let (X̂, Ŷ ) be an optimal pair under S ′ . Then the following implications are true
for scenario set U2I (Γ):
(i) If Γ ≥ βD, β ∈ (0, 1], then F (X̂) ≤ β1 F (X) for any X ∈ Φ.
(ii) If Γ ≤ γF (X̂), γ ∈ [0, 1) then F (X̂) ≤

1
1−γ F (X)

for any X ∈ Φ.

Proof. Let X ∈ Φ. Since S ′ ∈ U2I (Γ), we get
X
X
Ce + min f (Y, S ′ ).
F (X) =
Ce + max min f (Y, S) ≥
e∈X

S∈U2I (Γ) Y ∈ΦkX

e∈X

Y ∈ΦkX

(30)

We first prove implication (i). By (30) and the definition of (X̂, Ŷ ), we obtain
X
X
X
de
F (X) ≥
Ce + f (Ŷ , S ′ ) =
Ce +
min{ce + de , ce + Γ }
D
e∈X̂
e∈Ŷ
e∈X̂
X
X
X
X
X
≥
Ce +
min{ce + de , ce + βde } =
Ce +
(ce + βde ) ≥
Ce + βf (Ŷ , S),
e∈X̂

e∈Ŷ

e∈X̂

e∈Ŷ

e∈X̂

where S = (ce + de )e∈E . The rest of the proof is the same as in the proof of Lemma 6. We
now prove implication (ii). By (30) and the definition of (X̂, Ŷ ), we have
X
X
X
F (X) ≥
Ce + f (Ŷ , S ′ ) ≥
Ce + f (Ŷ , S) ≥
Ce + max f (Ŷ , S) − Γ
e∈X̂

≥

X

e∈X̂

e∈X̂

Ce + max

e∈X̂

min f (Y, S) − Γ = F (X̂) − Γ.

S∈U2I (Γ) Y ∈Φk

X̂

16

S∈U2I (Γ)

If Γ ≤ γF (X̂). Then F (X) ≥ F (X̂) − γF (X̂) = (1 − γ)F (X̂) and F (X̂) ≤

1
1−γ F (X).

Note that the value of F (X̂) under U2I (Γ) can be computed in polynomial time [17]. In
consequence, the constants β and γ can be efficiently determined for every particular instance
of the problem. Clearly, we can assume that de ≤ Γ for each e ∈ E, which implies D ≤ mΓ,
1
D for every instance of the problem.
where m = |E|. Hence, we can assume that Γ ≥ m
We thus get from Lemma 7 (implication (i)) that F (X̂) ≤ mF (X) for any X ∈ Φ and the
problem is approximable within m. If α, β and γ are the constants from Lemmas 6 and 7,
then the following theorem summarizes the approximation results:
Theorem 5. Rob Rec ST is approximable within α1 under scenario set U1I (Γ) and it is
1
} under scenario set U2I (Γ).
approximable within min{ β1 , α1 , 1−γ
Observe that Lemma 6 and Lemma 7 hold of any sets Φ and ΦkX (the particular structure
of these sets is not exploited). Hence the approximation algorithms can be applied to any
problem for which the recoverable version (27) is polynomially solvable.

4

Conclusions

In this paper we have studied the recoverable robust spanning tree problem (Rob Rec ST)
under various interval uncertainty representations. The main result is the polynomial time
combinatorial algorithm for the recoverable spanning tree. We have applied this algorithm
for solving Rob Rec ST under the traditional uncertainty representation (see, e.g., [13]) in
polynomial time. Moreover, we have used the algorithm for providing several approximation
results for Rec ST with the scenario set introduced by Bertsimas and Sim [3] and the scenario
set with a budged constraint (see, e.g,. [17]). There is a number of open questions concerning
the considered problem. Perhaps, the most interesting one is to resolve the complexity of
the robust problem under the interval uncertainty representation with budget constraint. It
is possible that this problem may be solved in polynomial time by some extension of the
algorithm constructed in this paper. One can also try to extend the algorithm for the more
general recoverable matroid base problem, which has also been shown to be polynomially
solvable in [10].
Acknowledgements
The second and the third authors were supported by the National Center for Science (Narodowe Centrum Nauki), grant 2013/09/B/ST6/01525.

References
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: theory, algorithms, and
applications. Prentice Hall, Englewood Cliffs, New Jersey, 1993.
[2] H. Aissi, C. Bazgan, and D. Vanderpooten. Approximation of min-max and min-max
regret versions of some combinatorial optimization problems. European Journal of Operational Research, 179:281–290, 2007.

17

[3] D. Bertsimas and M. Sim. Robust discrete optimization and network flows. Mathematical
Programming, 98:49–71, 2003.
[4] C. Büsing. Recoverable robustness in combinatorial optimization. PhD thesis, Technical
University of Berlin, Berlin, 2011.
[5] C. Büsing. Recoverable robust shortest path problems. Networks, 59:181–189, 2012.
[6] C. Büsing, A. M. C. A. Koster, and M. Kutschka. Recoverable robust knapsacks: the
discrete scenario case. Optimization Letters, 5:379–392, 2011.
[7] A. Chassein and M. Goerigk. On the recoverable robust traveling salesman problem.
Optimization Letters, DOI 10.1007/s11590-015-0949-5, 2015.
[8] O. Şeref, R. K. Ahuja, and J. B. Orlin. Incremental network optimization: theory and
algorithms. Operations Research, 57:586–594, 2009.
[9] N. G. Frederickson and R. Solis-Oba. Increasing the weight of minimum spanning trees.
Journal of Algorithms, 33:244–266, 1999.
[10] M. Hradovich, A. Kasperski, and P. Zieliński. The recoverable robust spanning
tree problem with interval costs is polynomially solvable. Optimization Letters, DOI
10.1007/s11590-016-1057-x, 2016.
[11] A. Kasperski, A. Kurpisz, and P. Zieliński. Recoverable robust combinatorial optimization problems. In Operations Research Proceedings 2012, pages 147–153, 2014.
[12] A. Kasperski and P. Zieliński. On the approximability of robust spanning problems.
Theoretical Computer Science, 412:365–374, 2011.
[13] P. Kouvelis and G. Yu. Robust Discrete Optimization and its Applications. Kluwer
Academic Publishers, 1997.
[14] L. C. Lau, R. Ravi, and M. Singh. Iterative Methods in Combinatorial Optimization.
Cambridge University Press, 2011.
[15] C. Liebchen, M. E. Lübbecke, R. H. Möhring, and S. Stiller. The concept of recoverable
robustness, linear programming recovery, and railway applications. In Robust and Online
Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 1–
27. Springer-Verlag, 2009.
[16] K. Lin and M. S. Chern. The most vital edges in the minimum spanning tree problem.
Information Processing Letters, 45:25–31, 1993.
[17] E. Nasrabadi and J. B. Orlin. Robust optimization with incremental recourse. CoRR,
abs/1312.4075, 2013.
[18] C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Dover Publications Inc., 1998.

18

