# Recoverable robust shortest path problem under interval uncertainty
representations

Marcel Jackiewicz  Wrocław University of Science and Technology, Wrocław,
Poland
<EMAIL_ADDRESS>Adam
Kasperski111Corresponding author Wrocław University of Science and Technology,
Wrocław, Poland
<EMAIL_ADDRESS>Paweł Zieliński
Wrocław University of Science and Technology, Wrocław, Poland
<EMAIL_ADDRESS>
###### Abstract

In this paper, the recoverable robust shortest path problem under interval
uncertainty representations is discussed. This problem is known to be strongly
NP-hard and also hard to approximate in general digraphs. In this paper, the
class of acyclic digraphs is considered. It is shown that for the traditional
interval uncertainty, the problem can be solved in polynomial time for all
natural, known from the literature, neighborhoods. Efficient algorithms for
various classes of acyclic digraphs are constructed. Some negative results for
general digraphs are strengthened. Finally, some exact and approximate methods
of solving the problem under budgeted interval uncertainty are proposed.

Keywords: robust optimization, interval data, recovery, shortest path.

##  1 Introduction

The concept of recoverable robustness was introduced by Liebchen et al. [29].
This two-stage approach consists in computing a first-stage solution whose
cost is known. In the second stage, after the uncertain costs are revealed, a
limited recovery action is allowed to modify the first-stage solution. We seek
a solution whose total first and second-stage cost is minimal. The recoverable
robust approach can be naturally applied to the class of combinatorial
optimization problems, where each solution can be represented as a subset of a
finite element set. In this case, the recovery action consists in adding some
elements to the first-stage solution or excluding some elements from it (see,
e.g., [12, 30, 23]). The second-stage uncertainty can be modeled in various
ways. We can use the _discrete uncertainty representation_ (see, e.g., [25])
by simply listing all possible realizations of the second-stage costs.
Alternatively, we can use the _interval uncertainty representation_ by
providing an interval of possible second-stage costs for each uncertain
parameter. To control the amount of uncertainty and the price of robustness,
budgeted versions of the interval uncertainty can be used [2, 3, 30].

The recoverable robust approach has recently been applied to various
combinatorial optimization problems. Under the interval uncertainty
representation, the problem can be solved in polynomial time for the class of
matroidal problems [28], for example, the selection [24, 26] and the minimum
spanning tree [21, 20] problems. On the other hand, the problem is strongly
NP-hard for the shortest path in general digraphs [7] and the assignment [13]
problems. Furthermore, the former problem is also hard to approximate even if
a very limited recovery action is allowed [7], while the latter one is
$W[1]$-hard with respect to the recovery parameter [13]. In [10, 17], the
recoverable robust version of the strongly NP-hard traveling salesperson
problem under interval uncertainty has been investigated. Several
approximation algorithms for some special cases of this problem were proposed.
In [4], the recoverable robust version of a single-machine scheduling problem
with interval job processing times was discussed. Some approximation
algorithms for this problem were proposed.

Adding budgets to the interval uncertainty makes solving the recoverable
robust problem challenging. Polynomial time algorithms are known only for some
very special cases, such as the selection problem under the _continuous
budgeted uncertainty_ [30], constructed in [11]. The complexity of the
analogous problem for the minimum spanning tree remains open. For the discrete
budgeted uncertainty [3], a compact mixed integer programming model for the
recoverable robust selection can be constructed [11]. For the analogous
recoverable robust version of the minimum spanning tree problem, computing a
worst scenario for a given first-stage solution (the adversarial problem) is
already strongly NP-hard [30]. In [8, 9], the recoverable robust knapsack
problem with the budgeted uncertainty in the item weights was investigated. A
compact mixed integer programming formulation for this problem was
constructed. Generally, the recoverable robust combinatorial problems under
budgeted interval uncertainty can be solved using a row generation algorithm
described in [22, 33]. However, this algorithm is efficient only for problems
of small size. Designing more efficient methods for particular problems is
still very challenging.

In this paper, we focus on the recoverable robust version of the shortest path
problem. This problem was first investigated in [6, 7], and a closely related
problem, called the incremental one, was also previously discussed in [12]. In
the traditional shortest path problem, we are given a directed graph $G$ with
arc costs, and we seek a simple shortest path between two specified nodes in
$G$. This well-known network problem can be solved in polynomial time in
general digraphs, assuming that the arc costs are nonnegative, and in acyclic
digraphs for arbitrary costs (see, e.g., [1]). Unfortunately, the complexity
of its recoverable robust version can be much worse. In this version, the
paths resulting from a recovery action form the so-called neighborhood of a
given first-stage path. It turns out that even computing an optimal recovery
action for a given second-stage scenario is strongly NP-hard for some natural
neighborhoods [12, 30]. Furthermore, computing the optimal first and second-
stage paths is strongly NP-hard for all natural neighborhoods [7, 30]. This
is, however, the case in general digraphs. Until now, the complexity of the
problem for acyclic digraphs has been open. In this paper, we close this gap
and show that the recoverable robust shortest path problem in acyclic
multidigraphs, under interval uncertainty, can be solved in polynomial time.
This fact remains valid for all neighborhoods discussed in the literature. We
construct polynomial time algorithms for general acyclic digraphs and faster
algorithms exploiting particular structures of the input graphs (layered and
arc series-parallel digraphs). We also strengthen the negative complexity
results for general digraphs. Namely, we show that the recoverable robust
shortest path problem is strongly NP-hard and hard to approximate for digraphs
that are near to acyclic planar ones. In the second part of the paper, we
discuss the robust version of the problem with budgeted interval uncertainty.
We show that the problem with the continuous budgeted uncertainty can be
solved by using a compact mixed integer programming formulation. Furthermore,
the polynomial time algorithms for acyclic digraphs and the interval
uncertainty allow us to construct efficient approximation algorithms for both
continuous and discrete budgeted uncertainty.

This paper is organized as follows. In Section 2, we recall the formulation of
the recoverable robust shortest path problem with various neighborhoods and
several interval uncertainty representations. We also recall the definitions
of the inner adversarial and incremental problems. In Section 3, we discuss
the case of the traditional interval uncertainty without a budget. We
strengthen the known complexity results for general digraphs and show that the
problem can be solved in polynomial time for acyclic multidigraphs. We present
several polynomial time algorithms for this class of graphs. In Section 4, we
discuss the recoverable robust shortest path problem with the budgeted
interval uncertainty. We construct a compact mixed integer programming
formulation for the continuous case while strengthening some known complexity
results for the discrete case. Finally, we propose several approximation
algorithms for the class of acyclic multidigraphs.

##  2 Recoverable robust shortest path problem

In the _shortest path problem_ (SP), we are given a _multidigraph_ $G=(V,A)$
that consists of a finite set of nodes $V$, $|V|=n$, and a finite multiset of
arcs $A$, $|A|=m$. Two nodes $s\in V$ and $t\in V$ are distinguished as the
_starting node_ and the _destination_ node, respectively. In particular, node
$s$ is called source if no arc enters $s$, and node $t$ is called sink if no
arc leaves $t$. Let $\Phi$ be the set of all simple $s$-$t$ paths in $G$. We
will identify each path $X\in\Phi$ with the corresponding set of arcs that
form $X$. We will also denote by $\chi(\Phi)\subset\\{0,1\\}^{|A|}$ the set of
characteristic vectors of the paths in $\Phi$. A deterministic cost is
associated with each arc of $G$, and we seek a simple $s$-$t$ path in $G$ with
the minimum total cost. The shortest path problem can be solved efficiently
using several polynomial-time algorithms (see, e.g., [1]).

In the _recoverable robust_ version of SP (Rec Rob SP for short), we are given
first-stage arc costs $C_{e}\geq 0$, $e\in A$, which are known in advance. The
second stage costs are uncertain, and they are specified as a _scenario
(uncertainty) set_ $\mathbb{U}\subset\mathbb{R}_{+}^{|A|}$. A particular
realization of the second-stage arc costs $S=(c_{e}^{S})_{e\in A}$ is called a
_scenario_. The decision process in Rec Rob SP is two-stage and consists in
choosing a path $X\in\Phi$ in the first stage. Then, in the second stage (the
recovery stage), after a scenario $S\in\mathbb{U}$ reveals, the path $X$ can
be modified to some extent. This modification consists in finding a shortest
path $Y$ under the cost scenario $S$ in a _neighborhood_ of $X$, denoted by
$\Phi(X,k)\subseteq\Phi$. This neighborhood depends on a given _recovery
parameter_ $k$, being an integer such that $k\geq 0$. In this paper, we
examine the following variants of the neighborhood $\Phi(X,k)$ (see, e.g.,
[12, 30]):

$\displaystyle\Phi^{\mathrm{incl}}(X,k)$
$\displaystyle=\\{Y\in\Phi\,:\,|Y\setminus X|\leq k\\},$ (1)
$\displaystyle\Phi^{\mathrm{excl}}(X,k)$
$\displaystyle=\\{Y\in\Phi\,:\,|X\setminus Y|\leq k\\},$ (2)
$\displaystyle\Phi^{\mathrm{sym}}(X,k)$
$\displaystyle=\\{Y\in\Phi\,:\,|(Y\setminus X)\cup(X\setminus Y)|\leq k\\}$
(3)

called the _arc inclusion neighborhood_ (at most $k$ new arcs can be added to
$X$), the _arc exclusion neighborhood_ (at most $k$ arcs can be removed from
$X$), and the _arc symmetric difference neighborhood_ (at most $k$ arcs can be
different in $X$ and $Y$), respectively.

The goal in Rec Rob SP is to find a pair of paths $X\in\Phi$ (the first-stage
path) and $Y\in\Phi(X,k)$ (the second-stage path), which minimizes the total
cost in a worst case. The problem can be formally stated as follows:

$\textsc{Rec Rob SP}:\;\min_{X\in\Phi}\left(\sum_{e\in
X}C_{e}+\max_{S\in\mathbb{U}}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}^{S}\right).$ (4)

The Rec Rob SP problem contains two inner problems. The first one is the
_adversarial problem_ , in which an _adversary_ wants to find, for a given
path $X\in\Phi$, a scenario that leads to the greatest increase in the cost of
a shortest path from $\Phi(X,k)$:

$\textsc{Adv SP}:\;\max_{S\in\mathbb{U}}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}^{S}.$ (5)

The Rec Rob SP problem reduces to Adv SP, when we set $C_{e}=0$ if $e\in X$
and $C_{e}=M$, otherwise, where $M$ is a sufficiently large number. The second
inner problem is called the _incremental problem_ , which is important from a
decision point of view in the second stage:

$\textsc{Inc SP}:\;\min_{Y\in\Phi(X,k)}\sum_{e\in Y}c_{e}^{S^{*}},$ (6)

where path $X\in\Phi$ is given, and the uncertain second stage arc costs are
realized in the form of the scenario $S^{*}$. The goal is to make some
modifications of $X$ that consist in finding a cheapest path $Y\in\Phi(X,k)$
under the cost scenario $S^{*}$ in order to accommodate $X$ to the cost
realization $S^{*}$. The Rec Rob SP problem reduces to Inc SP if
$\mathbb{U}=\\{S^{*}\\}$, $C_{e}=0$ if $e\in X$ and $C_{e}=M$, otherwise.

In this paper, we use the _interval uncertainty_ representation to model the
uncertain second-stage arc costs. Namely, scenario set $\mathbb{U}$ has the
following form:

$\mathcal{U}=\\{S=(c_{e}^{S})_{e\in
A}\,:\,c_{e}^{S}\in[\hat{c}_{e},\hat{c}_{e}+\Delta_{e}],e\in A\\},$ (7)

where $\hat{c}_{e}$ is the _nominal cost_ of $e\in A$ and $\Delta_{e}\geq 0$
is the maximum deviation of the cost of $e$ from its nominal value. To control
the amount of uncertainty in the set $\mathcal{U}$, one can consider the
following two budgeted variants of $\mathcal{U}$ that are commonly used in
robust optimization:

$\displaystyle\mathcal{U}(\Gamma^{d})$ $\displaystyle=\\{S=(c_{e}^{S})_{e\in
A}\in\mathcal{U}\,:\,|e\in A\,:\,c_{e}^{S}>\hat{c}_{e}|\leq\Gamma^{d}\\},$ (8)
$\displaystyle\mathcal{U}(\Gamma^{c})$ $\displaystyle=\\{S=(c_{e}^{S})_{e\in
A}\in\mathcal{U}\,:\,\sum_{e\in A}(c_{e}^{S}-\hat{c}_{e})\leq\Gamma^{c}\\}.$
(9)

The set $\mathcal{U}(\Gamma^{d})$ is called _discrete budgeted uncertainty_
[2, 3] and the set $\mathcal{U}(\Gamma^{c})$ is called _continuous budgeted
uncertainty_ [30]. The parameters $\Gamma^{d}\in\\{0,\ldots,|A|\\}$ and
$\Gamma^{c}\in\mathbb{R}_{+}$ are called _budgets_. The parameter $\Gamma^{d}$
limits the number of second-stage costs that can deviate from their nominal
values. On the other hand, the parameter $\Gamma^{c}$ limits the total
deviation of the second-stage costs from their nominal values. In the
following we will use
$\mathbb{U}\in\\{\mathcal{U},\mathcal{U}(\Gamma^{d}),\mathcal{U}(\Gamma^{c})\\}$
in (4)–(6).

If $k=0$, the first and the second stage paths must be identical. The Rec Rob
SP problem is then equivalent to the min-max shortest path problem (MinMax SP)
in which we seek a path minimizing the largest cost in scenario sets
$\mathcal{U}^{\prime}$, $\mathcal{U}^{\prime}(\Gamma^{c})$,
$\mathcal{U}^{\prime}(\Gamma^{d})$, in which
$\hat{c}_{e}^{\prime}=C_{e}+\hat{c}_{e}$ and $\Delta_{e}^{\prime}=\Delta_{e}$
for each $e\in A$. The MinMax SP problem can be solved in polynomial time by
solving a family of the deterministic shortest paths problems (see, e.g., [2,
27]). From now on, we will assume that $k\geq 1$.

##  3 The Rec Rob SP problem under the interval uncertainty

In this section, we consider the Rec Rob SP problem under the interval
uncertainty $\mathcal{U}$. We begin by observing that, in this case, the
adversarial problem (5) can be simplified. Indeed, it is easily seen that

$\max_{S\in\mathcal{U}}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}^{S}=\min_{Y\in\Phi(X,k)}\sum_{e\in Y}(\hat{c}_{e}+\Delta_{e}).$

Thus, Adv SP becomes the Inc SP problem under the upper bound scenario
$(\hat{c}_{e}+\Delta_{e})_{e\in A}$. Hence, the Rec Rob SP under $\mathcal{U}$
also simplifies and is equivalent to the following problem:

$\textsc{Rec SP}:\;\min_{X\in\Phi}\left(\sum_{e\in
X}C_{e}+\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}\overline{c}_{e}\right)=\min_{X\in\Phi,Y\in\Phi(X,k)}\left(\sum_{e\in
X}C_{e}+\sum_{e\in Y}\overline{c}_{e}\right),$ (10)

called the _recoverable shortest path problem_ , where $\overline{c}_{e}$
stands for $\hat{c}_{e}+\Delta_{e}$ for each $e\in E$. Thus, throughout this
section, we will study the Rec SP problem instead of the Rec Rob SP under
$\mathcal{U}$ and the Inc SP problem instead of Adv SP.

Table 1 summarizes the results obtained in this section. We will first
strengthen the known negative results for general digraphs. We then construct
polynomial time algorithms for various classes of acyclic multidigraphs.

Table 1: Summary of the results for Rec SP under the interval uncertainty $\mathcal{U}$ for various classes of multidigraphs and neighborhoods. | Neighborhoods
---|---
Multidigraph | $\Phi^{\mathrm{incl}}(X,k)$ | $\Phi^{\mathrm{excl}}(X,k)$ | $\Phi^{\mathrm{sym}}(X,k)$
General | strongly NP-hard | strongly NP-hard | strongly NP-hard
| not approximable | not approximable | not approximable
|  for $k=2$ [7] |  for $k=2$ [12] |  for unbounded $k$ [30]
| para-NP-complete | para-NP-complete |
| compact MIP | compact MIP | compact MIP
Nearly acyclic | strongly NP-hard | strongly NP-hard |
planar∗ | not approximable | not approximable. |
|  for unbounded $k$ |  for unbounded $k$ | ?
General acyclic | $O(|V|^{2}|A|k^{2})$ | $O(|V|^{2}|A|k^{2})$ | $O(|V|^{2}|A|k^{3})$
Layered | $O(|A||V|+|V|^{2}k)$ | $O(|A||V|+|V|^{2}k)$ | $O(|A||V|+|V|^{2}k)$
Arc series-parallel | $O(|A|k^{2})$ | $O(|A|k^{2})$ | $O(|A|k^{2})$
∗Multidigraph that becomes acyclic planar after removing $O(k)$ arcs.

###  3.1 Recoverable shortest path problem in general multidigraphs

We now analyze the computational complexity of the Inc SP and Rec SP problems
with the neighborhoods $\Phi^{\mathrm{incl}}(X,k)$,
$\Phi^{\mathrm{excl}}(X,k)$ and $\Phi^{\mathrm{sym}}(X,k)$. We refine the
known results in this area by providing hardness results for digraphs with a
simpler structure.

Consider first the neighborhood $\Phi^{\mathrm{incl}}(X,k)$. In this case, the
Inc SP problem in a general digraph $G=(V,A)$ can be solved in $O(k|A|)$ time
[12], while in [7, Corollary 4], Büsing proved that the Rec SP problem is
strongly NP-hard and not approximable in a general digraph unless P=NP, even
if the recovery parameter $k=2$. The proof shown in [7] uses a reduction from
the 2-vertex disjoint paths problem, which is strongly NP-complete in general
digraphs [15]. We now generalize this reduction and show that Rec SP remains
hard for a simple structure of digraphs, i.e., for the digraphs near acyclic
planar ones.

We start by recalling the definition of the $K$-_Vertex-Disjoint Paths
Problem_ ($K$-V-DP for short). We are given a digraph $G=(V,A)$ and $K$
terminal pairs $(s_{i},t_{i})$, where $s_{i},t_{i}\in V$, $i\in[K]$, are
pairwise distinct vertices. We ask whether there exist $K$ pairwise vertex-
disjoint paths $\pi_{1},\ldots,\pi_{K}$ in $G$ such that $\pi_{i}$ is a simple
$s_{i}$-$t_{i}$ path for each $i\in[K]=\\{1,\dots,K\\}$.

Figure 1: A graph $G+H$ used in the reductions in the proofs of Lemmas 1, 2,
and 7. The bold arcs form the graph $H$.

Let $G=(V,A)$ and $H=(V_{H},A_{H})$ be two digraphs such that $V_{H}\subseteq
V$. We will denote by $G+H$ the multidigraph having the set of nodes $V$ and
the set of arcs containing all the arcs from $A$ and $A_{H}$.

######  Lemma 1.

There is a polynomial time reduction from $K$-V-DP in a digraph $G$ to Rec SP
with $\Phi^{\mathrm{incl}}(X,k)$, $k=K$, in a digraph $G+H$ with costs
$(C_{e},\overline{c}_{e})\in\\{(0,0),(1,0),(0,1)\\}$ for all arcs $e$ in
$G+H$, where digraph $H$ is a simple path containing $2k-1$ arcs,
$|A_{H}|=2k-1$. Moreover, an instance of $K$-V-DP is positive iff the total
cost of any optimal solution to the corresponding instance of Rec SP is zero.

###### Proof.

The reduction presented here is a generalization, with some simplifications,
of the one given in [7, Corollary 4] to the case of $K$ terminal pairs. Given
an instance of the $K$-V-DP problem in a digraph $G=(V,A)$, we built the
corresponding instance of Rec SP as follows. We add $2K-1$ arcs to graph $G$,
i.e. the arcs $(s_{i},t_{i})$ with the costs $C_{s_{i}t_{i}}=1$,
$\overline{c}_{s_{i}t_{i}}=0$, $i\in[K]$, and the arcs $(t_{i},s_{i+1})$ with
the costs $C_{t_{i}s_{i+1}}=0$, $\overline{c}_{t_{i}s_{i+1}}=0$, $i\in[K-1]$.
These arcs form the simple $s$-$t$ path $H$, where $s=s_{1}$ and $t=t_{K}$
(see Figure 1). The rest of the arcs of graph $G+H$, i.e. the arcs of the
original graph $G$, have the costs $C_{e}=0$ and $\overline{c}_{e}=1$, $e\in
A$. Finally, we set $k=K$. We show that the answer to $K$-V-DP is positive iff
the total cost of any optimal solution to the corresponding instance of Rec SP
is zero.

($\Rightarrow$) Assume that the answer to an instance of $K$-V-DP is yes.
Thus, there exist $K$ pairwise vertex-disjoint paths $\pi_{1},\ldots,\pi_{K}$
in $G$ such that $\pi_{i}$ is a simple $s_{i}$-$t_{i}$ path for each
$i\in[K]$. Hence, the pair of simple $s$-$t$ paths
$X^{*}=(\pi_{1},(t_{1},s_{2}),\pi_{2},(t_{2},s_{2}),\ldots,\pi_{K})$ and
$H=((s_{1},t_{1}),(t_{1},s_{2}),(s_{2},t_{2}),\dots,(s_{K},t_{K}))\in\Phi^{\mathrm{incl}}(X^{*},k)$
is an optimal solution to the corresponding instance of Rec SP with the total
cost of zero.

($\Leftarrow$) Let $X^{*}$ and $Y^{*}\in\Phi^{\mathrm{incl}}(X,k)$ be an
optimal pair of the first and second stage simple $s$-$t$ paths in $G+H$.
Because the second stage cost of $Y^{*}$ is 0, $Y^{*}=H$. On the other hand,
the arcs $(s_{i},t_{i})$ for $i\in[K]$ cannot appear in $X^{*}$ because their
first stage costs are positive. In what follows, all the arcs
$(t_{i},s_{i+1})$, $i\in[K-1]$, must be present in $X^{*}$, since otherwise we
had to add more than $k$ arcs to $X^{*}$ to obtain $Y^{*}$. Since $X^{*}$ is a
simple $s$-$t$ path in $G$, it connects nodes $s_{i}$ and $t_{i}$, $i\in[K]$,
by arcs that only belong to $G$. Hence, there must exist $K$ node disjoint
simple paths $\pi_{i}$ between $s_{i}$ and $t_{i}$, $i\in[K]$, respectively,
in $G$. ∎

From Lemma 1 and the complexity of $K$-V-DP for $K=2$ in general digraphs
[15], we immediately obtain the aforementioned Büsing’s hardness results for
Rec SP when $k=2$. In this case, $H$ is a simple $3$-arc path (only three arcs
are added to $G$). It turns out that if $K$ is a part of the input, then
$K$-V-DP remains strongly NP-hard for acyclic planar digraphs [31]. Lemma 1
implies then the following result:

######  Theorem 1.

The Rec SP problem with $\Phi^{\mathrm{incl}}(X,k)$ in a digraph $G+H$ with
costs $(C_{e},\overline{c}_{e})\in\\{(0,0),(1,0),(0,1)\\}$ for all arcs $e$ in
$G+H$ is strongly NP-hard and not approximable unless P=NP, if $G$ is a planar
digraph, $k$ is a part of the input, and $H$ is a simple path having $2k-1$
arcs.

The inapproximability result follows from the fact that any approximation
algorithm for Rec SP would detect in polynomial time a solution with the cost
equal to 0. We will show in Section 3.2 that Rec SP is polynomially solvable
in acyclic digraphs. Theorem 1 shows that it is enough to add $2k-1$ arcs to
an acyclic planar digraph to make Rec SP computationally hard problem.

Let us look at the Rec SP problem from the parameterized complexity point of
view (see, e.g., [14] for an in-depth treatment of the parameterized
complexity), i.e. when Rec SP is parameterized by the recovery parameter $k$.

######  Theorem 2.

The decision version of Rec SP with $\Phi^{\mathrm{incl}}(X,k)$ parameterized
by $k$ is para-NP-complete in general digraphs.

###### Proof.

The problem Rec SP is in NP, because Inc SP (Adv SP) with
$\Phi^{\mathrm{incl}}(X,k)$ can be solved in $O(k|A|)$ time [12]. Hence, Rec
SP belongs to para-NP. Since Rec SP is NP-hard for constant $k$ ($k=2$) [7],
it is para-NP-hard (see [14, Theorem 2.14]). Thus, it is para-NP-complete in
general digraphs. ∎

######  Corollary 1.

The problem Rec SP with $\Phi^{\mathrm{incl}}(X,k)$ parameterized by $k$ is
para-NP-hard in general digraphs.

We now consider the arc exclusion neighborhood $\Phi^{\mathrm{excl}}(X,k)$.
For this case, the Inc SP problem is already strongly NP-hard and not
approximable in general digraphs, even if the recovery parameter $k=2$ by the
reduction from the $2$-V-DP problem [12]. Again, we generalize this reduction
to show that Inc SP remains hard for digraphs near acyclic planar ones.

######  Lemma 2.

There is a polynomial time reduction from $K$-V-DP in a digraph $G=(V,A)$ to
Inc SP with $\Phi^{\mathrm{excl}}(X,k)$, $k=K$, in a digraph $G+H$ with
$\overline{c}_{e}\in\\{0,1\\}$ for all arcs $e$ in $G+H$, where $H$ is a
simple path having $2k-1$ arcs, $|A_{H}|=2k-1$. Moreover, an instance of
$K$-V-DP is positive iff the total cost of any optimal solution to the
corresponding instance of INC SP is zero.

###### Proof.

Given an instance of the $K$-V-DP problem in a digraph $G=(V,A)$, we add
$2K-1$ arcs to graph $G$, i.e. arcs $(s_{i},t_{i})$ with the costs
$\overline{c}_{s_{i}t_{i}}=1$, $i\in[K]$, and arcs $(t_{i},s_{i+1})$ with the
costs $\overline{c}_{t_{i}s_{i+1}}=0$, $i\in[K-1]$. These new arcs form the
simple $s$-$t$ path $H$, where $s=s_{1}$ and $t=t_{K}$ (see Figure 1). The
rest of the arcs of the graph $G+H$, i.e. the arcs of the original $G$, have
the costs $\overline{c}_{e}=0$, $e\in A$. Let $X=H$ and fix $k=K$. The cost of
an optimal solution $Y^{*}$ to Inc SP is 0 iff all the $K$ arcs
$(s_{i},t_{i})$, $i\in[K]$, are removed from $X$ and all the arcs
$(t_{i},s_{i+1})$ for $i\in[K-1]$ are present in $Y^{*}$ (as at most $K$ arcs
can be removed from $X$). Because $Y^{*}$ is a simple path, there are $K$
vertex disjoint paths $\pi_{1},\dots,\pi_{K}$ between $s_{i}$ and $t_{i}$,
$i\in[K]$, in $G$. ∎

Lemma 2 and the strong NP-completeness of $K$-V-DP for $K=2$ in general
digraphs [15] lead to the hardness result for Inc SP with
$\Phi^{\mathrm{excl}}(X,k)$ when $k=2$ presented in [12]. By Lemma 2 and the
fact that $K$-V-DP is strongly NP-complete in an acyclic planar digraph, when
$K$ is a part of the input [31], we obtain the following hardness result for
simpler digraphs:

######  Theorem 3.

The Inc SP problem with $\Phi^{\mathrm{excl}}(X,k)$ in a digraph $G+H$ with
costs $\overline{c}_{e}\in\\{0,1\\}$ for all arcs $e$ in $G+H$ is strongly NP-
hard and not approximable unless P=NP, if $G$ is a planar digraph, $k$ is a
part of the input and $H$ is a simple path having $2k-1$ arcs.

We have the results analogous to Theorem 2 and Corollary 1 for the arc
exclusion neighborhood.

######  Theorem 4.

The decision version of Inc SP with $\Phi^{\mathrm{excl}}(X,k)$ parameterized
by $k$ is para-NP-complete in general digraphs.

###### Proof.

Clearly Inc SP is in NP, and so it is in para-NP. Since Inc SP is NP-hard for
$k=2$ [12], it is para-NP-hard (see [14, Theorem 2.14]). Thus, it is para-NP-
complete in general digraphs. ∎

######  Corollary 2.

The Inc SP problem with $\Phi^{\mathrm{excl}}(X,k)$ parameterized by $k$ is
para-NP-hard in general digraphs.

Finally, consider the arc symmetric difference neighborhood
$\Phi^{\mathrm{sym}}(X,k)$. It was shown in [30] that Inc SP is then strongly
NP-hard even if the recovery parameter $k$ is a part of the input. A simple
and straightforward modification of the reduction from [30] (it is enough to
change some arc costs) allows us to establish also the inapproximability of
Inc SP for this case.

######  Theorem 5.

The Inc SP problem in general digraphs with $\Phi^{\mathrm{sym}}(X,k)$ is
strongly NP-hard and not approximable unless P=NP if $k$ is a part of the
input.

Since Inc SP is a special case of Rec SP, all the hardness results for
$\Phi^{\mathrm{excl}}(X,k)$ and $\Phi^{\mathrm{sym}}(X,k)$ remain valid for
Rec SP with these neighborhoods. Hence, Rec SP is a computationally hard
problem for all neighborhoods under consideration. Notice, however, that the
above negative results hold for general digraphs. In Section 3.2, we will show
that Rec SP can be solved in polynomial time for all the considered
neighborhoods if the input graph is an acyclic multidigraph.

At the end of this section, we will show that Rec SP in general digraphs can
be solved using a compact mixed integer programming formulation (MIP for
short). Let us first express Rec SP as follows:

$\displaystyle\min\;$ $\displaystyle\sum_{e\in A}C_{e}x_{e}+\sum_{e\in
A}\overline{c}_{e}y_{e}$ (11)
$\displaystyle\boldsymbol{y}\in\chi(\Phi(X,k))\subset\\{0,1\\}^{|A|},$ (12)
$\displaystyle\boldsymbol{x}\in\chi(\Phi)\subset\\{0,1\\}^{|A|},$ (13)

where $\chi(\Phi(X,k))$ is the set of characteristic vectors of the $s$-$t$
paths from the neighborhood $\Phi(X,k)$. For the considered neighborhoods,
this set can be modeled by the following constraints:

$\displaystyle\Phi^{\mathrm{incl}}(X,k):$
$\displaystyle\boldsymbol{y}\in\chi(\Phi),\;\sum_{e\in A}(1-x_{e})y_{e}\leq
k,$ (14) $\displaystyle\Phi^{\mathrm{excl}}(X,k):$
$\displaystyle\boldsymbol{y}\in\chi(\Phi),\;\sum_{e\in A}(1-y_{e})x_{e}\leq
k,$ (15) $\displaystyle\Phi^{\mathrm{sym}}(X,k):$
$\displaystyle\boldsymbol{y}\in\chi(\Phi),\;\sum_{e\in
A}((1-x_{e})y_{e}+(1-y_{e})x_{e})\leq k.$ (16)

The model (11)-(13) can be easily linearized for all the neighborhoods. For
example, (14) can be modeled as follows: $\boldsymbol{y}\in\chi(\Phi)$ is
replaced by the mass balance flow linear constraints (see, e.g., [1]), the
same concerns (13). The term $\sum_{e\in A}(1-x_{e})y_{e}\leq k$ can be
expressed by the following constraints:

$\displaystyle\sum_{e\in A}(y_{e}-z_{e})\leq k,$ (17) $\displaystyle z_{e}\leq
x_{e}$ $\displaystyle\forall e\in A,$ (18) $\displaystyle z_{e}\leq y_{e}$
$\displaystyle\forall e\in A,$ (19) $\displaystyle z_{e}\geq 0$
$\displaystyle\forall e\in A,$ (20)

where (18)–(20) model the intersection between the first and second stages
paths $X$ and $Y$. In much the same way, we can linearize the constraints (15)
and (16). We conclude that the Rec SP problem with
$\Phi^{\mathrm{incl}}(X,k)$, $\Phi^{\mathrm{excl}}(X,k)$ and
$\Phi^{\mathrm{sym}}(X,k)$ admits compact MIP formulations.

###  3.2 Recoverable shortest path problem in acyclic multidigraphs

In this section we show that Rec SP with the neighborhoods
$\Phi^{\mathrm{incl}}(X,k)$, $\Phi^{\mathrm{excl}}(X,k)$ and
$\Phi^{\mathrm{sym}}(X,k)$ can be solved in polynomial time if the input graph
$G$ is an acyclic multidigraph. Observe that we can drop the assumption about
the nonnegativity of arc costs for this class of graphs. We first assume that
$G$ is layered and then we will generalize the result for arbitrary acyclic
multidigraphs.

####  3.2.1 Layered multidigraphs

In a layered multigraph $G=(V,A)$ the set of nodes $V$ is partitioned into $H$
disjoint subsets called layers, i.e. $V=V_{1}\cup\cdots\cup V_{H}$, and the
arcs go only from nodes in $V_{h}$ to nodes in $V_{h+1}$ for each $h\in[H-1]$.
Without loss of generality, we can assume $s\in V_{1}$ and $t\in V_{H}$. In a
layered multidigraphs all $s-t$ paths have the same cardinality. Therefore,
for every path $X\in\Phi$ and any $k=0,\dots,H-1$,
$\Phi^{\mathrm{incl}}(X,k)=\Phi^{\mathrm{excl}}(X,k)$. Also
$\Phi^{\mathrm{sym}}(X,k)=\Phi^{\mathrm{incl}}(X,\lfloor k/2\rfloor)$.
Therefore, it is enough to construct an algorithm for the arc inclusion
neighborhood $\Phi^{\mathrm{incl}}(X,k)$.

In the following, we will show a polynomial transformation from Rec SP in a
layered multidigraph to the Constrained Shortest Path Problem (CSP for short)
in an acyclic multidigraph. In the CSP problem, we are given an acyclic
multidigraph $G=(V,A)$ with a source $s\in V$ and a sink $t\in V$. Each arc
$e\in A$ has a cost $c_{e}$ and a transition time $t_{e}$. A positive total
transition time limit $T$ is specified. We seek an $s$-$t$ path $\pi$ in $G$
that minimizes the total cost, subject to not exceeding the transition time
limit $T$. The CSP is known to be weakly NP-hard (see, e.g., [16]) and can be
solved in $O(|A|T)$ time [19].

######  Lemma 3.

There is a polynomial time reduction from the Rec SP problem with the
neighborhoods $\Phi^{\mathrm{incl}}(X,k)$, $\Phi^{\mathrm{excl}}(X,k)$ and
$\Phi^{\mathrm{sym}}(X,k)$ in a layered multidigraph $G=(V,A)$ to the CSP
problem in an acyclic multidigraph.

###### Proof.

Let $G=(V,A)$ be a layered multidigraph in an instance of Rec SP with a
recovery parameter $k$. We will show a construction for the arc inclusion
neighborhood $\Phi^{\mathrm{incl}}(X,k)$. We build an acyclic multidigraph
$G^{\prime}=(V^{\prime},A^{\prime})$ in the corresponding instance of CSP as
follows. We fix $V^{\prime}=V$, $s^{\prime}=s$, $t^{\prime}=t$, and
$A^{\prime}$ contains two types of arcs labelled as $e^{(0)}$ and $e^{(1)}$.
Namely, for each pair of nodes $i\in V_{h}$ and $j\in V_{h+1}$, $h\in[H-1]$,
such that there exists at least one arc from $i$ to $j$ (note that $G$ can be
multidigraph), we add to $A^{\prime}$ arc $e^{(0)}=(i,j)$ with the cost
$c_{e^{(0)}}=\min_{e=(u,v)\in A\,:\,u=i,v=j}\\{C_{e}+\overline{c}_{e}\\}$ and
the transition time $t_{e^{(0)}}=0$. For each pair of nodes $i\in V_{g}$ and
$j\in V_{h}$, $g,h\in[H]$, such that the node $j$ is reachable from $i$ and
$1\leq h-g\leq k$, we add to $A^{\prime}$ arc $e^{(1)}=(i,j)$ with the cost
$c_{e^{(1)}}$ being the sum of the cost of a shortest path $X^{*}_{ij}$ from
$i$ to $j$ under $C_{e}$, $e\in A$, and the cost of a shortest path
$Y^{*}_{ij}$ from $i$ to $j$ under $\overline{c}_{e}$, $e\in A$. The the
transition time $t_{e^{(1)}}=|Y^{*}_{ij}\setminus X^{*}_{ij}|$. Since $G$ is
layered, $|X^{*}_{ij}|=|Y^{*}_{ij}|=h-g$ and thus $|Y^{*}_{ij}\setminus
X^{*}_{ij}|\leq h-g$. Finally, we set $T=k$. The graph $G^{\prime}$ can be
constructed in $O(|A||V|)$ time. We need to show that there is a pair of paths
$X\in\Phi$ and $Y\in\Phi^{\mathrm{incl}}(X,k)$ in $G$, feasible to Rec SP,
with the cost $\sum_{e\in X}C_{e}+\sum_{e\in Y}\overline{c}_{e}\leq UB$ if and
only if there is a path $\pi$ in $G^{\prime}$, feasible to CSP, such that
$\sum_{e\in\pi}c_{e}\leq UB$, where $UB\in\mathbb{R}$.

($\Rightarrow$) Let $X\in\Phi$ and $Y\in\Phi^{\mathrm{incl}}(X,k)$ be a pair
of paths, feasible to Rec SP in $G$, with the cost $\sum_{e\in
X}C_{e}+\sum_{e\in Y}\overline{c}_{e}\leq UB$. We form the corresponding
$s$-$t$ path $\pi$ in $G^{\prime}$ as follows. Let
$(i_{1},i_{2},\dots,i_{l})$, where $i_{1}=s$ and $i_{l}=t$ be the sequence of
the common nodes of paths $X$ and $Y$ in the order of visiting. This sequence
is the same for $X$ and $Y$ because $G$ is acyclic (an example is shown in
Figure 2). For each $i=2,\dots,l$, if $e=(i_{j-1},i_{j})\in X\cap Y$, then we
add to $\pi$ the arc $e^{(0)}=(i_{j},i_{j-1})\in A^{\prime}$. Notice that the
cost of $e^{(0)}$ is not greater than $C_{e}+\overline{c}_{e}$ and its
transition time is 0. If $e=(i_{j-1},i_{j})\notin X\cap Y$, then there are two
disjoint subpaths $X^{\prime}$ of $X$ and $Y^{\prime}$ of $Y$ from $i_{j-1}$
to $i_{j}$ in $G$. In this case, we add to $\pi$ the arc
$e^{(1)}=(i_{j},i_{j-1})\in A^{\prime}$. Notice that the cost of $e^{(1)}$ is
not greater than $\sum_{e\in X^{\prime}}C_{e}+\sum_{e\in
Y^{\prime}}\overline{c}_{e}$. Also, the transition time of $e^{(1)}$ is not
greater than $|Y^{\prime}\setminus X^{\prime}|$, which follows from the
layered structure of the input graph $G$. The arc $e^{(0)}$ (resp. $e^{(1)}$)
must exist in $G^{\prime}$, because $i_{j}$ is reachable from $i_{j-1}$ in
$G$. Therefore, $\pi$ is an $s$-$t$ path in $G^{\prime}$. It is also feasible
because its total transition time is at most $|Y\setminus X|\leq k$. Finally
the total cost of $\pi$ is not greater than $\sum_{e\in X}C_{e}+\sum_{e\in
Y}\overline{c}_{e}\leq UB$.

Figure 2: Illustration of the proof of Lemma 3 for $\Phi^{\mathrm{incl}}(X,k)$
and $\Phi^{\mathrm{excl}}(X,k)$. The dashed circles denote the layers. The
pair of paths $X$ and $Y$ in $G$ corresponds to the path $\pi$ in
$G^{\prime}$.

($\Leftarrow$) Assume that $\pi$ is an $s$-$t$ path in $G^{\prime}$, feasible
to CSP, with $\sum_{e\in\pi}c_{e}\leq UB$. For each arc $e^{(0)}=(i,j)\in\pi$,
we add the arc $e=(i,j)\in A$ such that $C_{e}+\overline{c}_{e}=c_{e^{(0)}}$
to $X$ and to $Y$. For each arc $e^{(1)}=(i,j)\in\pi$, we add the arcs
corresponding to $X^{*}_{ij}$ to $X$ and the arcs corresponding to
$Y^{*}_{ij}$ to $Y$. It is easily seen that $X\in\Phi$,
$Y\in\Phi^{\mathrm{incl}}(X,k)$ and $UB\geq\sum_{e\in\pi}c_{e}=\sum_{e\in
X}C_{e}+\sum_{e\in Y}\overline{c}_{e}$. ∎

We get the following result:

######  Theorem 6.

Rec SP with the neighborhoods $\Phi^{\mathrm{incl}}(X,k)$,
$\Phi^{\mathrm{excl}}(X,k)$ and $\Phi^{\mathrm{sym}}(X,k)$ in a layered
multidigraph $G=(V,A)$ can be solved in $O(|A||V|+|V|^{2}k)$ time.

###### Proof.

The graph $G^{\prime}$ from the proof of Lemma 3 can be constructed in
$O(|A||V|)$ time. The number of arcs in $G^{\prime}$ is $O(|V|^{2})$, so the
corresponding CSP problem can be solved in $O(|V|^{2}k)$ time. Hence the
overall running time is $O(|A||V|+|V|^{2}k)$. ∎

####  3.2.2 General acyclic multidigraphs

If the input graph $G$ is layered, then the disjoint subpaths of $X$ and $Y$
between any pair of nodes $i$ and $j$ have the same cardinalities (the number
of arcs). This fact has been exploited in Section 3.2.1. However, in general,
acyclic multidigraphs, the paths from $i$ to $j$ can have different
cardinalities, so cheaper recoverable action can require choosing more arcs.
To overcome this problem, we will extend the construction of the graph
$G^{\prime}$ shown in the proof of Lemma 3. However, the neighborhoods are not
equivalent now, and we must consider them separately.

######  Lemma 4.

There is a polynomial time reduction from the Rec SP with the neighborhood
$\Phi^{\mathrm{incl}}(X,k)$ in an acyclic multidigraph $G=(V,A)$ to the CSP
problem in an acyclic multidigraph.

###### Proof.

Given an acyclic multidigraph $G=(V,A)$ and a recovery parameter $k$ in an
instance of Rec SP, we construct an acyclic multidigraph
$G^{\prime}=(V^{\prime},A^{\prime})$ in the corresponding instance of CSP. We
set $V^{\prime}=V$, $s^{\prime}=s$, $t^{\prime}=t$, and the set of arcs
$A^{\prime}$ can contain $k+1$ types of arcs labeled as
$e^{(0)},\dots,e^{(k)}$, respectively. For each pair of nodes $i,j\in V$,
$i\not=j$, such that there exists at least one arc from $i$ to $j$ (recall
that $G$ can be a multidigraph), we add to $A^{\prime}$ the arc
$e^{(0)}=(i,j)$ with the cost $c_{e^{(0)}}=\min_{e=(k,l)\in
A\,:\,k=i,l=j}\\{C_{e}+\overline{c}_{e}\\}$ and the transition time
$t_{e^{(0)}}=0$. Consider a pair of nodes $i,j\in V$, $i\not=j$, such that $j$
is reachable from $i$. We first compute a path from $i$ to $j$ having the
minimum number of arcs $L^{*}_{ij}$. If $L_{ij}^{*}>k$, then we do nothing.
Otherwise, we find a shortest path $X^{*}_{ij}$ from $i$ to $j$ with the costs
$C_{e}$. Then, for each $l=L_{ij}^{*},\dots,k$, we find a shortest path
$Y^{*(l)}_{ij}$ with the costs $\overline{c}_{e}$, $e\in A$, subject to the
condition that $Y^{*(l)}_{ij}$ has at most $l$ arcs. Observe that
$Y^{*(l)}_{ij}$ can be found in $O(|A|k)$ time by solving a CSP problem with
arc transition times equal to 1 and the transition time limit equal to $l$. We
add to $A^{\prime}$ the arc $e^{(l)}=(i,j)$ with the cost
$c_{e^{(l)}}=\sum_{e\in X^{*}_{ij}}C_{e}+\sum_{e\in
Y^{*(l)}_{ij}}\overline{c}_{e}$ and with the transition time $t_{e^{(l)}}=l$.
Finally, we set $T=k$. Graph $G^{\prime}$ can be constructed in
$O(|V|^{2}|A|k^{2})$ time since we have to solve at most $k$ CSP problems for
at most $|V|^{2}$ pairs of nodes. As in Lemma 3, we need to show that there is
a pair of paths $X\in\Phi$ and $Y\in\Phi^{\mathrm{incl}}(X,k)$ in $G$,
feasible to Rec SP, with the cost $\sum_{e\in X}C_{e}+\sum_{e\in
Y}\overline{c}_{e}\leq UB$ if and only if there is a path $\pi$ in
$G^{\prime}$, feasible to CSP, such that $\sum_{e\in\pi}c_{e}\leq UB$, where
$UB\in\mathbb{R}$.

($\Rightarrow$) The proof goes the same way as the proof of Lemma 3. Now, if
$e=(i_{j-1},i_{j})\notin X\cap Y$, then there are two disjoint subpaths
$X^{\prime}$ and $Y^{\prime}$ from $i_{j-1}$ to $i_{j}$ in $G$. The subpath
$Y^{\prime}$ has $l\in\\{L^{*}_{i_{j-1}i_{j}},\dots,k\\}$ arcs. We add to
$\pi$ the arc $e^{(l)}=(i_{j-1},i_{j})\in A^{\prime}$. The transition time of
$e^{(l)}$ is $|Y^{\prime}\setminus X^{\prime}|=l$ and its cost is at most
$\sum_{e\in X^{\prime}}C_{e}+\sum_{e\in Y^{\prime}}\overline{c}_{e}$. The rest
of the proof is the same as in Lemma 3 (an example is depicted in Figure 3).

Figure 3: Illustration of the proof of Lemma 4. The pair of paths $X$ and $Y$
for $\Phi^{\mathrm{incl}}(X,k)$ in $G$ corresponds to the path $\pi$ in
$G^{\prime}$.

($\Leftarrow$) Assume that $\pi$ is an $s$-$t$ path in $G^{\prime}$ feasible
to CSP with $\sum_{e\in\pi}c_{e}\leq UB$. For each arc $e^{(0)}=(i,j)\in\pi$,
we add the arc $e=(i,j)\in A$ such that $C_{e}+\overline{c}_{e}=c_{e^{(0)}}$
to $X$ and to $Y$. For each arc $e^{(l)}=(i,j)\in\pi$, we add the arcs
corresponding to $X^{*}_{ij}$ to $X$ and the arcs corresponding to
$Y^{*(l)}_{ij}$ to $Y$, we recall that $|Y^{*(l)}_{ij}|\leq l$. It follows
easily that $X\in\Phi$, $Y\in\Phi^{\mathrm{incl}}(X,k)$ and
$UB\geq\sum_{e\in\pi}c_{e}=\sum_{e\in X}C_{e}+\sum_{e\in Y}\overline{c}_{e}$.
∎

######  Lemma 5.

There is a polynomial time reduction from the Rec SP problem with the
neighborhood $\Phi^{\mathrm{excl}}(X,k)$ in an acyclic multidigraph $G=(V,A)$
to the CSP problem in an acyclic multidigraph.

###### Proof.

The reduction is similar to that in the proof of Lemma 4. We only point out
some differences. Having computed $L^{*}_{ij}\leq k$, we find a shortest path
$Y^{*}_{ij}$ from $i$ to $j$ with the arc costs $\overline{c}_{e}$. Then, for
each $l=L_{ij}^{*},\dots,k$, we find a shortest path $X_{ij}^{*(l)}$ with the
arc costs $C_{e}$, subject to the condition that $X_{ij}^{*(l)}$ has at most
$l$ arcs. We add to $A^{\prime}$ the arc $e^{(l)}=(i,j)$ with the cost
$c_{e^{(l)}}=\sum_{e\in Y^{*}_{ij}}\overline{c}_{e}+\sum_{e\in
X^{*(l)}_{ij}}C_{e}$ and with the transition time $t_{e^{(l)}}=l$. The proof
goes then similarly to the proof of Lemma 4 with the following modifications:

($\Rightarrow$) If $e=(i_{j-1},i_{j})\notin X\cap Y$, then the subpath
$X^{\prime}$ from $i_{j-1}$ to $i_{j}$ in $G$ has
$l\in\\{L^{*}_{i_{j-1}i_{j}},\dots,k\\}$ arcs. We add to $\pi$ the arc
$e^{(l)}=(i_{j-1},i_{j})\in A^{\prime}$. The transition time of $e^{(l)}$ is
$|X^{\prime}\setminus Y^{\prime}|=l$ and its cost is at most $\sum_{e\in
X^{\prime}}C_{e}+\sum_{e\in Y^{\prime}}\overline{c}_{e}$.

($\Leftarrow$) For each arc $e^{(l)}=(i,j)\in\pi$, we add the arcs
corresponding to $Y^{*}_{ij}$ to $Y$ and the arcs corresponding to
$X^{*(l)}_{ij}$ to $X$ and we note that $|X^{*(l)}_{ij}|\leq l$. It follows
then easily that $X\in\Phi$, $Y\in\Phi^{\mathrm{excl}}(X,k)$ and
$UB\geq\sum_{e\in\pi}c_{e}=\sum_{e\in X}C_{e}+\sum_{e\in Y}\overline{c}_{e}$.
∎

######  Lemma 6.

There is a polynomial time reduction from the Rec SP problem with the
neighborhood $\Phi^{\mathrm{sym}}(X,k)$ in an acyclic multidigraph $G=(V,A)$
to the CSP problem in an acyclic multidigraph.

###### Proof.

We again point out some differences in the reduction from Lemma 4. Having
computed $L_{ij}^{*}$, if $2L_{ij}^{*}>k$, then we do nothing. Otherwise, for
each $u=L_{ij}^{*},\dots,k$ and $v=L_{ij}^{*},\dots,k$, we find a shortest
path $X^{*(u)}_{ij}$ with the costs $C_{e}$, $e\in A$, subject to the
constraint $|X^{*(u)}_{ij}|\leq u$ and a shortest path $Y^{*(v)}_{ij}$ with
the costs $\overline{c}_{e}$, $e\in A$, subject to the constraint
$|Y^{*(v)}_{ij}|\leq v$. We add to $A^{\prime}$ the arc $e^{(uv)}=(i,j)$ with
the cost $c_{e^{(uv)}}=\sum_{e\in X^{*(u)}_{ij}}C_{e}+\sum_{e\in
Y^{*(v)}_{ij}}\overline{c}_{e}$ and the transition time $t_{e^{(uv)}}=u+v$.
Graph $G^{\prime}$ can be constructed in $O(|V|^{2}|A|k^{3})$ time because we
have to solve at most $k^{2}$ CSP problems for at most $|V|^{2}$ pairs of
nodes. The proof goes then similarly to the proof of Lemma 4 with the
following modifications:

($\Rightarrow$) If $e=(i_{j-1},i_{j})\notin X\cap Y$, then the subpaths
$X^{\prime}$ and $Y^{\prime}$ from $i_{j-1}$ to $i_{j}$ in $G$ have
$u,v\in\\{L^{*}_{i_{j-1}i_{j}},\dots,k\\}$ arcs, respectively. We add to $\pi$
the arc $e^{(uv)}=(i_{j-1},i_{j})\in A^{\prime}$. The transition time of
$e^{(uv)}$ is $|(Y^{\prime}\setminus X^{\prime})\cup(X^{\prime}\setminus
Y^{\prime})|=u+v$ and its cost is at most $\sum_{e\in
X^{\prime}}C_{e}+\sum_{e\in Y^{\prime}}\overline{c}_{e}$.

($\Leftarrow$) For each arc $e^{(uv)}=(i,j)\in\pi$, we add the arcs
corresponding to $X^{*(u)}_{ij}$ to $X$ and the arcs corresponding to
$Y^{*(v)}_{ij}$ to $Y$, where $|X^{*(u)}_{ij}|\leq u$ and $|Y^{*(v)}_{ij}|\leq
v$. Thus, $X\in\Phi$, $Y\in\Phi^{\mathrm{sym}}(X,k)$ and
$UB\geq\sum_{e\in\pi}c_{e}=\sum_{e\in X}C_{e}+\sum_{e\in Y}\overline{c}_{e}$.
∎

######  Theorem 7.

Rec SP in acyclic multidigraph $G=(V,A)$ can be solved in $O(|V|^{2}|A|k^{2})$
time for the neighborhoods $\Phi^{\mathrm{incl}}(X,k)$,
$\Phi^{\mathrm{excl}}(X,k)$ and in $O(|V|^{2}|A|k^{3})$) time for the
neighborhood $\Phi^{\mathrm{sym}}(X,k)$.

###### Proof.

The multidigraphs $G^{\prime}$ from Lemma 4 and Lemma 5 can be constructed in
$O(|V|^{2}|A|k^{2})$ time and have at most $|V|^{2}(k+1)$ arcs. The CSP
problem in $G^{\prime}$ can then be solved in $O(|V|^{2}k^{2})$ time. The
overall running time for $\Phi^{\mathrm{incl}}(X,k)$ and
$\Phi^{\mathrm{excl}}(X,k)$ is $O(|V|^{2}|A|k^{2})$. Accordingly, the
multidigraph $G^{\prime}$ from Lemma 6 can be constructed in
$O(|V|^{2}|A|k^{3})$ time and has at most $|V|^{2}(k^{2}+1)$ arcs. The CSP
problem in $G^{\prime}$ can then be solved in $O(|V|^{2}k^{3})$ time. Hence,
the overall running time for $\Phi^{\mathrm{sym}}(X,k)$ is
$O(|V|^{2}|A|k^{3})$. ∎

####  3.2.3 Series-parallel multidigraph

In this section, we will construct faster algorithms for Rec SP with all the
considered neighborhoods, assuming that $G$ is an arc series-parallel
multidigraph. Again, we have to treat all the considered neighborhoods
separately, as the subpaths between two nodes of $G$ may have different
cardinalities. Let us recall that an arc series-parallel multidigraph (ASP) is
recursively defined as follows (see, e.g., [32]). A graph consisting of two
nodes joined by a single arc is ASP. If $G_{1}$ and $G_{2}$ are ASP, so are
the multidigraphs constructed by each of the following two operations:

  * •

_parallel composition_ $p(G_{1},G_{2})$: identify the source of $G_{1}$ with
the source of $G_{2}$ and the sink of $G_{1}$ with the sink of $G_{2}$,

  * •

_series composition_ $s(G_{1},G_{2})$: identify the sink of $G_{1}$ with the
source of $G_{2}$.

Each ASP multidigraph $G$ is associated with a rooted binary tree
$\mathcal{T}$, called _the binary decomposition tree of $G$_, which can be
constructed in $O(|A|)$ time [32]. Each leaf of the tree represents an arc in
$G$. Each internal node $\sigma$ of $\mathcal{T}$ is labeled by $\mathtt{S}$
or $\mathtt{P}$ and corresponds to the series or parallel composition in $G$.
Every node $\sigma$ of $\mathcal{T}$ corresponds to an ASP subgraph of $G$,
denoted by $G_{\sigma}$, defined by the subtree rooted at $\sigma$. The root
of $\mathcal{T}$ represents the input ASP multidigraph $G$.

In [7], Büsing showed an idea of a polynomial-time algorithm for Rec SP with
$\Phi^{\mathrm{incl}}(X,k)$ in ASP, together with a theorem resulting from it
[7, Theorem 5]. In this section, we will describe a complete
$O(|A|k^{2})$-time algorithm for Rec SP in ASP with the neighborhoods
$\Phi^{\mathrm{incl}}(X,k)$, $\Phi^{\mathrm{excl}}(X,k)$ and
$\Phi^{\mathrm{sym}}(X,k)$. Let $\Phi_{G_{\sigma}}$ denote the set of all
paths from the source to the sink in $G_{\sigma}$ and

$\displaystyle\Phi^{l}_{G_{\sigma}}=\\{X\in\Phi_{G_{\sigma}}\,:\,|X|=l\\},$
$\displaystyle\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}=\\{(X,Y)\in\Phi_{G_{\sigma}}\times\Phi_{G_{\sigma}}\,:|Y\setminus
X|=l\\},$
$\displaystyle\Psi^{\mathrm{excl}[l]}_{G_{\sigma}}=\\{(X,Y)\in\Phi_{G_{\sigma}}\times\Phi_{G_{\sigma}}\,:|X\setminus
Y|=l\\},$
$\displaystyle\Psi^{\mathrm{sym}[l]}_{G_{\sigma}}=\\{(X,Y)\in\Phi_{G_{\sigma}}\times\Phi_{G_{\sigma}}\,:|Y\setminus
X|+|X\setminus Y|=l\\}.$

Consider first the arc inclusion neighborhood $\Phi^{\mathrm{incl}}(X,k)$. For
each ASP subgraph $G_{\sigma}$, we store the following three crucial pieces of
information. The first one is the cost of a shortest path from the source to
the sink in $G_{\sigma}$ under costs $C_{e}$, $e\in A$:

$C_{G_{\sigma}}=\min_{X\in\Phi_{G_{\sigma}}}\sum_{e\in X}C_{e}.$ (21)

The second one is the $k$-element array
$\overline{\boldsymbol{c}}_{G_{\sigma}}$, whose $l$-th element
$\overline{\boldsymbol{c}}_{G_{\sigma}}[l]$ is the cost of a shortest path
$Y^{*}\in\Phi^{l}_{G_{\sigma}}$ under the costs $\overline{c}_{e}$, $e\in A$,
if such a path exists:

$\overline{\boldsymbol{c}}_{G_{\sigma}}[l]=\begin{cases}\displaystyle\min_{Y\in\Phi^{l}_{G_{\sigma}}}\sum_{e\in
Y}\overline{c}_{e}&\text{if $\Phi^{l}_{G_{\sigma}}\not=\emptyset$,}\\\
+\infty&\text{otherwise},\end{cases}\quad l=1,\ldots,k.$ (22)

The third one is the $(k+1)$-element array $\boldsymbol{c}^{*}_{G_{\sigma}}$,
whose $l$-th element $\boldsymbol{c}^{*}_{G_{\sigma}}[l]$, stores the cost of
an optimal pair $(X^{*},Y^{*})\in\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}$, if
such paths exist:

$\boldsymbol{c}^{*}_{G_{\sigma}}[l]=\begin{cases}\displaystyle\min_{(X,Y)\in\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}}\left(\sum_{e\in
X}C_{e}+\sum_{e\in Y}\overline{c}_{e}\right)&\text{if
$\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}\not=\emptyset$},\\\
+\infty&\text{otherwise},\end{cases}\quad l=0,\ldots,k.$ (23)

Note that at least one set of paths $\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}$ is
always nonempty in $G_{\sigma}$, for instance, when $l=0$. For each leaf node
$\sigma$ of the tree $\mathcal{T}$ (in this case, the subgraph $G_{\sigma}$
consists of a single arc $e\in A$), the initial values of $C_{G_{\sigma}}$,
$\overline{\boldsymbol{c}}_{G_{\sigma}}$ and $\boldsymbol{c}^{*}_{G_{\sigma}}$
are as follows:

$\displaystyle C_{G_{\sigma}}=C_{e},$ (24)
$\displaystyle\overline{\boldsymbol{c}}_{G_{\sigma}}[1]=\overline{c}_{e},\;\overline{\boldsymbol{c}}_{G_{\sigma}}[l]=+\infty,$
$\displaystyle l=2,\ldots,k,$ (25)
$\displaystyle\boldsymbol{c}^{*}_{G_{\sigma}}[0]=C_{e}+\overline{c}_{e},\;\boldsymbol{c}^{*}_{G_{\sigma}}[l]=+\infty,$
$\displaystyle l=1,\ldots,k.$ (26)

By traversing the tree $\mathcal{T}$ from the leaves to the root, we
recursively construct each ASP subgraph $G_{\sigma}$ corresponding to the
internal node $\sigma$ and compute the values of $C_{G_{\sigma}}$,
$\overline{\boldsymbol{c}}_{G_{\sigma}}$ and $\boldsymbol{c}^{*}_{G_{\sigma}}$
associated with $G_{\sigma}$, depending on the label of the node $\sigma$. If
$\sigma$ is marked $\mathtt{P}$, then we call Algorithm 1, otherwise we call
Algorithm 2, on the subgraph $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$, where $\mathrm{left}(\sigma)$ and
$\mathrm{right}(\sigma)$ are children of $\sigma$ in $\mathcal{T}$. If
$\sigma$ is the root of $\mathcal{T}$, then $G_{\sigma}=G$ and the array
$\boldsymbol{c}^{*}_{G_{\sigma}}$ contains information about the cost of an
optimal pair of paths $X^{*},Y^{*}\in\Phi$, being an optimal solution to Rec
SP in $G$, which is equal to

$\min_{0\leq l\leq k}\boldsymbol{c}^{*}_{G_{\sigma}}[l].$

The algorithm for Rec SP with $\Phi^{\mathrm{incl}}(X,k)$ is given in the form
of Algorithm 3. For simplicity of the presentation, we have only shown how to
compute the costs stored in $C_{G_{\sigma}}$,
$\overline{\boldsymbol{c}}_{G_{\sigma}}$ and
$\boldsymbol{c}^{*}_{G_{\sigma}}$. The associated paths can be easily
reconstructed by using pointers to the first and the last arcs of these paths,
managed during the course of the algorithm.

1 Perform parallel composition $G_{\sigma}\leftarrow
p(G_{\mathrm{left}(\sigma)},G_{\mathrm{right}(\sigma)})$;

2
$\boldsymbol{c}^{*}_{G_{\sigma}}[0]\leftarrow\min\\{\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}[0],\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}}[0]\\}$;

3 for  _$l=1$ _to_ $k$_ do

4
$\boldsymbol{c}^{*}_{G_{\sigma}}[l]\leftarrow\min\\{\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}[l],\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}}[l],C_{G_{\mathrm{left}(\sigma)}}+\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}}[l],C_{G_{\mathrm{right}(\sigma)}}+\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}}[l]\\}$
;

5
$\overline{\boldsymbol{c}}_{G_{\sigma}}[l]\leftarrow\min\\{\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}}[l],\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}}[l]\\}$

6$C_{G_{\sigma}}\leftarrow\min\\{C_{G_{\mathrm{left}(\sigma)}},C_{G_{\mathrm{right}(\sigma)}}\\}$;

return
_$(G_{\sigma},\boldsymbol{c}^{*}_{G_{\sigma}},C_{G_{\sigma}},\overline{\boldsymbol{c}}_{G_{\sigma}})$_

Algorithm 1
P-incl$(G_{\mathrm{left}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}},C_{G_{\mathrm{left}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}},G_{\mathrm{right}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}},C_{G_{\mathrm{right}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}})$

1 Perform series composition $G_{\sigma}\leftarrow
s(G_{\mathrm{left}(\sigma)},G_{\mathrm{right}(\sigma)})$;

2 for  _$l=0$ _to_ $k$_ do

3 $\boldsymbol{c}^{*}_{G_{\sigma}}[l]\leftarrow\min_{0\leq j\leq
l}\\{\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}[j]+\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}}[l-j]\\}$

4$C_{G_{\sigma}}\leftarrow
C_{G_{\mathrm{left}(\sigma)}}+C_{G_{\mathrm{right}(\sigma)}}$;

5 $\overline{\boldsymbol{c}}_{G_{\sigma}}[1]\leftarrow+\infty$;

6 for  _$l=2$ _to_ $k$_ do

7 $\overline{\boldsymbol{c}}_{G_{\sigma}}[l]\leftarrow\min_{1\leq
j<l}\\{\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}}[j]+\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}}[l-j]\\}$

return
_$(G_{\sigma},\boldsymbol{c}^{*}_{G_{\sigma}},C_{G_{\sigma}},\overline{\boldsymbol{c}}_{G_{\sigma}})$_

Algorithm 2
S-incl$(G_{\mathrm{left}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}},C_{G_{\mathrm{left}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}},G_{\mathrm{right}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}},C_{G_{\mathrm{right}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}})$

1 Find the binary decomposition tree $\mathcal{T}$ of $G$;

2 foreach  _leaf $\sigma$ of $\mathcal{T}$ _ do // Initially $\sigma$
corresponds to arc $e\in A$

3 $\boldsymbol{c}^{*}_{G_{\sigma}}[0]\leftarrow C_{e}+\overline{c}_{e}$;

4 for  _$l=1$ _to_ $k$_ do
$\boldsymbol{c}^{*}_{G_{\sigma}}[l]\leftarrow+\infty$;

5 $C_{G_{\sigma}}\leftarrow C_{e}$;

6 $\overline{\boldsymbol{c}}_{G_{\sigma}}[1]\leftarrow\overline{c}_{e}$;

7 for  _$l=2$ _to_ $k$_ do
$\overline{\boldsymbol{c}}_{G_{\sigma}}[l]\leftarrow+\infty$;

8

9while  _there is a node $\sigma$ in $\mathcal{T}$ with two leaves:
$\mathrm{left}(\sigma)$ and $\mathrm{right}(\sigma)$ _ do

10 if  _node $\sigma$ is labeled $\mathtt{P}$ in $\mathcal{T}$_ then

11
$(G_{\sigma},\boldsymbol{c}^{*}_{G_{\sigma}},C_{G_{\sigma}},\overline{\boldsymbol{c}}_{G_{\sigma}})\leftarrow\texttt{P-incl}(G_{\mathrm{left}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}C_{G_{\mathrm{left}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}},G_{\mathrm{right}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}},C_{G_{\mathrm{right}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}})$

12 else // node $\sigma$ is labeled $\mathtt{S}$ in $\mathcal{T}$

13
$(G_{\sigma},\boldsymbol{c}^{*}_{G_{\sigma}},C_{G_{\sigma}},\overline{\boldsymbol{c}}_{G_{\sigma}})\leftarrow\texttt{S-incl}(G_{\mathrm{left}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}C_{G_{\mathrm{left}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}},G_{\mathrm{right}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}},C_{G_{\mathrm{right}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}})$

14 Delete leaves $\mathrm{left}(\sigma)$ and $\mathrm{right}(\sigma)$ from
$\mathcal{T}$;

15

return _$\min_{0\leq l\leq k}\boldsymbol{c}^{*}_{G_{\sigma}}[l]$_ // node
$\sigma$ is the root of $\mathcal{T}$ corresponding to $G$

Algorithm 3 Solve Rec SP in ASP$(G,\\{C_{e}\\}_{e\in
A},\\{\overline{c}_{e}\\}_{e\in A},k,s,t)$ with $\Phi^{\mathrm{incl}}(X,k)$

An algorithm for Rec SP with $\Phi^{\mathrm{excl}}(X,k)$ is symmetric to the
one with $\Phi^{\mathrm{incl}}(X,k)$. We also store three pieces of
information for each ASP subgraph $G_{\sigma}$. Namely, the cost of a shortest
path from the source to the sink in $G_{\sigma}$ under costs
$\overline{c}_{e}$, $e\in A$:

$\overline{c}_{G_{\sigma}}=\min_{Y\in\Phi_{G_{\sigma}}}\sum_{e\in
Y}\overline{c}_{e}.$ (27)

The $k$-element array $\boldsymbol{C}_{G_{\sigma}}$, whose $l$-th element
$\boldsymbol{C}_{G_{\sigma}}[l]$ is the cost of a shortest path from the
source to the sink in $G_{\sigma}$ under costs $C_{e}$, $e\in A$, that uses
exactly $l$ arcs if such a path exists:

$\boldsymbol{C}_{G_{\sigma}}[l]=\begin{cases}\displaystyle\min_{X\in\Phi^{l}_{G_{\sigma}}}\sum_{e\in
X}C_{e}&\text{if $\Phi^{l}_{G_{\sigma}}\not=\emptyset$,}\\\
+\infty&\text{otherwise},\end{cases}\quad l=1,\ldots,k.$ (28)

The third element is the $(k+1)$-element array
$\boldsymbol{c}^{*}_{G_{\sigma}}$ whose definition is the same as (23) with
the exception that $\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}$ is replaced with
$\Psi^{\mathrm{excl}[l]}_{G_{\sigma}}$. The initial values of
$\overline{c}_{G_{\sigma}}$, $\boldsymbol{C}_{G_{\sigma}}$ and
$\boldsymbol{c}^{*}_{G_{\sigma}}$ for each leaf node $\sigma$ of the tree
$\mathcal{T}$ are as follows:

$\displaystyle\overline{c}_{G_{\sigma}}=\overline{c}_{e},$ (29)
$\displaystyle\boldsymbol{C}_{G_{\sigma}}[1]=C_{e},\;\boldsymbol{C}_{G_{\sigma}}[l]=+\infty,$
$\displaystyle l=2,\ldots,k,$ (30)
$\displaystyle\boldsymbol{c}^{*}_{G_{\sigma}}[0]=C_{e}+\overline{c}_{e},\;\boldsymbol{c}^{*}_{G_{\sigma}}[l]=+\infty,$
$\displaystyle l=1,\ldots,k.$ (31)

It is easily seen that adapting Algorithms 1 and 2 and, in consequence,
Algorithm 3 for the neighborhood $\Phi^{\mathrm{excl}}(X,k)$ requires small
changes in them that take into account $\overline{c}_{G_{\sigma}}$,
$\boldsymbol{C}_{G_{\sigma}}$, $\boldsymbol{c}^{*}_{G_{\sigma}}$, and
(29)–(31).

An algorithm for Rec SP with the symmetric difference neighborhood
$\Phi^{\mathrm{sym}}(X,k)$ combines the ideas for the neighborhoods
$\Phi^{\mathrm{incl}}(X,k)$ and $\Phi^{\mathrm{excl}}(X,k)$. Now, the three
arrays are associated with each ASP subgraph $G_{\sigma}$. Namely, the
$(k-1)$-element arrays $\boldsymbol{\overline{c}}_{G_{\sigma}}$, and
$\boldsymbol{C}_{G_{\sigma}}$ defined as (22) and (28), respectively, for
$l\in[k-1]$. The $(k+1)$-element array $\boldsymbol{c}^{*}_{G_{\sigma}}$,
whose definition is the same as (23), with the exception that
$\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}$ is replaced with
$\Psi^{\mathrm{sym}[l]}_{G_{\sigma}}$. Of course,
$\boldsymbol{c}^{*}_{G_{\sigma}}[1]=+\infty$. The initial values of
$\boldsymbol{\overline{c}}_{G_{\sigma}}$, $\boldsymbol{C}_{G_{\sigma}}$, and
$\boldsymbol{c}^{*}_{G_{\sigma}}$, for each leaf node $\sigma$ of the tree
$\mathcal{T}$, are as follows:

$\displaystyle\overline{\boldsymbol{c}}_{G_{\sigma}}[1]=\overline{c}_{e},$
$\displaystyle\overline{\boldsymbol{c}}_{G_{\sigma}}[l]=+\infty,$
$\displaystyle l=2,\ldots,k-1,$ (32)
$\displaystyle\boldsymbol{C}_{G_{\sigma}}[1]=C_{e},$
$\displaystyle\boldsymbol{C}_{G_{\sigma}}[l]=+\infty,$ $\displaystyle
l=2,\ldots,k-1,$ (33)
$\displaystyle\boldsymbol{c}^{*}_{G_{\sigma}}[0]=C_{e}+\overline{c}_{e},$
$\displaystyle\boldsymbol{c}^{*}_{G_{\sigma}}[l]=+\infty,$ $\displaystyle
l=1,\ldots,k.$ (34)

1 Perform parallel composition $G_{\sigma}\leftarrow
p(G_{\mathrm{left}(\sigma)},G_{\mathrm{right}(\sigma)})$;

2
$\boldsymbol{c}^{*}_{G_{\sigma}}[0]\leftarrow\min\\{\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}[0],\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}}[0]\\}$;

3 $\boldsymbol{c}^{*}_{G_{\sigma}}[1]\leftarrow+\infty$;

4 for  _$l=2$ _to_ $k$_ do

5 $\boldsymbol{c}^{*}_{G_{\sigma}}[l]\leftarrow\min_{1\leq
j<l}\\{\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}[l],\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}}[l],\boldsymbol{C}_{G_{\mathrm{left}(\sigma)}}[j]+\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}}[l-j],\boldsymbol{C}_{G_{\mathrm{right}(\sigma)}}[j]+\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}}[l-j]\\}$;

6

7for  _$l=1$ _to_ $k-1$_ do

8
$\boldsymbol{C}_{G_{\sigma}}[l]\leftarrow\min\\{\boldsymbol{C}_{G_{\mathrm{left}(\sigma)}}[l],\boldsymbol{C}_{G_{\mathrm{right}(\sigma)}}[l]\\}$;

9
$\overline{\boldsymbol{c}}_{G_{\sigma}}[l]\leftarrow\min\\{\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}}[l],\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}}[l]\\}$

return
_$(G_{\sigma},\boldsymbol{c}^{*}_{G_{\sigma}},\boldsymbol{C}_{G_{\sigma}},\overline{\boldsymbol{c}}_{G_{\sigma}})$_

Algorithm 4
P-sym$(G_{\mathrm{left}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}},\boldsymbol{C}_{G_{\mathrm{left}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}},G_{\mathrm{right}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}},\boldsymbol{C}_{G_{\mathrm{right}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}})$

1 Perform series composition $G_{\sigma}\leftarrow
s(G_{\mathrm{left}(\sigma)},G_{\mathrm{right}(\sigma)})$;

2 for  _$l=0$ _to_ $k$_ do

3 $\boldsymbol{c}^{*}_{G_{\sigma}}[l]\leftarrow\min_{0\leq j\leq
l}\\{\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}}[j]+\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}}[l-j]\\}$

4$\boldsymbol{C}_{G_{\sigma}}[1]\leftarrow+\infty$;

5 $\overline{\boldsymbol{c}}_{G_{\sigma}}[1]\leftarrow+\infty$;

6 for  _$l=2$ _to_ $k-1$_ do

7 $\boldsymbol{C}_{G_{\sigma}}[l]\leftarrow\min_{1\leq
j<l}\\{\boldsymbol{C}_{G_{\mathrm{left}(\sigma)}}[j]+\boldsymbol{C}_{G_{\mathrm{right}(\sigma)}}[l-j]\\}$;

8 $\overline{\boldsymbol{c}}_{G_{\sigma}}[l]\leftarrow\min_{1\leq
j<l}\\{\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}}[j]+\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}}[l-j]\\}$

return
_$(G_{\sigma},\boldsymbol{c}^{*}_{G_{\sigma}},\boldsymbol{C}_{G_{\sigma}},\overline{\boldsymbol{c}}_{G_{\sigma}})$_

Algorithm 5
S-sym$(G_{\mathrm{left}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{left}(\sigma)}},\boldsymbol{C}_{G_{\mathrm{left}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{left}(\sigma)}},G_{\mathrm{right}(\sigma)},\boldsymbol{c}^{*}_{G_{\mathrm{right}(\sigma)}},\boldsymbol{C}_{G_{\mathrm{right}(\sigma)}},\overline{\boldsymbol{c}}_{G_{\mathrm{right}(\sigma)}})$

In order to give a version of Algorithm 3 for the neighborhood
$\Phi^{\mathrm{sym}}(X,k)$, we need to modify the initialization according to
(32)–(34 (lines 3–3) and call Algorithms 4 and 5 in the lines 3 and 3,
respectively.

We now prove the correctness of the algorithms.

######  Theorem 8.

Rec SP with $\Phi^{\mathrm{incl}}(X,k)$, $\Phi^{\mathrm{excl}}(X,k)$ and
$\Phi^{\mathrm{sym}}(X,k)$ in arc series-parallel multidigraphs $G=(V,A)$ can
be solved in $O(|A|k^{2})$ time.

###### Proof.

We will give a proof only for the arc inclusion neighborhood
$\Phi^{\mathrm{incl}}(X,k)$. The proof for the neighborhood
$\Phi^{\mathrm{excl}}(X,k)$ is almost the same, while a proof for
$\Phi^{\mathrm{sym}}(X,k)$ is similar in spirit to the given below. It is
enough to make some technical changes to take into account the differences
among the neighborhoods described previously in this section.

We first prove that for each node $\sigma$ of the decomposition tree
$\mathcal{T}$, graph $G_{\sigma}$ is an ASP subgraph of $G$ and the
corresponding costs $C_{G_{\sigma}}$, $\overline{\boldsymbol{c}}_{G_{\sigma}}$
and $\boldsymbol{c}^{*}_{G_{\sigma}}$ are correctly computed by Algorithm 3.
The first part of the claim is due to [32]. It is easily seen that after
running lines 3–3, for each leaf $\sigma$ of $\mathcal{T}$, the costs
$C_{G_{\sigma}}$, $\overline{\boldsymbol{c}}_{G_{\sigma}}$ and
$\boldsymbol{c}^{*}_{G_{\sigma}}$, corresponding to the single-arc subgraphs,
are correctly initialized. Hence, if $|A|=1$, then the claim trivially holds.
Assume that $|A|\geq 2$. The proof is by induction on the numbers of
iterations of Algorithm 3 (the lines 3–3).

The base case is when the algorithm runs for only one iteration ($|A|=2$). The
node $\sigma$ is then the root of $\mathcal{T}$ and has two leaves
corresponding to two single-arc subgraphs $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$. If $\sigma$ is labeled $\mathtt{P}$, then the
algorithm P-incl is called for $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$, otherwise the S-incl is called. Consider the
P-incl case. First the parallel composition of $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$ is performed. The resulting graph $G_{\sigma}$
has two parallel arcs, $e_{1},e_{2}$, the source and the sink. We get
$\boldsymbol{c}^{*}_{G_{\sigma}}[0]=\min\\{C_{e_{1}}+\overline{c}_{e_{1}},C_{e_{2}}+\overline{c}_{e_{2}}\\}$,
$\boldsymbol{c}^{*}_{G_{\sigma}}[1]=\min\\{+\infty,+\infty,C_{e_{1}}+\overline{c}_{e_{2}},C_{e_{2}}+\overline{c}_{e_{1}}\\}$,
$\overline{\boldsymbol{c}}_{G_{\sigma}}[1]=\min\\{\overline{c}_{e_{1}},\overline{c}_{e_{2}}\\}$
and $C_{G_{\sigma}}=\min\\{C_{e_{1}},C_{e_{2}}\\}$. The rest of elements of
$\boldsymbol{c}^{*}_{G_{\sigma}}$ and $\overline{\boldsymbol{c}}_{G_{\sigma}}$
are equal to $+\infty$. Let us turn to the case S-incl. Now, after the series
composition of $G_{\mathrm{left}(\sigma)}$ and $G_{\mathrm{right}(\sigma)}$,
the resulting graph $G_{\sigma}$ has three nodes $\\{s,v_{1},t\\}$ and two
series arcs $e_{1}=(s,v_{1})$, $e_{2}=(v_{1},t)$. Therefore, only one $s$-$t$
path exists in $G_{\sigma}$. We get
$\boldsymbol{c}^{*}_{G_{\sigma}}[0]=C_{e_{1}}+\overline{c}_{e_{1}}+C_{e_{2}}+\overline{c}_{e_{2}}$,
$C_{G_{\sigma}}=C_{e_{1}}+C_{e_{2}}$ and
$\overline{\boldsymbol{c}}_{G_{\sigma}}[2]=\overline{c}_{e_{1}}+\overline{c}_{e_{2}}$.
The rest of the elements of $\boldsymbol{c}^{*}_{G_{\sigma}}$ and
$\overline{\boldsymbol{c}}_{G_{\sigma}}$ are equal to $+\infty$. Hence all the
costs $C_{G_{\sigma}}$, $\overline{\boldsymbol{c}}_{G_{\sigma}}$ and
$\boldsymbol{c}^{*}_{G_{\sigma}}$ are correctly computed for the base case.

For the induction step, let $\sigma$ be an internal node of $\mathcal{T}$ with
two leaves $\mathrm{left}(\sigma)$ and $\mathrm{right}(\sigma)$. By the
induction hypothesis, $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$ are ASP subgraphs and the costs $C_{G_{\sigma}}$,
$\overline{\boldsymbol{c}}_{G_{\sigma}}$ and
$\boldsymbol{c}^{*}_{G_{\sigma}}$, associated with them, are correctly
computed. We need to consider two cases that depend on the label of $\sigma$.
The first case (the label $\mathtt{P}$) is when the algorithm P-incl is called
for $G_{\mathrm{left}(\sigma)}$ and $G_{\mathrm{right}(\sigma)}$. After the
parallel composition of $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$, the resulting subgraph $G_{\sigma}$ is an ASP
subgraph. Note that,
$\Phi_{G_{\sigma}}=\Phi_{\mathrm{left}(\sigma)}\cup\Phi_{G_{\mathrm{left}(\sigma)}}$,
where
$\Phi_{G_{\mathrm{left}(\sigma)}}\cap\Phi_{G_{\mathrm{left}(\sigma)}}=\emptyset$.
Hence, we immediately get that the costs computed in lines 1, 1 and 1 of
Algorithm 1 are correctly computed. The costs
$\boldsymbol{c}^{*}_{G_{\sigma}}[l]$, for $l=1,\ldots,k$, (see line 1 of
Algorithm 1), are correctly computed as well. Indeed, the first two terms in
the minimum are obvious. The last two terms take into account the cases when
the optimal paths $X^{*}\in\Phi_{G_{\sigma}}$ and $Y^{*}\in\Phi_{G_{\sigma}}$
in $\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}$ are such that
$X^{*}\in\Phi_{G_{\mathrm{left}(\sigma)}}$ and
$Y^{*}\in\Phi_{G_{\mathrm{right}(\sigma)}}$ or
$X^{*}\in\Phi_{G_{\mathrm{right}(\sigma)}}$ and
$Y^{*}\in\Phi_{G_{\mathrm{left}(\sigma)}}$. Consider the second case (the
label $\mathtt{S}$) when the algorithm S-incl is called. The subgraph
$G_{\sigma}$, after the series composition of $G_{\mathrm{left}(\sigma)}$ and
$G_{\mathrm{right}(\sigma)}$, is an ASP subgraph and there is a node $v$ in
$G_{\sigma}$ being the sink of $G_{\mathrm{left}(\sigma)}$ and the source of
$G_{\mathrm{right}(\sigma)}$. Thus, every path $X\in\Phi_{G_{\sigma}}$ must
traverse the node $v$ and $X$ is the concatenation of
$X_{1}\in\Phi_{G_{\mathrm{left}(\sigma)}}$ and
$X_{2}\in\Phi_{G_{\mathrm{right}(\sigma)}}$. In what follows, for each
$l=0,\ldots,k$, the cost $\boldsymbol{c}^{*}_{G_{\sigma}}[l]$ in $G_{\sigma}$
is the sum of its optimal counterparts, respectively, in
$G_{\mathrm{left}(\sigma)}$ and $G_{\mathrm{right}(\sigma)}$, for some $0\leq
j^{*}\leq l$. It is enough to find such $j^{*}$ for each $l$. A similar
argument holds for the costs $\overline{\boldsymbol{c}}_{G_{\sigma}}[l]$ for
$l=2,\ldots,k$. Therefore, Algorithm 2 correctly computes the costs
$C_{G_{\sigma}}$, $\overline{\boldsymbol{c}}_{G_{\sigma}}$ and
$\boldsymbol{c}^{*}_{G_{\sigma}}$ in lines 2, 2 and 2. This proves the claim.

If $\sigma$ is the root of $\mathcal{T}$, then $G_{\sigma}=G$. It immediately
follows from the claim, that the array $\boldsymbol{c}^{*}_{G_{\sigma}}$
contains the optimal costs of the solutions in
$\Psi^{\mathrm{incl}[l]}_{G_{\sigma}}$ for $l=0,\ldots,k$. Thus, the cost of
an optimal solution, $X^{*},Y^{*}\in\Phi$ to Rec SP in $G$ is equal to
$\min_{0\leq l\leq k}\boldsymbol{c}^{*}_{G_{\sigma}}[l]$.

Let us analyze the running time of Algorithm 3. The binary decomposition tree
$\mathcal{T}$ of $G$, line 3, can be constructed in $O(|A|)$ time [32]. The
initialization, lines 3–3, can be done in $O(|A|)$ time. The root of
$\mathcal{T}$ can be reached in $O(|A|)$ time, lines 3–3. Algorithms 1 and 2
require $O(k^{2})$ time. Hence, the running time of Algorithm 3 is
$O(|A|k^{2})$. Since the algorithm for $\Phi^{\mathrm{excl}}(X,k)$ is
symmetric, its running time is the same. Observe that Algorithms 4 and 5
require $O(k^{2})$ time. Thus, the running time of algorithm for
$\Phi^{\mathrm{sym}}(X,k)$ is $O(|A|k^{2})$. ∎

##  4 The Rec Rob SP problem under budgeted uncertainty

In this section, we consider the Rec Rob SP problem under budgeted
uncertainty. Adding budgets to the interval uncertainty representation makes
the problem more challenging. Of course, all the negative results for Rec SP
(see Section 3.1) remain valid for Rec Rob SP with budgeted uncertainty. In
particular, the problem is strongly NP-hard and not approximable in general
digraphs for all considered neighborhoods.

###  4.1 The Rec Rob SP problem under $\mathcal{U}(\Gamma^{c})$

We now show a compact mixed integer programming formulation for Rec Rob SP
under the scenario set $\mathcal{U}(\Gamma^{c})$. We will use the fact that
$\mathcal{U}(\Gamma^{c})$ is a special case of polyhedral uncertainty.

######  Theorem 9.

The Rec Rob SP under $\mathcal{U}(\Gamma^{c})$ in general digraph $G=(V,A)$,
$|A|=m$, with neighborhoods $\Phi^{\mathrm{incl}}(X,k)$,
$\Phi^{\mathrm{excl}}(X,k)$ and $\Phi^{\mathrm{sym}}(X,k)$, admits a compact
MIP formulation.

###### Proof.

The idea of the construction is similar to that in [5, Theorem 1] (see also
[18]), where a compact MIP formulation for a recoverable version of a single-
machine scheduling problem under uncertainty was proposed. Namely, it uses
Carathéodory’s theorem, which states that any point in a convex hull ${\rm
Conv}(P)$ of a set $P\subset\mathbb{R}^{n}$ can be expressed as a convex
combination of at most $n+1$ points in $P$. Then, using the minimax theorem
(see, e.g., [5] for details) allows us to express Rec Rob SP as follows:

$\min_{\underset{Y^{(1)},\ldots,Y^{(m+1)}\in\Phi(X,k)}{X\in\Phi}}\left(\sum_{e\in
X}C_{e}+\max_{S\in\mathcal{U}(\Gamma^{c})}\min_{i\in[m+1]}\sum_{e\in
Y^{(i)}}c_{e}^{S}\right).$ (35)

Fix $\boldsymbol{x}\in\chi(\Phi)$ and
$\boldsymbol{y}^{(i)}\in\chi(\Phi(X,k))$, $i\in[m+1]$. The inner problem

$\max_{S\in\mathcal{U}(\Gamma^{c})}\min_{i\in[m+1]}\sum_{e\in
Y^{(i)}}c_{e}^{S}$ (36)

can be modeled as follows:

$\displaystyle\max\;$ $\displaystyle t$ (37) $\displaystyle t\leq\sum_{e\in
A}\hat{c}_{e}y^{(i)}_{e}+\sum_{e\in A}y^{(i)}_{e}u_{e}$ $\displaystyle\forall
i\in[m+1],$ (38) $\displaystyle 0\leq u_{e}\leq\Delta_{e}$
$\displaystyle\forall e\in A,$ (39) $\displaystyle\sum_{e\in
A}u_{e}\leq\Gamma^{c}.$ (40)

Dualizing the inner problem, we get

$\displaystyle\min\;$ $\displaystyle\sum_{i\in[m+1]}\left(\sum_{e\in
A}\hat{c}_{e}y^{(i)}_{e}\right)\lambda_{i}+\sum_{e\in
A}\Delta_{e}\gamma_{e}+\Gamma^{c}\Theta$
$\displaystyle\sum_{i\in[m+1]}\lambda_{i}=1,$
$\displaystyle\gamma_{e}+\Theta\geq\sum_{i\in[m+1]}y^{(i)}_{e}\lambda_{i}$
$\displaystyle\forall e\in A,$ $\displaystyle\lambda_{i}\geq 0$
$\displaystyle\forall i\in[m+1],$ $\displaystyle\gamma_{e}\geq 0$
$\displaystyle\forall e\in A,$ $\displaystyle\Theta\geq 0.$

By the strong duality, Rec Rob SP under $\mathcal{U}(\Gamma^{c})$ can be
rewritten as

$\displaystyle\min\;$ $\displaystyle\sum_{i\in[m+1]}\left(\sum_{e\in
A}\hat{c}_{e}y^{(i)}_{e}\right)\lambda_{i}+\sum_{e\in
A}\Delta_{e}\gamma_{e}+\Gamma^{c}\Theta$ (41)
$\displaystyle\sum_{i\in[m+1]}\lambda_{i}=1,$ (42)
$\displaystyle\gamma_{e}+\Theta\geq\sum_{i\in[m+1]}y^{(i)}_{e}\lambda_{i}$
$\displaystyle\forall e\in A,$ (43) $\displaystyle\lambda_{i}\geq 0$
$\displaystyle\forall i\in[m+1],$ (44) $\displaystyle\gamma_{e}\geq 0$
$\displaystyle\forall e\in A,$ (45) $\displaystyle\Theta\geq 0,$ (46)
$\displaystyle\boldsymbol{y}^{(i)}\in\chi(\Phi(X,k))$ $\displaystyle\forall
i\in[m+1],$ (47) $\displaystyle\boldsymbol{x}\in\chi(\Phi).$ (48)

The constraints (47) can be replaced with one of (14)–(16), depending on the
neighborhood used. Finally, it suffices to linearize (41), (43), (47) and (48)
in the model (41)–(48) by using standard techniques. ∎

The following theorem establishes the parameterized complexity hardness of Rec
Rob SP, not only when parameterized by $k$ (see Theorem 2), but also by
$\Gamma^{c}$.

######  Theorem 10.

The decision version of Rec Rob SP under $\mathcal{U}(\Gamma^{c})$ with
$\Phi^{\mathrm{incl}}(X,k)$, parameterized by $k$ and $\Gamma^{c}$ is para-NP-
complete in general digraphs.

###### Proof.

The problem Rec Rob SP is in NP, since (35) shows that $X\in\Phi$ and
$Y^{(1)},\ldots,Y^{(m+1)}\in\Phi(X,k)$ is a certificate for proving if an
instance of Rec Rob SP is “yes” instance and computing the value of
$\sum_{e\in
X}C_{e}+\max_{S\in\mathcal{U}(\Gamma^{c})}\min_{i\in[m+1]}\sum_{e\in
Y^{(i)}}c_{e}^{S}$ can be done in polynomial time by solving the linear
programming model (37)–(40). Thus, Rec Rob SP is in para-NP. Since Rec Rob SP
is NP-hard for constant $k$ and $\Gamma^{c}$ ($k=\Gamma^{c}=1$) [30], it is
para-NP-hard. ∎

######  Corollary 3.

The problem Rec Rob SP under $\mathcal{U}(\Gamma^{c})$ with
$\Phi^{\mathrm{incl}}(X,k)$, parameterized by $k$ and $\Gamma^{c}$ is para-NP-
hard in general digraphs.

###  4.2 The Rec Rob SP problem under $\mathcal{U}(\Gamma^{d})$

Proposing compact mixed integer programming formulations for Rec Rob SP under
the scenario set $\mathcal{U}(\Gamma^{d})$ is an open problem, contrary to the
Rec Rob SP under $\mathcal{U}(\Gamma^{c})$, where such models exist (see
Theorem 9).

It was shown in [30, Theorem 5] that the Rec Rob SP problem with
$\Phi^{\mathrm{incl}}(X,k)$ under $\mathcal{U}(\Gamma^{d})$ is strongly NP-
hard and not approximable in general digraphs, even if the recovery parameter
$k=1$ and the budget $\Gamma^{d}=1$, by a reduction from $2$-V-DP for a
general digraph [15]. Likewise, in Section 3.1, we generalize this reduction
to show that Rec Rob SP is hard for a structure of digraphs simpler than
general digraphs.

######  Lemma 7.

There is a polynomial time reduction from the $K$-V-DP problem in a digraph
$G$ to the Rec Rob SP problem under $\mathcal{U}(\Gamma^{d})$ with
$\Phi^{\mathrm{incl}}(X,k)$, $k=\Gamma^{d}=1$, in a digraph $G+H$ with cost
$C_{e}=0$, $\hat{c}_{e}=0$ and $\Delta_{e}\in\\{0,1\\}$ for all arcs $e$ in
$G+H$, where $H$ is a simple path having $2K-1$ arcs. Moreover, an instance of
$K$-V-DP is positive iff the total cost of any optimal solution to the
corresponding instance of Rec Rob SP is zero.

###### Proof.

The proof is a generalization of the one given in [30, Theorem 5] to the case
of $K$ terminal pairs. Given an instance of $K$-V-DP in a digraph $G=(V,A)$,
the graph $G+H$ is the same as in the proof of Lemma 1 (see Figure 1) except
for the definition of the arc costs. Now the arcs $(s_{i},t_{i})$, $i\in[K]$,
have costs $C_{s_{i}t_{i}}=0$, $\hat{c}_{s_{i}t_{i}}=0$ and
$\Delta_{s_{i}t_{i}}=1$. The same costs are assigned to the arcs that only
belong to $G$. The arcs $(t_{i+1},s_{i})$, $i\in[K-1]$, have the costs
$C_{t_{i+1}s_{i}}=0$, $\hat{c}_{t_{i+1}s_{i}}=0$ and
$\Delta_{t_{i+1}s_{i}}=0$. Finally, set $k=1$ and $\Gamma^{d}=1$. Yet, we need
to show that an instance of $K$-V-DP is positive iff the total cost of any
optimal solution to the corresponding instance of Rec Rob SP is zero. The
proof is almost the same as in [30]. ∎

Lemma 7 and the strong NP-completeness of $K$-V-DP for $K=2$ in general
digraphs [15] yield the mentioned hardness results for Rec Rob SP presented in
[30] ($H$ is now a simple $3$-arc path). Moreover, the problem remains
strongly NP-complete in an acyclic planar digraph when the number of terminal
pairs $K$ is unbounded [31], which leads to a hardness results for Rec Rob SP
in digraphs with a simpler structure than general digraphs.

######  Theorem 11.

The Rec Rob SP problem under $\mathcal{U}(\Gamma^{d})$ with
$\Phi^{\mathrm{incl}}(X,k)$ in a digraph $G+H$ with cost $C_{e}=0$,
$\hat{c}_{e}=0$ and $\Delta_{e}\in\\{0,1\\}$ for all arcs $e$ in $G+H$ is
strongly NP-hard and not approximable unless P=NP, even if $k=\Gamma^{d}=1$,
$G$ is an acyclic planar digraph and $H$ is a simple path having $2K-1$ arcs
($K$ is the number of pairwise vertex-disjoint paths in $K$-V-DP, see Lemma
7).

From Theorem 11 we immediately get a parameterized complexity result, similar
to Corollary 3.

######  Theorem 12.

The Rec Rob SP problem in a digraph $G+H$ with $\Phi^{\mathrm{incl}}(X,k)$
under $\mathcal{U}(\Gamma^{d})$ parameterized by $k$ and $\Gamma^{c}$ is para-
NP-hard, even if $G$ is an acyclic planar digraph and $H$ is a simple path.

###### Proof.

Rec Rob SP is para-NP-hard, since it is NP-hard for constant $k$ and
$\Gamma^{c}$ ($k=\Gamma^{c}=1$, see Theorem 11). ∎

###  4.3 Approximation algorithms

In this section, we again study the Rec Rob SP problem in acyclic
multidigraphs. We have shown in Section 3 that this problem can be solved in
polynomial time for the interval uncertainty $\mathcal{U}$. We now use this
fact to provide several approximation algorithms for the problem under
scenario sets $\mathcal{U}(\Gamma^{c})$ and $\mathcal{U}(\Gamma^{d})$ whose
computational complexity status is unknown in acyclic multidigraphs. Let

$F(X)=\left(\sum_{e\in
X}C_{e}+\max_{S\in\mathbb{U}}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}^{S}\right),$

where $\mathbb{U}\in\\{\mathcal{U}(\Gamma^{c}),\mathcal{U}(\Gamma^{d})\\}$ and
$\Phi(X,k)$ is one of the neighborhoods (1)–(3). Fix scenario $S\in\mathbb{U}$
and consider the problem

$\textsc{Rec SP $(S)$}:\;\min_{X\in\Phi,Y\in\Phi(X,k)}\left(\sum_{e\in
X}C_{e}+\sum_{e\in Y}c_{e}^{S}\right).$

Let us recall the following two results originally given for the recoverable
robust spanning tree problem [20, Lemmas 6, 7]. Their proofs go almost
verbatim for Rec SP $(S)$.

######  Lemma 8.

Suppose that $\hat{c}_{e}\geq\alpha(\hat{c}_{e}+\Delta_{e})$ for each $e\in
A$, where $\alpha\in(0,1]$, and let $(\hat{X},\hat{Y})$ be an optimal solution
to Rec SP $(S)$ for $S=(\hat{c}_{e})_{e\in A}$. Then
$F(\hat{X})\leq\frac{1}{\alpha}F(X)$ for each $X\in\Phi$.

Let $D=\sum_{e\in A}\Delta_{e}>0$. Define scenario $S^{\prime}$ in which
$c_{e}^{S^{\prime}}=\min\\{\hat{c}_{e}+\Delta_{e},\hat{c}_{e}+\Gamma^{c}\frac{\Delta_{e}}{D}\\}$,
$e\in A$. It is easy to see that $S^{\prime}\in\mathcal{U}(\Gamma^{c})$, since
$\sum_{e\in A}(c_{e}^{S^{\prime}}-\hat{c}_{e})\leq\sum_{e\in
A}\Gamma^{c}\frac{\Delta_{e}}{D}=\Gamma^{c}$.

######  Lemma 9.

Assume that $\mathbb{U}=\mathcal{U}(\Gamma^{c})$ and let $(\hat{X},\hat{Y})$
be an optimal solution to Rec SP ($S^{\prime}$). Then, the following
implications are true:

  1. (a)

if $\Gamma^{c}\geq\beta D$ for $\beta\in(0,1]$, then $F(\hat{X})\leq\beta
F(X)$ for each $X\in\Phi$,

  2. (b)

if $\Gamma^{c}\leq\gamma F(\hat{X})$ for $\gamma\in[0,1)$, then
$F(\hat{X})\leq\frac{1}{1-\gamma}F(X)$ for each $X\in\Phi$.

Observe that Rec SP (S) can be solved in polynomial time in acyclic
multidigraphs, according to the results shown in Section 3 (it is equivalent
to Rec SP with $\overline{c}_{e}=c^{S}_{e}$, $e\in A$). The value of $F(X)$
for a given $X\in\Phi$ can be computed in polynomial time for the scenario set
$\mathcal{U}(\Gamma^{c})$ and the neighborhood $\Phi^{\mathrm{incl}}(X,k)$,
see [30], where the time-expanded network approach [1] was applied. The same
technique can be applied to computing the value of $F(X)$ for
$\mathcal{U}(\Gamma^{c})$ and the neighborhoods $\Phi^{\mathrm{excl}}(X,k)$
and $\Phi^{\mathrm{sym}}(X,k)$ in polynomial time in acyclic multidigraphs.
From this, it follows that one can verify the condition $(b)$ from Lemma 9 in
polynomial time. Therefore, Lemma 8 and Lemma 9 imply the following
approximation results, where $\alpha$, $\beta$ and $\gamma$ are the constants
from these lemmas:

######  Theorem 13.

The Rec Rob SP in acyclic multidigraphs, under $\mathcal{U}(\Gamma^{d})$, is
approximable within $\frac{1}{\alpha}$.

######  Theorem 14.

The Rec Rob SP in acyclic multidigraphs, under $\mathcal{U}(\Gamma^{c})$ , is
approximable within
$\min\\{\frac{1}{\alpha},\frac{1}{\beta},\frac{1}{1-\gamma}\\}$.

The approximation ratios from the above theorems depend on the cost structure
in the scenario set. For example, the condition
$\hat{c}_{e}\geq\alpha(\hat{c}_{e}+\Delta_{e})$ means that the maximum second
stage cost of $e$ can be at most $\frac{1}{\alpha}$ greater than its nominal
cost. It is unlikely that the value of $\alpha$ is very small as the maximum
increase in the costs is typically limited. Similar interpretation can be
provided for the conditions $(a)$ and $(b)$ in Lemma 9.

##  5 Conclusion

In this paper, we have discussed the recoverable robust shortest path problem
under various interval scenario sets and neighborhoods. The main results are
polynomial time algorithms for acyclic multidigraphs and the traditional
interval uncertainty. In addition, we have strengthened the known negative
complexity results for general digraphs and provided some new results for the
budgeted interval uncertainty. In particular, we have proposed a compact MIP
formulation for the continuous budgeted uncertainty and some approximation
algorithms for acyclic digraphs. There are still several open questions
regarding the considered problem. Perhaps the most interesting one is the
characterization of the complexity of the recoverable robust problem in
acyclic digraphs under budgeted uncertainty. The problem is known to be hard
only for general digraphs. A polynomial time algorithm may exist in general
acyclic digraphs or for some of their special cases (layered, series-parallel,
etc.). It is also interesting to provide a more detailed characterization of
the problem from the parameterized complexity point of view.

#### Acknowledgements

The authors were supported by the National Science Centre, Poland, grant
2022/45/B/HS4/00355.

## 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] D. Bertsimas and M. Sim.  Robust discrete optimization and network flows.  Mathematical Programming, 98:49–71, 2003.
  * [3] D. Bertsimas and M. Sim.  The price of robustness.  Operations research, 52:35–53, 2004.
  * [4] M. Bold and M. Goerigk.  Investigating the recoverable robust single machine scheduling problem under interval uncertainty.  Discrete Applied Mathematics, 313:99–114, 2022.
  * [5] M. Bold and M. Goerigk.  Recoverable Robust Single Machine Scheduling with Polyhedral Uncertainty.  Technical report, arXiv:2011.06284, 2022.
  * [6] C. Büsing.  Recoverable robustness in combinatorial optimization.  PhD thesis, Technical University of Berlin, Berlin, 2011.
  * [7] C. Büsing.  Recoverable robust shortest path problems.  Networks, 59:181–189, 2012.
  * [8] C. Büsing, S. Goderbauer, A. M. Koster, and M. Kutschka.  Formulations and algorithms for the recoverable $\gamma$-robust knapsack problem.  EURO Journal on Computational Optimization, 7:15–45, 2019.
  * [9] C. Büsing, A. M. Koster, and M. Kutschka.  Recoverable robust knapsacks: $\Gamma$-scenarios.  In Network Optimization, pages 583–588. Springer, 2011.
  * [10] A. Chassein and M. Goerigk.  On the recoverable robust traveling salesman problem.  Optimization Letters, 10:1479–1492, 2016.
  * [11] A. Chassein, M. Goerigk, A. Kasperski, and P. Zieliński.  On recoverable and two-stage robust selection problems with budgeted uncertainty.  European Journal of Operational Research, 265:423–436, 2018.
  * [12] O. Şeref, R. K. Ahuja, and J. B. Orlin.  Incremental network optimization: theory and algorithms.  Operations Research, 57:586–594, 2009.
  * [13] D. Fischer, T. A. Hartmann, S. Lendl, and G. J. Woeginger.  An investigation of the recoverable robust assignment problem.  In 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, pages 19:1–19:14, 2021.
  * [14] J. Flum and M. Grohe.  Parameterized Complexity Theory.  Springer-Verlag, 2006.
  * [15] S. Fortune, J. Hopcroft, and J. Wyllie.  The directed subgraph homeomorphism problem.  Theoretical Computer Science, 10:111–121, 1980.
  * [16] M. R. Garey and D. S. Johnson.  Computers and Intractability. A Guide to the Theory of NP-Completeness.  W. H. Freeman and Company, 1979.
  * [17] M. Goerigk, S. Lendl, and L. Wulf.  On the recoverable travling salesman problem.  Technical report, arXiv:2111.09691, 2021.
  * [18] M. Goerigk, S. Lendl, and L. Wulf.  On the complexity of robust multi-stage problems with discrete recourse.  Discrete Applied Mathematics, 343:355–370, 2024.
  * [19] R. Hassin.  Approximation Schemes for the Restricted Shortest Path Problem.  Mathematics of Operations Research, 17:36–42, 1992.
  * [20] M. Hradovich, A. Kasperski, and P. Zieliński.  Recoverable robust spanning tree problem under interval uncertainty representations.  Journal of Combinatorial Optimization, 34:554–573, 2017.
  * [21] M. Hradovich, A. Kasperski, and P. Zieliński.  The recoverable robust spanning tree problem with interval costs is polynomially solvable.  Optimization Letters, 11:17–30, 2017.
  * [22] M. Hradovich, A. Kasperski, and P. Zieliński.  Robust recoverable 0–1 optimization problems under polyhedral uncertainty.  European Journal of Operational Research, 278:136–148, 2019.
  * [23] T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto.  A parameterized view to the robust recoverable base problem of matroids under structural uncertainty.  Operations Research Letters, 50:370–375, 2022.
  * [24] A. Kasperski and P. Zieliński.  Robust recoverable and two-stage selection problems.  Discrete Applied Mathematics, 233:52–64, 2017.
  * [25] P. Kouvelis and G. Yu.  Robust Discrete Optimization and its Applications.  Kluwer Academic Publishers, 1997.
  * [26] T. Lachmann, S. Lendl, and G. J. Woeginger.  A linear time algorithm for the robust recoverable selection problem.  Discrete Applied Mathematics, 303:94–107, 2021.
  * [27] T. Lee and C. Kwon.  A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty.  4OR, 12:373–378, 2014.
  * [28] S. Lendl, B. Peis, and V. Timmermans.  Matroid bases with cardinality constraints on the intersection.  Mathematical Programming, marzec 2021.
  * [29] C. Liebchen, M. E. Lübbecke, R. H. Mö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.
  * [30] E. Nasrabadi and J. B. Orlin.  Robust optimization with incremental recourse.  CoRR, abs/1312.4075, 2013.
  * [31] G. Naves and A. Sebő.  Multiflow feasibility: An annotated tableau.  In W. Cook, L. Lovász, and J. Vygen, editors, Research Trends in Combinatorial Optimization, pages 261–283. Springer Berlin Heidelberg, 2009.
  * [32] J. Valdes, R. E. Tarjan, and E. L. Lawler.  The recognition of series parallel digraphs.  SIAM Journal on Computing, 11:298–313, 1982.
  * [33] B. Zeng and L. Zhao.  Solving two-stage robust optimization problems using a column and constraint generation method.  Operation Research Letters, 41:457–461, 2013.