# Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest
Paths

Matthias Bentert  Fedor V. Fomin  Petr A. Golovach

###### Abstract

We examine the possibility of approximating Maximum Vertex-Disjoint Shortest
Paths. In this problem, the input is an edge-weighted (directed or undirected)
$n$-vertex graph $G$ along with $k$ terminal pairs
$(s_{1},t_{1}),(s_{2},t_{2}),\ldots,(s_{k},t_{k})$. The task is to connect as
many terminal pairs as possible by pairwise vertex-disjoint paths such that
each path is a shortest path between the respective terminals. Our work is
anchored in the recent breakthrough by Lochet [SODA ’21], which demonstrates
the polynomial-time solvability of the problem for a fixed value of $k$.

Lochet’s result implies the existence of a polynomial-time $ck$-approximation
for Maximum Vertex-Disjoint Shortest Paths, where $c\leq 1$ is a constant.
(One can guess $\nicefrac{{1}}{{c}}$ terminal pairs to connect in
$k^{O(\nicefrac{{1}}{{c}})}$ time and then utilize Lochet’s algorithm to
compute the solution in $n^{f(\nicefrac{{1}}{{c}})}$ time.) Our first result
suggests that this approximation algorithm is, in a sense, the best we can
hope for. More precisely, assuming the gap-ETH, we exclude the existence of an
$o(k)$-approximations within $f(k)\cdot\operatorname{poly}(n)$ time for any
function $f$ that only depends on $k$.

Our second result demonstrates the infeasibility of achieving an approximation
ratio of $n^{\nicefrac{{1}}{{2}}-\varepsilon}$ in polynomial time, unless P
$=$ NP. It is not difficult to show that a greedy algorithm selecting a path
with the minimum number of arcs results in a
$\lceil\sqrt{\ell}\rceil$-approximation, where $\ell$ is the number of edges
in all the paths of an optimal solution. Since $\ell\leq n$, this underscores
the tightness of the $n^{\nicefrac{{1}}{{2}}-\varepsilon}$-inapproximability
bound.

Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths is
fixed-parameter tractable when parameterized by $\ell$ but does not admit a
polynomial kernel.

Our hardness results hold for undirected graphs with unit weights, while our
positive results extend to scenarios where the input graph is directed and
features arbitrary (non-negative) edge weights.

##  1 Introduction

We study a variant of the well-known Vertex-Disjoint Paths problem, where the
input comprises a (directed or undirected) graph $G$ and $k$ terminal pairs as
input. The task is to identify whether pairwise vertex-disjoint paths can
connect all terminals. Vertex-Disjoint Paths has long been established as NP-
complete [16] and has played a pivotal role in the graph-minor project by
Robertson and Seymour [23].

Eilam-Tzoreff [12] introduced a variant of Vertex-Disjoint Paths where all
paths in the solution must be _shortest_ paths between the respective
terminals. The parameterized complexity of this variant, known as Vertex-
Disjoint Shortest Paths, was recently resolved [2, 19]: The problem,
parameterized by $k$, is W[1]-hard and in XP for undirected graphs. On
directed graphs, the problem is NP-hard already for $k=2$ if zero-weight edges
are allowed. The problem is solvable in polynomial time for $k=2$ for strictly
positive edge weights [3]. It is NP-hard when $k$ is part of the input, and
the complexity for constant $k>2$ remains open.

An optimization variant of Vertex-Disjoint Shortest Paths, where not
necessarily all terminal pairs need to be connected, but at least $p$ of them,
is referred to as Maximum Vertex-Disjoint Shortest Paths.

> Maximum Vertex-Disjoint Shortest Paths
>  Input: A graph $G=(V,E)$, an edge-length function $w\colon
> E\rightarrow\mathds{Q}_{\geq 0}$, terminal pairs
> $(s_{1},t_{1}),(s_{2},t_{2}),\ldots,(s_{k},t_{k})$ where $s_{i}\neq t_{i}$
> for $i\in[k]$, and integers $p$ and $\ell$. Question: Is there a set
> $S\subseteq[k]$ with $|S|\geq p$ such that there is a collection
> ${\mathcal{C}=\\{P_{i}\\}_{i\in S}}$ of pairwise vertex-disjoint paths
> satisfying the following conditions: for each $i\in S$, path $P_{i}$ is a
> shortest path from $s_{i}$ to $t_{i}$ and the total amount of edges in all
> paths of $\mathcal{C}$ is at most $\ell$?

A few remarks are in order. In the literature concerning Vertex-Disjoint Paths
and its variants, it is common for paths in a solution to share a terminal.
However, in our context, terminal pairs may indeed share a terminal, but the
paths comprising a feasible solution must be vertex-disjoint, and this
constraint also applies to their endpoints.

Note that Vertex-Disjoint Shortest Paths is a special case of Maximum Vertex-
Disjoint Shortest Paths with $p=k$ and $\ell=n$. For the maximization version,
we are not given $p$ as input but are instead asked to find a set $S$ that is
as large as possible. Slightly abusing notation, we do not distinguish between
these two variants and refer to both as Maximum Vertex-Disjoint Shortest
Paths.

In the definition of Maximum Vertex-Disjoint Shortest Paths, we also
incorporate the upper bound $\ell$ on the number of edges in a solution. This
parameter $\ell$ proves to be very useful for approximation and parameterized
algorithms. While parameterization by $k$ yields strong hardness bounds (both
in parameterized complexity and approximation), another natural
parameterization would be the sum of path lengths. If we confine all edge
weights to be positive integers, then $\ell$ serves as a lower bound for the
sum of path lengths. Since our hardness results apply to unweighted graphs,
studying $\ell$ instead of the sum of path lengths does not weaken the
negative results.

For the parameterized complexity of Maximum Vertex-Disjoint Shortest Paths, we
note that the results for Vertex-Disjoint Shortest Paths [2, 19] for the
parameterization by $k$ directly translate for Maximum Vertex-Disjoint
Shortest Paths parameterized by $p$. The problem is W[1]-hard as a
generalization of Vertex-Disjoint Shortest Paths, and to obtain an XP
algorithm, it is sufficient to observe that in $n^{O(p)}$ time we can guess a
set $S\subseteq[k]$ of size $p$ and apply the XP algorithm for Vertex-Disjoint
Shortest Paths for the selected set of terminal pairs.

In terms of approximations, we are not aware of any studies of Maximum Vertex-
Disjoint Shortest Paths. For Maximum Vertex-Disjoint Paths, where the task is
to connect the maximum number of terminal pair by disjoint but not necessarily
shortest paths, there is a known $O(\sqrt{n})$-approximation [18] and the best
known lower bounds are $2^{\Omega(\sqrt{\log(n)})}$ and
$n^{\Omega(\nicefrac{{1}}{{(\log\log n)^{2}}})}$, where the former lower bound
holds even if the input graph is an unweighted planar graph and the latter
lower bound holds even if the input graph is an unweighted grid graph [8, 9].
The best known approximation algorithms for these two special cases are
$\tilde{O}(n^{\nicefrac{{9}}{{19}}})$ and
$\tilde{O}(n^{\nicefrac{{1}}{{4}}})$, respectively.

When requiring the solution paths to be edge-disjoint rather than vertex-
disjoint, there have been some studies on relaxing the notion so that each
edge appears in at most $c>1$ of the solution paths. The integer $c$ is called
the congestion and the currently best known approximation algorithm achieves a
$\operatorname{poly}(\log n)$-approximation with $c=2$ [7].

Our results. We show that computing a
$n^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximations is NP-hard for any
$\varepsilon>0$ (Theorem 2). For FPT-approximation, we show in Theorem 1 that
any $k^{o(1)}$-approximation in ${f(k)\cdot\operatorname{poly}(n)}$ time
implies FPT $=$ W[1] and that one cannot $o(k)$-approximate Maximum Vertex-
Disjoint Shortest Paths in ${f(k)\cdot\operatorname{poly}(n)}$ time unless the
gap-ETH fails. We complement the first lower bound by developing a
$\lceil\sqrt{\ell}\rceil$-approximation in Theorem 3. In Theorems 4 and 5, we
show that Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable
when parameterized by $\ell$, but it does not admit a polynomial kernel. We
mention that all of our hardness results hold for undirected graphs with unit
weights and all of our positive results hold even for directed and edge-
weighted input graphs. Our results are summarized in Table 1.

Table 1: Overview over results. New results are bold. All hardness results hold for unweighted and undirected graphs, while all new algorithmic results hold even for directed graphs with arbitrary non-negative edge weights. | Exact | Approximation
---|---|---
no parameter | NP-complete | no $\mathbf{n^{\nicefrac{{1}}{{2}}-\varepsilon}}$-approximation in $\text{poly}(n)$ time
$k$ | XP and W[1]-hard | no $\mathbf{o(k)}$-approximation in $\mathbf{f(k)\cdot\text{poly}(n)}$ time
$\ell$ |  FPT and no poly kernel |  $\mathbf{\lceil\sqrt{\ell}\rceil}$-approximation

The remainder of this work is organized as follows. We start in Section 2 by
introducing concepts and notation used throughout the paper. In Section 3, we
present our results on approximation algorithms and lower bounds for Maximum
Vertex-Disjoint Shortest Paths. Section 4 is devoted to the parameterized
complexity of Maximum Vertex-Disjoint Shortest Paths with respect to $\ell$,
that is, we show fixed-parameter tractability and exclude polynomial kernels.
We conclude with an open problem in Section 5.

##  2 Preliminaries

For a positive integer $x$, we denote by $[x]=\\{1,2,\dots,x\\}$ the set of
all positive integers at most $x$. We denote by $G=(V,E)$ a graph and by $n$
and $m$ the number of vertices and edges in $G$, respectively. The graph $G$
is said to be  _$k$ -partite_ if $V$ can be partitioned into $k$ disjoint sets
$V_{1},V_{2},\ldots,V_{k}$ such that each set $V_{i}$ induces an independent
set, that is, there is no edge $\\{u,v\\}\in E$ with $\\{u,v\\}\subseteq
V_{i}$ for some $i\in[k]$. The _degree_ of a vertex $v$ is the number of edges
in $E$ that contain $v$ as an endpoint and the _maximum degree_ of a graph is
highest degree of any vertex in the graph.

A _path_ in a graph $G$ is a sequence $(v_{0},v_{1},\dots,v_{\ell})$ of
distinct vertices such that each pair $(v_{i-1},v_{i})$ is connected by an
edge in $G$. The length of a path is the sum of its edge lengths or simply the
number $\ell$ of edges if the graph is unweighted. For two vertices $v,w$, we
denote the length of a shortest $v$-$w$-path in $G$ by
$\operatorname{dist}_{G}(v,w)$ or $\operatorname{dist}(v,w)$ if the graph $G$
is clear from the context. The first and last vertex $v_{0}$ and $v_{\ell}$
are called the _ends_ of $P$. We also say that $P$ is a path _from_ $v_{0}$
_to_ $v_{\ell}$ or a $v_{0}$-$v_{\ell}$-path.

We assume the reader to be familiar with the big-O notation and basic concepts
in computational complexity like NP-completeness and reductions. We refer to
the textbook by Garey and Johnson [14] for an introduction. Throughout this
paper, we reduce from 3-Sat, Clique, and Multicolored Clique, three of the
most fundamental problems in theoretical computer science. We state their
definitions for the sake of completeness.

> 3-Sat
>  Input: A Boolean formula $\phi$ in conjunctive normal form where each
> clause contains at most three literals. Question: Is $\phi$ satisfiable?

> Clique
>  Input: An undirected graph $G$ and an integer $k$. Question: Is there a
> clique of size $k$ in $G$, that is, a set of $k$ vertices that are pairwise
> neighbors?

> Multicolored Clique
>  Input: An undirected $x$-partite graph $G$ and an integer $k\leq x$.
> Question: Is there a clique of size $k$ in $G$?

It is more common to state Multicolored Clique for $x=k$ and, in this case,
the partitions of the input graph are often modelled as colors and a clique is
called multicolored as it contains exactly one vertex from each color class.
However, it is convenient for us to allow $k\leq x$ and we call a clique in
this context _multicolored_ if it contains at most one vertex from each color
class.

For a detailed introduction to parameterized complexity and kernelization, we
refer the reader to the text books by Cygan et al. [10] and Fomin et al. [13].
A _parameterized problem_ $P$ is a language containing pairs $(I,\rho)$ where
$I$ is an instance of an (unparameterized) problem and $\rho$ is an integer
called the _parameter_. In this paper, the parameter will usually be either
the number $k$ of terminal pairs or the upper bound $\ell$ on the number of
edges in a solution. A parameterized problem $P$ is _fixed-parameter
tractable_ if there exists an algorithm solving any instance $(I,\rho)$ of $P$
in $f(\rho)\cdot\operatorname{poly}(|I|)$ time, where $f$ is some computable
function only depending on $\rho$. The class _XP_ contains all parameterized
problems which can be solved in $|I|^{f(\rho)}$ time, that is, in polynomial
time if $\rho$ is constant. A parameterized problem is said to admit a
_polynomial kernel_ , if there is a polynomial-time algorithm that given an
instance $(I,\rho)$ computes an equivalent instance
$(I^{\prime},\rho^{\prime})$ (called the _kernel_) such that
$|I^{\prime}|+\rho^{\prime}$ are upper-bounded by a polynomial in $\rho$. It
is known that any parameterized problem admitting a polynomial kernel is
fixed-parameter tractable and each fixed-parameter tractable problem is
contained in XP.

An optimization problem does not ask whether a given instance belongs to a
language or not. Instead, it asks for an optimal feasible solution (usually
some kind of maximum or minimum). In the case of Maximum Vertex-Disjoint
Shortest Paths, the task is to compute a maximum size subset $S$ of $[k]$ such
that there exist vertex-disjoint shortest paths $P_{i}$ for all $i\in S$. An
$\alpha$-approximation algorithm for a maximization problem is a polynomial-
time algorithm that for any input returns a solution of size at least
$\nicefrac{{\operatorname{OPT}}}{{\alpha}}$ where $\operatorname{OPT}$ is the
size of an optimal solution $S^{*}$. A parameterized $\alpha$-approximation
algorithm also returns a solution of size at least
$\nicefrac{{\operatorname{OPT}}}{{\alpha}}$, but its running time is allowed
to be $f(\rho)\cdot\operatorname{poly}(n)$, where $\rho$ is the parameter and
$f$ is some computable function only depending on $\rho$. In this work, we
always consider (unparameterized) approximation algorithms unless we
specifically state a parameterized running time.

To exclude an $\alpha$-approximation for an optimization problem, one can use
the framework of _approximation-preserving reductions_. A strict
approximation-preserving reduction is a pair of algorithms—called the
_reduction algorithm_ and the _solution-lifting algorithm_ —that both run in
polynomial time and satisfy the following. The reduction algorithm takes as
input an instance $I$ of a problem $L$ and produces an instance $I^{\prime}$
of a problem $L^{\prime}$. The solution-lifting algorithm takes any solution
$S$ of $I^{\prime}$ and transforms it into a solution $S^{*}$ of $I$ such that
if $S$ is an $\alpha$-approximation for $I^{\prime}$ for some $\alpha\geq 1$,
then $S^{*}$ is an $\alpha$-approximation for $I$. If a strict approximation-
preserving reduction from $L$ to $L^{\prime}$ exists and $L$ is hard to
approximate within some value $\beta$, then $L$ is also hard to approximate
within $\beta$.

The _exponential time hypothesis (ETH)_ introduced by Impagliazzo and Paturi
[15] states that there is some $\varepsilon>0$ such that each
(unparameterized) algorithm solving 3-Sat takes at least $2^{\varepsilon
n+o(n)}$ time, where $n$ is the number of variables in the input instance. A
stronger conjecture called the _gap-ETH_ was independently introduced by Dinur
[11] and Manurangsi and Raghavendra [21]. It states that there exist
$\varepsilon,\delta>0$ such that any $(1+\varepsilon)$-approximation algorithm
for Max 3-Sat111Max 3-Sat is a generalization of 3-Sat where the question is
not whether the input formula is satisfiable but rather how many clauses can
be satisfied simultaneously. takes at least $2^{\delta n+o(n)}$ time.

##  3 Approximation

In this section, we show that Maximum Vertex-Disjoint Shortest Paths cannot be
$o(k)$-approximated in $f{(k)\cdot\operatorname{poly}(n)}$ time and not
$n^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximated in polynomial time. We
complement the latter result by developing a
$\lceil\sqrt{\ell}\rceil$-approximation algorithm that runs in polynomial
time. We start with a reduction based on a previous reduction by Bentert et
al. [2]. Note however, that the known reduction is not approximation-
preserving. Moreover, our result is tight in the sense that a
$k$-approximation can be computed in polynomial time by simply connecting any
terminal pair by a shortest path. A $ck$-approximation for any constant $c\leq
1$ can also be computed in polynomial time by guessing $\frac{1}{c}$ terminal
pairs to connect and then using the XP-time algorithm by Bentert et al. [2] to
find a solution. Note that since $c$ is a constant, the XP-time algorithm for
$\frac{1}{c}$ terminal pairs runs in polynomial time.

######  Theorem 1.

Unless FPT$=$W[1], Maximum Vertex-Disjoint Shortest Paths cannot be
$k^{o(1)}$-approximated in $f(k)\cdot\operatorname{poly}(n)$ time, and
assuming the gap-ETH, it cannot be $o(k)$-approximated in
$f{(k)\cdot\operatorname{poly}(n)}$ time. All of these results hold even for
subcubic graphs with terminals of degree at most two.

###### Proof.

We present a strict approximation-preserving reduction from Multicolored
Clique to Maximum Vertex-Disjoint Shortest Paths such that the maximum degree
is three and each terminal vertex has degree two. Moreover, the maximum number
$\operatorname{OPT}$ of vertex-disjoint shortest paths between terminal pairs
will be equal to the largest clique in the original instance. The theorem then
follows from the fact that a $f(k)\cdot\operatorname{poly}(n)$-time
$k^{o(1)}$-approximation for Clique would imply that FPT$=$W[1] [6, 17], and a
$f(k)\cdot\operatorname{poly}(n)$-time $o(k)$-approximation for Clique refutes
the gap-ETH [5], and the fact that the textbook reduction from Clique to
Multicolored Clique only increases the number of vertices by a quadratic
factor and does not change the size of a largest clique in the graph.

The reduction is depicted in Figure 1 and works as follows.

$1,1$$2,1$$3,1$$4,1$$1,2$$2,2$$3,2$$4,2$$1,3$$2,3$$3,3$$4,3$$1,4$$2,4$$3,4$$4,4$$s_{1}$$t_{1}$$s_{2}$$t_{2}$$s_{3}$$t_{3}$$s_{4}$$t_{4}$$s_{1}^{1}$$s_{1}^{4}$$t_{1}^{1}$$t_{1}^{4}$$u^{1,2}_{1,1}$$v^{1,2}_{1,1}$$u^{2,3}_{3,1}$$x^{1,3}_{4,4}$
Figure 1:  An illustration of the reduction from Multicolored Clique to
Maximum Vertex-Disjoint Shortest Paths.
_Left side:_ Example instance for Multicolored Clique with $k=4$ colors and
$n=4$ vertices per color. A multicolored clique is highlighted (by thick
edges).
_Right side:_ The constructed instance with the four shortest paths
corresponding to the vertices of the clique highlighted. Note that these paths
are pairwise disjoint. The dotted edges (incident to $s_{i}$ and $t_{i}$
vertices) indicate binary trees (where all leaves have distance
$\lceil\log(\nu)\rceil$ from the root). Red edges indicate paths of length
$2\nu$ and blue edges indicate paths of length $2$.

Let $G=(V,E)$ be a $k$-partite graph (or equivalently a graph colored with $k$
colors where all vertices of any color form an independent set) with $\nu$
vertices of each color. Let
$V_{i}=\\{v^{i}_{1},v^{i}_{2},\ldots,v^{i}_{\nu}\\}$ be the set of vertices of
color $i\in[k]$ in $G$. We start with a terminal pair $(s_{i},t_{i})$ for each
color $i$ and a pair of vertices $(s_{i}^{j},t_{i}^{j})$ for each vertex
$v^{i}_{j}\in V_{i}$. Next for each color $i$, we add a binary tree of height
$\lceil\log(\nu)\rceil$ with root $s_{i}$ and leaves $s_{i}^{j}$ for
$v_{j}^{i}\in V_{i}$. Analogously, we add a binary tree of the same height
with root $t_{i}$ and leaves $t^{i}_{j}$. Next, we add a crossing gadget for
each pair of vertices $(v_{j}^{i},v_{b}^{a})$ with $i<a$. If
$\\{v_{j}^{i},v_{b}^{a}\\}\notin E$, then the gadget consists of four vertices
$u_{j,b}^{i,a},v_{j,b}^{i,a},x_{j,b}^{i,a}$, and $y_{j,b}^{i,a}$ and edges
$\\{u_{j,b}^{i,a},v_{j,b}^{i,a}\\}$ and $\\{x_{j,b}^{i,a},y_{j,b}^{i,a}\\}$.
If $\\{v_{j}^{i},v_{b}^{a}\\}\in E$, then the gadget consists of only two
vertices $u_{j,b}^{i,a}$ and $v_{j,b}^{i,a}$ and the edge
$\\{u_{j,b}^{i,a},v_{j,b}^{i,a}\\}$. For the sake of notational convenience,
we will in the latter case also denote $u_{j,b}^{i,a}$ by $x_{j,b}^{i,a}$ and
$v_{j,b}^{i,a}$ by $y_{j,b}^{i,a}$. To complete the construction, we connect
the different gadgets as follows. First, we connect via paths of length two
$v_{j,b}^{i,a}$ and $u_{j,b+1}^{i,a}$ for all $b<\nu$ and $y_{j,b}^{i,a}$ and
$x_{j-1,b}^{i,a}$ for all $j>1$. Second, we connect via paths of length two
the vertices $v_{j,\nu}^{i,a}$ to $u_{j,1}^{i,a+1}$ for all $j\in[\nu]$ and
all $a<k$ and $y^{i,a}_{1,b}$ to $x^{i+1,a}_{\nu,b}$ for all $b\in[\nu]$ and
all $i<a-1$. Third, we connect also via paths of length two $y^{i,i+1}_{1,b}$
to $u^{i+1,i+2}_{b,1}$ for all $i<k-1$ and all $b\in[\nu]$. Next, we connect
via paths of length $2\nu$ each vertex $s_{i}^{j}$ to $x^{1,i}_{\nu,j}$ for
each $i>1$ and $j\in[\nu]$. Similarly, $v^{i,k}_{j,\nu}$ is connected to
$t_{i}^{j}$ via paths of length $2\nu$. Finally, we connect $s^{1}_{j}$ with
$u^{1,2}_{j,1}$ for all $j\in[\nu]$ and $y^{k-2,k-1}_{1,j}$ with $t^{k}_{j}$
for all $j\in[\nu]$. This concludes the construction.

We next prove that all shortest $s_{i}$-$t_{i}$-paths are of the form

$\displaystyle
s_{i}-s_{i}^{j}-x^{1,i}_{\nu,j}-y^{i-1,i}_{1,j}-u^{i,i+1}_{j,1}-v^{i,k}_{j,\nu}-t^{j}_{i}-t_{i}$
(1)

for some $j\in[\nu]$ and where the $s_{1}$-$t_{1}$-paths go directly from
$s_{i}^{j}$ to $u^{1,2}_{j,1}$ and the $s_{k}$-$t_{k}$-paths go directly from
$y^{k-1,k}_{1,j}$ to $t_{j}^{i}$. We say that the respective path is the _$j$
th canonical path_ for color $i$.

To show the above claim, first note that the distance from $s_{i}$ to any
vertex $s^{j}_{i}$ is the same value ${x=\lceil\nu\rceil}$ for all pairs of
indices $i$ and $j$. Moreover, the same holds for $t_{i}$ and $t_{i,j}$, each
$s_{i}$-$t_{i}$-path contains at least one vertex $s_{i}^{j}$ and one vertex
$s_{i}^{j^{\prime}}$ for some $j,j^{\prime}\in[\nu]$, and all paths of the
form in Equation 1 are of length $y=2x+4\nu+3(k-1)\nu-2$. We first show that
each path $s_{i}$-$t_{i}$-path of length at most $y$ contains an edge of the
form $y^{i,i+1}_{1,b}$ to $u^{i+1,i+2}_{b,1}$. Consider the graph where all of
these edges are removed. Note that due to the grid-like structure, the
distance between $s_{i}$ and $x^{i^{\prime},a}_{j,b}$ for any values
$i^{\prime}\leq i\leq a,j$, and $b$ is at least
$x+2\nu+3(i^{\prime}-1)\nu+3(\nu-j)$ if $i=a$ and at least
$x+2\nu+3(i^{\prime}-1)\nu+3(a-i)\nu+3(\nu-j)+3b$ if $i<a$.222We mention that
there are some pairs of vertices $x^{i_{1},a_{1}}_{j_{1},b_{1}}$ and
$x^{i_{2},a_{2}}_{j_{2},b_{2}}$, where the distance between the two is less
than $3(|i_{1}-i_{2}|+|a_{1}-a_{2}|)\nu+3(|j_{1}-j_{2}|+|b_{1}-b_{2}|)$. An
example is the pair $(x^{1,2}_{1,1}=u^{1,2}_{1,1},x^{1,2}_{2,2})$ in Figure 1
with a distance of $4$. However, in all examples it holds that $i_{1}\nu-
j_{1}\neq i_{2}\nu-j_{2}$ and $a_{1}\nu+b_{1}\neq a_{2}\nu+b_{2}$ such that
the left side is either smaller in both inequalities or larger in both
inequalities. Hence, these pairs cannot be used as shortcuts as they move
“down and left” instead of towards “down and right” in Figure 1. Hence, all
shortest $s_{i}$-$t_{i}$-paths use an edge of the form $y^{i,i+1}_{1,b}$ to
$u^{i+1,i+2}_{b,1}$ and the shortest path from $s_{i}^{j}$ to some vertex
$y^{i,i+1}_{1,b}$ is to the vertex $y^{i,i+1}_{1,j}$. Note that the other
endpoint of the specified edge is $u^{i,i+1}_{j,1}$ and the shortest path to
$t_{i}$ now goes via $t_{i}^{j}$ for analogous reasons. Thus, all shortest
$s_{i}$-$t_{i}$-paths have the form (1).

We next prove that any set of $p$ disjoint shortest paths between terminal
pairs $(s_{i},t_{i})$ in the constructed graph has a one-to-one correspondence
to a multicolored clique of size $p$ for any $p$. For the first direction,
assume that there is a set $P$ of disjoint shortest paths between $p$ terminal
pairs. Let $S\subseteq[k]$ be the set of indices such that the paths in $P$
connect $s_{i}$ and $t_{i}$ for each $i\in S$. Moreover, let $j_{i}$ be the
index such that the shortest $s_{i}$-$t_{i}$-path in $P$ is the $j_{i}$th
canonical path for $i$ for each $i\in S$. Now consider the set
$K=\\{v_{j_{i}}^{i}\mid i\in S\\}$ of vertices in $G$. Clearly $K$ contains at
most one vertex of each color and is of size $p$ as $S$ is of size $p$. It
remains to show that $K$ induces a clique in $G$. To this end, consider any
two vertices $v_{j_{i}}^{i},v_{j_{i^{\prime}}}^{i^{\prime}}\in K$. We assume
without loss of generality that $i<i^{\prime}$. By assumption, the $j_{i}$th
canonical path for $i$ and the $j_{i^{\prime}}$th canonical path for
$i^{\prime}$ are disjoint. This implies that
$u^{i,i^{\prime}}_{j_{i},j_{i^{\prime}}}\neq
x^{i,i^{\prime}}_{j_{i},j_{i^{\prime}}}$ as the $j_{i}$th canonical path for
$i$ contains the former and the $j_{i^{\prime}}$th canonical path for
$i^{\prime}$ contains the latter. By construction, this means that
$\\{v_{j_{i}}^{i},v_{j_{i^{\prime}}}^{i^{\prime}}\\}\in E$. Since the two
vertices were chosen arbitrarily, it follows that all vertices in $K$ are
pairwise adjacent, that is, $K$ induces a multicolored clique of size $p$.

For the other direction assume that there is a multicolored clique
$C=\\{v_{j_{1}}^{i_{1}},v_{j_{2}}^{i_{2}},\ldots,v_{j_{p}}^{i_{p}}\\}$ of size
$p$ in $G$. We will show that the $j_{q}$th canonical path for $i_{q}$ is
vertex disjoint from the $j_{r}$th canonical path for $i_{r}$ for all $q\neq
r\in[p]$. Let $q,r$ be two arbitrary distinct indices in $[p]$ and let without
loss of generality be $q<r$. Note that the two mentioned paths can only
overlap in vertices
$u^{i_{q},i_{r}}_{j_{q},j_{r}},v^{i_{q},i_{r}}_{j_{q},j_{r}},c^{i_{q},i_{r}}_{j_{q},j_{r}},$
or $y^{i_{q},i_{r}}_{j_{q},j_{r}}$ and that the $j_{q}$th canonical path for
$i_{q}$ only contains vertices $u^{i_{q},i_{r}}_{j_{q},j_{r}}$ and
$v^{i_{q},i_{r}}_{j_{q},j_{r}}$ and the $j_{r}$th canonical path for $i_{r}$
only contains $x^{i_{q},i_{r}}_{j_{q},j_{r}}$ and
$y^{i_{q},i_{r}}_{j_{q},j_{r}}$. Moreover, since by assumption
$v_{j_{q}}^{i_{q}}$ and $v_{j_{r}}^{i_{r}}$ are adjacent, it holds by
construction that
$u^{i_{q},i_{r}}_{j_{q},j_{r}},v^{i_{q},i_{r}}_{j_{q},j_{r}},x^{i_{q},i_{r}}_{j_{q},j_{r}}$,
and $y^{i_{q},i_{r}}_{j_{q},j_{r}}$ are four distinct vertices. Thus, we found
vertex disjoint paths between $p$ distinct terminal pairs. This concludes the
proof of correctness.

To finish the proof, observe that the constructed instance has maximum degree
three, all terminal vertices are roots of binary trees and therefore have
degree two, and that the construction can be computed in polynomial time. ∎

We mention in passing that in graphs of maximum degree three with terminal
vertices of degree at most two, two paths are vertex disjoint if and only if
they are edge disjoint. Hence, Theorem 1 also holds for the edge-disjoint
version of Maximum Vertex-Disjoint Shortest Paths.

We continue with an unparameterized lower bound by establishing that computing
a $n^{\frac{1}{2}-\varepsilon}$-approximation is NP-hard. To the best of our
knowledge, this is the first unparameterized approximation lower bound for
Maximum Vertex-Disjoint Shortest Paths and no similar bound is known for
Disjoint Paths. We mention that the reduction is quite similar to the
reduction in the proof for Theorem 1.

######  Theorem 2.

Computing a $n^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximation for any
$\varepsilon>0$ for Maximum Vertex-Disjoint Shortest Paths is NP-hard.

###### Proof.

It is known that computing a $n^{1-\varepsilon}$-approximation for Clique is
NP-hard [24]. We present an approximation-preserving reduction from Clique to
Maximum Vertex-Disjoint Shortest Paths based on Theorem 1. We use basically
the same reduction as in Theorem 1 but we start from an instance of Clique and
have a separate terminal pair for each vertex in the graph. Moreover, we do
not require the binary trees pending from the terminal vertices (the terminal
vertices now have degree one instead) and neither do we require long induced
paths (red edges in Figure 1). These are instead paths with one internal
vertex. An illustration of the modified reduction is given in Figure 2.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$s_{1}$$t_{1}$$s_{2}$$t_{2}$$s_{3}$$t_{3}$$s_{4}$$t_{4}$$s_{5}$$t_{5}$$s_{6}$$t_{6}$
Figure 2:  An illustration of the reduction from Clique to Maximum Vertex-
Disjoint Shortest Paths.
_Left side:_ Example instance for Clique with a highlighted solution (by thick
edges).
_Right side:_ The constructed instance with the four shortest paths
corresponding to the solution on the left side highlighted. Note that each
shortest $s_{i}$-$t_{i}$-path uses exactly two of the diagonal edges.

Note that the number of vertices and edges in the graph is at most $3N^{2}$,
where $N$ is the number of vertices in the instance of Clique. Moreover, for
each terminal pair $(s_{i},t_{i})$, there is exactly one shortest
$s_{i}$-$t_{i}$-path (the path that moves horizontally in Figure 2 until it
reaches the main diagonal, then uses exactly two edges on the diagonal, and
finally moves vertically to $t_{i}$).

We next prove that for any $p$, there is a one-to-one correspondence between a
set of $p$ disjoint shortest paths between terminal pairs $(s_{i},t_{i})$ in
the constructed graph and a clique of size $p$ in the input graph. For the
first direction, assume that there is a set $P$ of disjoint shortest paths
between $p$ terminal pairs. Let $S\subseteq[k]$ be the set of indices such
that the paths in $P$ connect $s_{i}$ and $t_{i}$ for each $i\in S$. Now
consider the set $K=\\{v_{i}\mid i\in S\\}$ of vertices in $G$. Clearly $K$
contains $p$ vertices. It remains to show that $K$ induces a clique in $G$. To
this end, consider any two vertices $v_{i},v_{j}\in K$. We assume without loss
of generality that $i<j$. By assumption, the unique shortest
$s_{i}$-$t_{i}$-path and the unique shortest $s_{j}$-$t_{j}$-path are vertex-
disjoint. By the description of the shortest paths between terminal pairs and
the fact that $s_{i}$ is higher than $s_{j}$ and $t_{i}$ is to the left of
$t_{j}$, it holds that the two considered paths both visit the region that is
to the right of $s_{j}$ and above $t_{i}$. This implies that two edges must be
crossing at this position, that is, there are four vertices in the described
region and not only two. By construction, this means that
$\\{v_{i},v_{j}\\}\in E$. Since the two vertices were chosen arbitrarily, it
follows that all vertices in $K$ are pairwise adjacent, that is, $K$ induces a
clique of size $p$ in the input graph.

For the other direction assume that there is a clique
$C=\\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{p}}\\}$ of size $p$ in the input graph.
We will show that the unique shortest $s_{i_{q}}$-$t_{i_{q}}$-path is vertex-
disjoint from the unique shortest $s_{i_{r}}$-$t_{i_{r}}$-path for all $q\neq
r\in[p]$. Let $q,r$ be two arbitrary distinct indices in $[p]$ and let without
loss of generality be $q<r$. Note that the two mentioned paths can only
overlap in the region that is to the right of $s_{i_{r}}$ and above
$t_{i_{q}}$. Moreover, since by assumption $v_{i_{q}}$ and $v_{i_{r}}$ are
adjacent, it holds by construction that there are four distinct vertices in
the described region and the two described paths are indeed vertex-disjoint.
Thus, we found vertex disjoint paths between $p$ distinct terminal pairs.

We conclude by analyzing the approximation ratio. Note that we technically did
not prove a strict reduction for the factor $n^{1-\varepsilon}$ as the number
of vertices in the two instances are not the same. Still, any
$n^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximation for Maximum Vertex-
Disjoint Shortest Paths corresponds to a
$(3N^{2})^{\nicefrac{{1}}{{2}}-\varepsilon}=N^{1-\varepsilon^{\prime}}$-approximation
for Clique for some $0<\varepsilon^{\prime}<2\varepsilon$ and therefore
computing a $n^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximation for Maximum
Vertex-Disjoint Shortest Paths is NP-hard. ∎

Note that the maximum degree of the constructed instance is again three and
all terminal vertices are of degree one. Thus, Theorem 2 also holds for the
edge disjoint version of Maximum Vertex-Disjoint Shortest Paths.

We next show that this result is tight, that is, we show how to compute a
$\sqrt{n}$-approximation for Maximum Vertex-Disjoint Shortest Paths in
polynomial time. We also show that the same algorithm achieves a
$\lceil\sqrt{\ell}\rceil$-approximation. Note that we can always assume that
$\ell<n$ as a set of vertex-disjoint paths is a forest and the number of edges
in a forest is less than its number of vertices. We mention that this
algorithm is basically identical to the best known (unparameterized)
approximation algorithm for Maximum Disjoint Paths [18].

######  Theorem 3.

There is a polynomial-time algorithm for Maximum Vertex-Disjoint Shortest
Paths on directed and weighted graphs that achieves an approximation factor of
$\min\\{\sqrt{n},\lceil\sqrt{\ell}\rceil\\}$.

###### Proof.

Let $\operatorname{OPT}$ be a maximum subset of terminal pairs that can be
connected by shortest pairwise vertex-disjoint paths and let $j$ be the index
of a terminal pair $(s_{j},t_{j})$ such that a shortest $(s_{j},t_{j})$-path
contains a minimum number of arcs. We can compute the index $j$ as well as a
shortest $s_{j}$-$t_{j}$-path with a minimum number of arcs by running a
folklore modification of Dijkstra’s algorithm from each terminal vertex
$s_{i}$.333The standard Dijkstra’s algorithm is modified by assigning to each
vertex a pair of labels: the distance from the terminal and the number of arcs
in the corresponding path; then the pairs of labels are compared
lexicographically. Let $\ell_{j}$ be the number of arcs in the found path. Our
algorithm iteratively picks the shortest $s_{j}$-$t_{j}$-path using $\ell_{j}$
arcs, removes all involved vertices from the graph, recomputes the distance
between all terminal pairs, removes all terminal pairs whose distance
increased, updates the index $j$, and recomputes $\ell_{j}$. For the analysis
of our algorithm, we assume that we know an optimal solution and pretend to
also remove a terminal pair $(s_{i},t_{i})$ if the minimum number $\ell_{i}$
of arcs in a shortest $s_{i}$-$t_{i}$-path increases. Moreover, we distinguish
whether $\ell_{j}+1\leq\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)$ or not.

While $\ell_{j}+1\leq\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)$, note that we
removed at most $\ell_{j}+1$ terminals pairs in $\operatorname{OPT}$. Hence,
if $\ell_{j}+1\leq\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)$ holds at every
stage, then we connected at least
$\nicefrac{{|\operatorname{OPT}|}}{{\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)}}$
terminal pairs, that is, we found a
$\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)$-approximation.

So assume that at some point $\ell_{j}>\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)$
and let $x$ be the number of terminal pairs that we already connected by
disjoint shortest paths. By the argument above, we have removed at most
$x\min(\sqrt{n},\lceil\sqrt{\ell}\rceil)$ terminal pairs from
$\operatorname{OPT}$ thus far. We now make a case distinction whether or not
$\sqrt{n}\leq\lceil\sqrt{\ell}\rceil$. If
$\ell_{j}+1>\lceil\sqrt{\ell}\rceil\geq\sqrt{n}$, then we note that all
remaining paths in $\operatorname{OPT}$ contain at least $\sqrt{n}$ vertices
each and since the paths are vertex-disjoint, there can be at most $\sqrt{n}$
paths left in $\operatorname{OPT}$. Hence, we can infer that
$|\operatorname{OPT}|\leq(x+1)\cdot\sqrt{n}$. Consequently, even though we
might remove all remaining terminal pairs in $\operatorname{OPT}$ by
connecting $s_{j}$ and $t_{j}$, this is still a $\sqrt{n}$-approximation (and
a $\lceil\sqrt{\ell}\rceil$-approximation as we assumed
$\lceil\sqrt{\ell}\rceil\geq\sqrt{n}$).

If $\ell_{j}+1>\sqrt{n}\geq\lceil\sqrt{\ell}\rceil$, then we note that all
remaining paths in $\operatorname{OPT}$ contain at least
$\ell_{j}>\lceil\sqrt{\ell}\rceil-1$ edges each. Moreover, since $\ell_{j}$
and $\lceil\sqrt{\ell}\rceil$ are integers, each path contains at least
$\lceil\sqrt{\ell}\rceil$ edges each. Since all paths in $\operatorname{OPT}$
contain by definition at most $\ell$ edges combined, the number of paths in
$\operatorname{OPT}$ is at most
$\nicefrac{{\ell}}{{\lceil\sqrt{\ell}\rceil}}\leq\lceil\sqrt{\ell}\rceil$.
Hence, we can infer in that case that
$|\operatorname{OPT}|\leq(x+1)\cdot\lceil\sqrt{\ell}\rceil$. Again, even if we
remove all remaining terminal pairs in $\operatorname{OPT}$ by connecting
$s_{j}$ and $t_{j}$, this is still a $\lceil\sqrt{\ell}\rceil$-approximation
(and a $\sqrt{n}$-approximation as we assumed
$\sqrt{n}\geq\lceil\sqrt{\ell}\rceil$). This concludes the proof. ∎

##  4 Exact Algorithms

In this section, we show that Maximum Vertex-Disjoint Shortest Paths is fixed-
parameter tractable when parameterized by $\ell$, but it does not admit a
polynomial kernel. The proof of our first theorem uses the _color-coding_
technique of Alon, Yuster, and Zwick [1]. Imagine we are searching for some
structure of size $k$ in a graph. The idea of color coding is to color the
vertices (or edges) of the input graph with a set of $k$ colors and then only
search for colorful solutions, that is, structures in which all vertices have
distinct colors. Of course, this might not yield an optimal solution, but by
trying enough different random colorings, one can often get a constant error
probability in $f(k)\cdot\operatorname{poly}(n)$ time. Using the following
result by Naor, Schulman, and Srinivasan [22], this can also be turned into a
deterministic algorithm showing that the problem is fixed-parameter tractable.
The result states that for any $n,k\geq 1$, one can construct an
$(n,k)$-perfect hash family of size $e^{k}k^{O(\log k)}\log(n)$ in
$e^{k}k^{O(\log k)}n\log(n)$ time. An $(n,k)$-perfect hash family
$\mathcal{F}$ is a family of functions from $[n]$ to $[k]$ such that for every
set $S\subseteq[n]$ with $|S|\leq k$, there exists a function
$f\in\mathcal{F}$ such that $f$ colors all vertices in $S$ with distinct
colors.

######  Theorem 4.

Maximum Vertex-Disjoint Shortest Paths on weighted and directed graphs can be
solved in $2^{O(\ell)}\operatorname{poly}(n)$ time.

###### Proof.

Let $(G,w,(s_{1},t_{1}),\dots,(s_{k},t_{k}),p,\ell)$ be an instance of Maximum
Vertex-Disjoint Shortest Paths. We assume that $p\leq\ell$ as we have a
trivial no-instance otherwise. Notice that the total number of vertices in a
(potential) solution with $p$ paths is at most $\ell+p$. We use the color-
coding technique of Alon, Yuster, and Zwick [1]. We color the vertices of $G$
uniformly at random using $p+\ell$ colors (the set of colors is $[\ell+p]$)
and observe that the probability that all the vertices in the paths in a
solution have distinct colors is at least
$\frac{(p+\ell)!}{(p+\ell)^{(p+\ell)}}\geq e^{-(p+\ell)}$. We say that a
solution to the considered instance is _colorful_ if distinct paths in the
solution have no vertices of the same color. Note that we do not require that
the vertices within a path in the solution are colored by distinct colors. The
crucial observations are that any colorful solution is a solution and the
probability of the existence of a colorful solution for a yes-instance of
Maximum Vertex-Disjoint Shortest Paths is at least $e^{-(p+\ell)}$ as any
solution in which all vertices receive distinct colors is a colorful solution.

We use dynamic programming over subsets of colors to find a colorful solution.
More precisely, we find the minimum number of arcs in a collection
${\mathcal{C}=\\{P_{i}\\}_{i\in S}}$ of $p$ pairwise vertex-disjoint paths for
some $S\subseteq[k]$ satisfying the conditions: (i) for each $i\in S$, the
path $P_{i}$ is a shortest path from $s_{i}$ to $t_{i}$ and (ii) there are no
vertices of distinct paths of the same color.

For a subset $X\subseteq[p+\ell]$ of colors and a positive integer $r\leq p$,
we denote by $f[X,r]$ the minimum total number of arcs in $r$ shortest paths
connecting distinct terminal pairs such that the paths contains only vertices
of colors in $X$ and there are no vertices of distinct paths of the same
color. We set $f[X,r]=\infty$ if such a collection of $r$ paths does not
exist.

To compute $f$, if $r=1$, then let $W\subseteq V$ be the subset of vertices
colored by the colors in $X$. We use Dijkstra’s algorithm to find the set
$I\subseteq[k]$ of all indices $i\in[k]$ such that the lengths of the shortest
$s_{i}$-$t_{i}$-paths in $G$ and $G[W]$ are the same. If $I=\emptyset$, then
we set $f[X,1]=\infty$. Assume that this is not the case. Then, we use the
variant of Dijkstra’s algorithm mentioned in Theorem 3 to find the index $i\in
I$ and a shortest $s_{i}$-$t_{i}$-path $P$ in $G[W]$ with a minimum number of
arcs. Finally, we set $f[X,1]$ to be equal to the number of arcs in $P$.

For $r\geq 2$, we compute $f[X,r]$ for each $X\subseteq[p+\ell]$ using the
recurrence relation

$f[X,r]=\min_{Y\subset X}\\{f[X\setminus Y,r-1]+f[Y,1]\\}.$ (2)

The correctness of computing the values of $f[X,1]$ follows from the
description and the correctness of recurrence (2) follows from the condition
that distinct paths should not have vertices of the same color.

We compute the values $f[X,r]$ in order of increasing $r\in[p]$. Since
computing $f[Y,1]$ for a given set $Y$ of colors can be done in polynomial
time, we can compute all values in overall $3^{p+\ell}\operatorname{poly}(n)$
time. Once all values $f[X,r]$ are computed, we observe that a colorful
solution exists if and only if $f[S,p]\leq\ell$.

If there is a colorful solution, then we conclude that
$(G,w,(s_{1},t_{1}),\dots,(s_{k},t_{k}),p,\ell)$ is a yes-instance of Maximum
Vertex-Disjoint Shortest Paths. Otherwise, we discard the considered coloring
and try another random coloring and iterate. If we fail to find a solution
after executing $N=\lceil e^{p+\ell}\rceil$ iterations, we obtain that the
probability that $(G,w,(s_{1},t_{1}),\dots,(s_{k},t_{k}),p,\ell)$ is a yes-
instance is at most $(1-\frac{1}{e^{p+\ell}})^{e^{p+\ell}}\leq e^{-1}$. Thus,
we return that $(G,w,(s_{1},t_{1}),\dots,(s_{k},t_{k}),p,\ell)$ is a no-
instance with the error probability upper bounded by $e^{-1}<1$. Since the
running time in each iteration is $3^{p+\ell}\operatorname{poly}(n)$ and
$p\leq\ell$, the total running time is in $2^{O(\ell)}\operatorname{poly}(n)$.

The above algorithm can be derandomized using the results of Naor, Schulman,
and Srinivasan [22] by replacing random colorings by prefect hash families. We
refer to the textbook by Cygan et al. [10] for details on this common
technique. ∎

The FPT result of Theorem 4 immediately raises the question about the
existence of a polynominal kernel. To show that a parameterized problem $P$
does presumably not admit a polynomial kernel, one can use the framework of
_cross-compositions_. Given an NP-hard problem $L$, a polynomial equivalence
relation $R$ on the instances of $L$ is an equivalence relation such that (i)
one can decide for any two instances in polynomial time whether they belong to
the same equivalence class, and (ii) for any finite set $S$ of instances, $R$
partitions the set into at most $\max_{I\in S}\operatorname{poly}(|I|)$
equivalence classes. Given an NP-hard problem $L$, a parameterized problem
$P$, and a polynomial equivalence relation $R$ on the instances of $L$, an OR-
cross-composition of $L$ into $P$ (with respect to $R$) is an algorithm that
takes $q$ instances $I_{1},I_{2},\ldots,I_{q}$ of $L$ belonging to the same
equivalence class of $R$ and constructs in
$\operatorname{poly}(\sum_{i=1}^{q}|I_{i}|)$ time an instance $(I,\rho)$ of
$P$ such that (i) $\rho$ is polynomially upper-bounded by
$\max_{i\in[q]}|I_{i}|+\log(q)$, and (ii) $(I,\rho)$ is a yes-instance of $P$
if and only if at least one of the instances $I_{i}$ is a yes-instance of $L$.
If a parameterized problem admits an OR-cross-composition, then it does not
admit a polynomial kernel unless NP $\subseteq$ coNP/poly [4].

In order to exclude a polynomial kernel, we first show that a special case of
Maximum Vertex-Disjoint Shortest Paths remains NP-hard. We call this special
case Layered Vertex-Disjoint Shortest Paths and it is the special case of
Vertex-Disjoint Shortest Paths where all edges have weight $1$ and the input
graph is layered, that is, there is a partition of the vertices into
(disjoint) sets $V_{1},V_{2},\ldots,V_{\lambda}$ such that all edges
$\\{u,v\\}$ are between two consecutive layers, that is $u\in V_{i}$ and
${v\in V_{i+1}}$ or $u\in V_{i}$ and $v\in V_{i-1}$ for some $i\in[\lambda]$.
Moreover, each terminal pair $(s_{i},t_{i})$ satisfies that $s_{i}\in V_{1}$,
$t_{i}\in V_{\lambda}$, and each shortest path between the two terminals is
_monotone_ , that is, it contains exactly one vertex of each layer. Layered
Vertex-Disjoint Shortest Paths is formally defined as follows.

> Layered Vertex-Disjoint Shortest Paths
>  Input: A $\lambda$-layered graph $G=(V,E)$ with a $\lambda$-partition
> $\\{V_{1},V_{2},\ldots,V_{\lambda}\\}$ of the vertex set, terminal pairs
> $(s_{1},t_{1}),(s_{2},t_{2}),\ldots,(s_{k},t_{k})$ with $s_{i}\in V_{1}$,
> $t_{i}\in V_{\lambda}$, and $\operatorname{dist}(s_{i},t_{i})=\lambda-1$ for
> all $i\in[\lambda]$. Question: Is there a collection
> $\mathcal{C}=\\{P_{i}\\}_{i\in[k]}$ of pairwise vertex-disjoint paths such
> that $P_{i}$ is an $s_{i}$-$t_{i}$-path of length $\lambda-1$ for all
> $i\in[k]$?

We now prove that Layered Vertex-Disjoint Shortest Paths is NP-complete.

######  Proposition 1.

Layered Vertex-Disjoint Shortest Paths is NP-complete.

###### Proof.

We focus on the NP-hardness as Layered Vertex-Disjoint Shortest Paths is a
special case of Vertex-Disjoint Shortest Paths and therefore clearly in NP. We
reduce from 3-Sat. The main part of the reduction is a selection gadget. The
gadget consists of a set $U$ of $n+1$ vertices $u_{0},u_{1},\ldots,u_{n}$ and
between each pair of consecutive vertices $u_{i-1},u_{i}$, there are two paths
with $m$ internal vertices each. Let the set of vertices be
$V_{i}=\\{v_{1}^{i},v_{2}^{i},\ldots,v_{m}^{i}\\}$ and
$W_{i}=\\{w_{1}^{i},w_{2}^{i},\ldots,w_{m}^{i}\\}$. The set of edges in the
selection gadget is

$\displaystyle
E=\\{\\{u_{i-1},v_{1}^{i}\\},\\{u_{i-1},w_{1}^{i}\\},\\{v_{m}^{i},u_{i}\\},\\{w_{m}^{i},u_{i}\\}$
$\displaystyle\mid i\in[n]\\}$
$\displaystyle\cup\,\\{\\{v_{j}^{i},v_{j+1}^{i}\\},\\{w_{j}^{i},w_{j+1}^{i}\\}$
$\displaystyle\mid i\in[n]\land j\in[m-1]\\}.$

The constructed instance will have $m+1$ terminal pairs and is depicted in
Figure 3.

$s_{3}$$u_{1}$$u_{2}$$t_{3}$$s_{1}$$t_{1}$$s_{2}$$t_{2}$ Figure 3: An example
of the construction in the proof of Proposition 1 for the input formula
$(x_{1}\lor x_{2}\lor\overline{x_{3}})\land(x_{1}\lor\overline{x_{2}}\lor
x_{3})$.

We set $s_{m+1}=u_{0}$ and $t_{m+1}=u_{n}$ and we will ensure that any
shortest $s_{m+1}$-$t_{m+1}$-path contains all vertices in $U$ and for each
$i\in[n]$ either all vertices in $V_{i}$ or all vertices in $W_{i}$. These
choices will correspond to setting the $i$th variable to either true or false.
Additionally, we have a terminal pair $(s_{j},t_{j})$ for each clause $C_{j}$.
There are (up to) three disjoint paths between $s_{j}$ and $t_{j}$, each of
which is of length $n\cdot(m+1)$. These paths correspond to which literal in
the clause satisfies it. For each of these paths, let $x_{i}$ be the variable
corresponding to the path. If $x_{i}$ appears positively in $C_{j}$, then we
identify the $(i-1)(m+1)+j+1$st vertex in the path with $w_{j}^{i}$ and if
$x_{i}$ appears negatively, then we identify the vertex with $v_{j}^{i}$. Note
that the constructed instance is $(m+1)n$-layered and that once any monotone
path starting in $s_{m+1}$ leaves the selection gadget, it cannot end in
$t_{m+1}$ as any vertex outside the selection gadget has degree at most two
and at the end of these paths are only terminals $t_{1},t_{2},\ldots,t_{m}$.

Since the construction clearly runs in polynomial time, we focus on the proof
of correctness. If the input formula is satisfiable, then we connect all
terminal pairs as follows. Let $\beta$ be a satisfying assignment. The
terminal pair $(s_{m+1},t_{m+1})$ is connected by a path containing all
vertices in $U$ and for each $i\in[n]$, if $\beta$ assigns the $i$th variable
to true, then the path contains all vertices in $V_{i}$ and otherwise all
vertices in $W_{i}$. For each clause $C_{j}$, let $x_{i_{j}}$ be variable in
$C_{j}$ which $\beta$ uses to satisfy $C_{j}$ (if multiple such variables
exist, we choose any one). By construction, there is a path associated with
$x_{i_{j}}$ that connects $s_{j}$ and $t_{j}$ and only uses one vertex in
$W_{i}$ if $x_{i_{j}}$ appears positively in $C_{j}$ and a vertex in $V_{i}$,
otherwise. Since each vertex in $V_{i}$ and $W_{i}$ is only associated with at
most one such path, we can connect all terminal pairs. For the other direction
assume that all $m+1$ terminal pairs can be connected by disjoint shortest
paths. As argued above, the $s_{m+1}$-$t_{m+1}$-path stays in the selection
gadget. We define a truth assignment by assigning the $i$th variable to true
if and only if the $s_{m+1}$-$t_{m+1}$-path contains the vertices in $V_{i}$.
For each clause $C_{j}$, we look at the neighbor of $s_{j}$ in the solution.
This vertex belongs to a path of degree-two vertices that at some point joins
the selection gadget. By construction, the vertex where this happens is not
used by the $s_{m+1}$-$t_{m+1}$-path, which guarantees that $C_{j}$ is
satisfied by the corresponding variable. Since all clauses are satisfied by
the same assignment, the formula is satisfiable and this concludes the proof.
∎

With the NP-hardness of Layered Vertex-Disjoint Shortest Paths at hand, we can
now show that it does not admit a polynomial kernel when parameterized by
$\ell$ by providing an OR-cross-composition from its unparameterized version
to the version parameterized by $\ell$.

######  Theorem 5.

Layered Vertex-Disjoint Shortest Paths parameterized by
$\ell=k\cdot(\lambda-1)$ does not admit a polynomial kernel unless NP
$\subseteq$ coNP/poly.

###### Proof.

We present an OR-cross-composition from Layered Vertex-Disjoint Shortest Paths
into Layered Vertex-Disjoint Shortest Paths parameterized by $\ell$. To this
end, assume we are given $t$ instances of Layered Vertex-Disjoint Shortest
Paths all of which have the same number $\lambda$ of layers and the same
number $k$ of terminal pairs. Moreover, we assume that $t$ is some power of
two. Note that we can pad the instance with at most $t$ trivial no-instances
to reach an equivalent instance in which the number of instances is a power of
two and the size of all instances combined has at most doubled.

The main ingredient for our proof is a construction to merge two instances
into one. The construction is depicted in Figure 4. We first proof that the
constructed instance is a yes-instance if and only if at least one of the
original instances was a yes-instance. Afterwards, we will show how to use
this construction to get an OR-cross-composition for all $t$ instances.

$s_{1}$$s_{2}$$s_{3}$$\dots$$s_{k}$$s_{1}^{i}$$s_{2}^{i}$$s_{3}^{i}$$\dots$$s_{k}^{i}$$G_{i}$$t_{1}^{i}$$t_{2}^{i}$$t_{3}^{i}$$\dots$$t_{k}^{i}$$s_{1}^{j}$$s_{2}^{j}$$s_{3}^{j}$$\dots$$s_{k}^{j}$$G_{j}$$t_{1}^{j}$$t_{2}^{j}$$t_{3}^{j}$$\dots$$t_{k}^{j}$$t_{1}$$t_{2}$$t_{3}$$\dots$$t_{k}$
Figure 4: The construction to merge two instances of Layered Vertex-Disjoint
Shortest Paths into one equivalent instance. The dotted edges can be read as
regular edges for $k=4$ and indicate where additional vertices and edges have
to be added for more terminal pairs. Note that the height of a vertex in the
drawing does not indicate its layer as dotted edges distort the picture.

To show that the construction works correctly, first assume that one of the
two instances original instances is a yes-instance. Since both cases are
completely symmetrical, assume that there are shortest disjoint paths between
all terminal pairs $(s_{a}^{i},t_{a}^{i})$ for all $a\in[k]$ in $G_{i}$. Then,
we can connect all terminal pairs $(s_{b},t_{b})$ by using the unique shortest
paths between $s_{b}$ and $s_{b}^{i}$ and between $t_{b}^{i}$ and $t_{b}$ for
all $b\in[k]$ together with the solution paths inside $G_{i}$. Now assume that
there is a solution in the constructed instance, that is, there are pairwise
vertex-disjoint shortest paths between all terminal pairs $(s_{b},t_{b})$ for
all $b\in[k]$. First assume that the $s_{1}$-$t_{1}$-path passes through
$G_{i}$. Then, this path uses the unique shortest path from $t_{1}^{i}$ to
$t_{i}$. Note that this path blocks all paths between $t_{b}^{j}$ and vertices
in $G_{j}$ for all $b\neq 1$. Thus, all paths have to pass through the graph
$G_{i}$. Note that the only possible way to route vertex-disjoint paths from
all $s$-terminals to all $s^{i}$ terminals and from all $t^{i}$-terminals to
all $t$-terminals is to connect $s_{a}$ to $s_{a}^{i}$ and $t_{a}^{i}$ to
$t_{a}$ for all $a\in[k]$. This implies that there is a solution that contains
vertex-disjoint shortest paths between $s_{a}^{i}$ and $t_{a}^{i}$ in $G_{i}$
for all $a\in[k]$, that is, at least one of the two original instances is a
yes-instance. The case where the $s_{1}$-$t_{1}$-path passes through $G_{j}$
is analogous since the only monotone path from $s_{1}$ to a vertex in $G_{j}$
is the unique shortest $s_{1}$-$s_{1}^{j}$-path and this path blocks all
monotone paths from $s_{a}$ to vertices in $G_{i}$ for all $a\neq 1$.

Note that the constructed graph is layered and that the number of layers is
$\lambda+2k$. Moreover, the size of the new instance is in
$O(|G_{i}|+|G_{j}|+k^{2})$. To complete the reduction, we iteratively half the
number of instances by partitioning all instances into arbitrary pairs and
merge the two instances in a pair into one instance. After $\log t$
iterations, we are left with a single instance which is a yes-instance if and
only if at least one of the $t$ original instances is a yes-instance. The size
of the instance is in $O(\sum_{i\in[t]}|G_{i}|+t\cdot k^{2})$ which is clearly
polynomial in $\sum_{i\in[t]}|G_{i}|$ as each instance contains at least $k$
vertices. Moreover, the parameter $\ell$ in the constructed instance is
$k\cdot(\lambda-1)+2k\log t$, which is polynomial in $|G_{i}|+\log t$ for each
graph $G_{i}$ as $G_{i}$ contains at least one vertex in each of the $\lambda$
layers and at least $k$ terminal vertices. Thus, all requirements of an OR-
cross-composition are met and this concludes the proof. ∎

Note that since Layered Vertex-Disjoint Shortest Paths is a special case of
Maximum Vertex-Disjoint Shortest Paths, Theorem 5 also excludes polynomial
kernels for Maximum Vertex-Disjoint Shortest Paths parameterized by $\ell$.

##  5 Conclusion

In this paper, we studied Maximum Vertex-Disjoint Shortest Paths. We show that
there is no $n^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximation in polynomial
time unless P $=$ NP. Moreover, if FPT$\neq$W[1] or assuming the stronger gap-
ETH, we show that there are no non-trivial approximations for Maximum Vertex-
Disjoint Shortest Paths in $f(k)\cdot\operatorname{poly}(n)$ time. When
parameterized by $\ell$, there is simple
$\lceil\sqrt{\ell}\rceil$-approximation in polynomial time that matches the
$n^{\nicefrac{{1}}{{2}}}$ lower bound as $\ell<n$. Finally, we showed that
Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable when
parameterized by $\ell$, but it does not admit a polynomial kernel.

A way to combine approximation algorithms and the theory of (polynomial)
kernels are _lossy kernels_ [20]. Since the exact definition is quite
technical and not relevant for this work, we only give an intuitive
description. An $\alpha$-approximate kernel or lossy kernel for an
optimization problem is a pair of algorithms that run in polynomial time which
are called _pre-processing algorithm_ and _solution-lifting algorithm_. The
pre-processing algorithm takes as input an instance $(I,\rho)$ of a
parameterized problem $P$ and outputs an instance $(I^{\prime},\rho^{\prime})$
of $P$ such that $|I^{\prime}|+\rho^{\prime}\leq g(\rho)$ for some computable
function $g$. The solution-lifting algorithm takes any solution $S$ of
$(I^{\prime},\rho^{\prime})$ and transforms it into a solution $S^{*}$ of
$(I,\rho)$ such that if $S$ is an $c$-approximation for
$(I^{\prime},\rho^{\prime})$ for some $\gamma\geq 1$, then $S^{*}$ is an
$\gamma\cdot\alpha$-approximation for $(I,\rho)$. If size of the kernel is
$g(\rho)$ and if $g$ is constant or a polynomial, then we call it a constant-
size or polynomial-size $\alpha$-approximate kernel, respectively. It is known
that a (decidable) parameterized problem admits a constant-size approximate
$\alpha$-kernel if and only if the unparameterized problem associated with $P$
can be $\alpha$-approximated (in polynomial time) [20]. Moreover, any
(decidable) parameterize problem admits an $\alpha$-approximate kernel (of
arbitrary size) if and only if the problem can be $\alpha$-approximated in
$f(\rho)\cdot\operatorname{poly}(|I|)$ time.

In terms of lossy kernelization, our results imply that there are no non-
trivial lossy kernels for the parameter $k$. For the parameter $\ell$, Theorem
3 implies a constant-size lossy kernel for $\alpha\in\Omega(\sqrt{\ell})$ and
Theorem 4 implies an $f(\ell)$-size lossy kernels for any $\alpha\geq 1$. This
leaves the following gap which we pose as an open problems.

######  Open Problem 1.

Are there any $\operatorname{poly}(\ell)$-size lossy kernels for Maximum
Vertex-Disjoint Shortest Paths with $\alpha\in o(\sqrt{\ell})$ (or even
constant $\alpha$)?

## References

  * Alon et al. [1995] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  _Journal of the ACM_ , 42(4):844–856, 1995\.
  * Bentert et al. [2023] Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche.  Using a geometric lens to find $k$-disjoint shortest paths.  _SIAM Journal on Discrete Mathematics_ , 37(3):1674–1703, 2023.
  * Berczi and Kobayashi [2017] Kristof Berczi and Yusuke Kobayashi.  The directed disjoint shortest paths problem.  In _Proceedings of the 25th Annual European Symposium on Algorithms (ESA)_ , pages 13:1–13:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
  * Bodlaender et al. [2014] Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch.  Kernelization lower bounds by cross-composition.  _SIAM Journal on Discrete Mathematics_ , 28(1):277–305, 2014.
  * Chalermsook et al. [2017] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan.  From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more.  In _Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 743–754. IEEE Computer Society, 2017.
  * Chen et al. [2023] Yijia Chen, Yi Feng, Bundit Laekhanukit, and Yanlin Liu.  Simple combinatorial construction of the k${}^{\mbox{o(1)}}$-lower bound for approximating the parameterized k-clique.  _CoRR_ , abs/2304.07516, 2023.
  * Chuzhoy and Li [2016] Julia Chuzhoy and Shi Li.  A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2.  _Journal of the ACM_ , 63(5):45:1–45:51, 2016\.
  * Chuzhoy et al. [2021] Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat.  Almost polynomial hardness of node-disjoint paths in grids.  _Theory of Computing_ , 17:1–57, 2021.
  * Chuzhoy et al. [2022] Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat.  New hardness results for routing on disjoint paths.  _SIAM Journal on Computing_ , 51(2):17–189, 2022.
  * Cygan et al. [2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  _Parameterized Algorithms_.  Springer, 2015.
  * Dinur [2016] Irit Dinur.  Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover.  _Electronic Colloquium on Computational Complexity_ , TR16-128, 2016\.
  * Eilam-Tzoreff [1998] Tali Eilam-Tzoreff.  The disjoint shortest paths problem.  _Discrete Applied Mathematics_ , 85(2):113–138, 1998.
  * Fomin et al. [2019] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  _Kernelization_.  Cambridge University Press, Cambridge, 2019.
  * Garey and Johnson [1979] M. R. Garey and David S. Johnson.  _Computers and Intractability: A Guide to the Theory of NP-Completeness_.  W. H. Freeman, 1979.
  * Impagliazzo and Paturi [2001] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  _Journal on Computer and Syststem Sciences_ , 62(2):367–375, 2001.
  * Karp [1975] Richard M. Karp.  On the computational complexity of combinatorial problems.  _Networks_ , 5(1):45–68, 1975.
  * Karthik C. S. and Khot [2022] Karthik C. S. and Subhash Khot.  Almost polynomial factor inapproximability for parameterized k-clique.  In _Proceedings of the 37th Computational Complexity Conference (CCC)_ , pages 6:1–6:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * Kleinberg [1996] Jon M. Kleinberg.  _Approximation algorithms for disjoint paths problems_.  PhD thesis, Massachusetts Institute of Technology, 1996.
  * Lochet [2021] William Lochet.  A polynomial time algorithm for the $k$-disjoint shortest paths problem.  In _Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 169–178. SIAM, 2021.
  * Lokshtanov et al. [2017] Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh.  Lossy kernelization.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC)_ , pages 224–237. ACM, 2017.
  * Manurangsi and Raghavendra [2017] Pasin Manurangsi and Prasad Raghavendra.  A birthday repetition theorem and complexity of approximating dense csps.  In _Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)_ , pages 78:1–78:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * Naor et al. [1995] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan.  Splitters and near-optimal derandomization.  In _Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 182–191. IEEE Computer Society, 1995.
  * Robertson and Seymour [1995] Neil Robertson and Paul D. Seymour.  Graph minors. XIII: The disjoint paths problem.  _Journal of Combinatorial Theory. Series B_ , 63(1):65–110, 1995.
  * Zuckerman [2007] David Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  _Theory of Computing_ , 3(1):103–128, 2007.