Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

We show that computing a $m^{1/2-\epsilon }$-approximation for Maximum Vertex-Disjoint Shortest Paths is NP-hard for any $\epsilon >0$ (Theorem 3). Moreover in terms of FPT-approximations, we demonstrate in Theorem 1 that any $k^{o(1)}$-approximation in time $f(k)\cdot \mathrm{poly}(n)$ implies FPT $=$ W[1] and that it is impossible to achieve an $o(k)$-approximation in time $f(k)\cdot \mathrm{poly}(n)$ unless the gap-ETH fails. This significantly improves the current state of approximation results for Maximum Vertex-Disjoint Shortest Paths in two ways. First, we use the weaker assumption FPT $\ne$ W[1] instead of the gap-ETH. Second, our theorem excludes approximation factors polynomial in the input size, rather than only constant factors larger than 2 as shown by Chitnis et al. [8].

We complement the first lower bound by showing that a simple greedy strategy for Maximum Vertex-Disjoint Paths achieves a $\lceil \sqrt{\mathrm{\ell }}\rceil$-approximation also for Maximum Vertex-Disjoint Shortest Paths (Theorem 4). In Theorems 5 and 7, we show that Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable when parameterized by $\mathrm{\ell }$, but it does not admit a polynomial kernel. We mention that our hardness results hold for undirected graphs with unit weights, and all our positive results hold even for directed and edge-weighted input graphs. We summarize our results in Table 1.

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 one. Moreover, the maximum number $\mathrm{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 \mathrm{poly}(n)$-time $k^{o(1)}$-approximation for Clique would imply that FPT $=$ W[1] [7, 22], a $f(k)\cdot \mathrm{poly}(n)$-time $o(k)$-approximation for Clique refutes the gap-ETH [6], and 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 [12].

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

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_1^i,v_2^i,\mathrm{\dots },v_{\nu }^i\}$ 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 (non-terminal) vertices $(s_i^j,t_i^j)$ for each vertex $v_j^i\in V_i$. Next for each color $i$, we add a binary tree of height $\lceil \log (\nu )\rceil$ where the vertices $s_i^j$ are the leaves for all $v_j^i\in V_i$. We make $s_i$ adjacent to the root of the binary tree. Analogously, we add a binary tree of the same height with leaves $t_j^i$ and make $t_i$ adjacent to the root. Next, we add a crossing gadget for each pair of vertices $(v_j^i,v_b^a)$ with . If $\{v_j^i,v_b^a\}\in 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\}\notin 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  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  and $y_{1,b}^{i,a}$ to $x_{\nu ,b}^{i+1,a}$ for all $b\in [\nu ]$ and all . Third, we connect also via paths of length two $y_{1,b}^{i,i+1}$ to $u_{b,1}^{i+1,i+2}$ for all  and all $b\in [\nu ]$. Next, we connect via paths of length $2\nu$ each vertex $s_i^j$ to $x_{\nu ,j}^{1,i}$ for each $i>1$ and $j\in [\nu ]$. Similarly, $v_{j,\nu }^{i,k}$ is connected to $t_i^j$ via paths of length $2\nu$. Finally, we connect $s_j^1$ with $u_{j,1}^{1,2}$ for all $j\in [\nu ]$ and $y_{1,j}^{k-2,k-1}$ with $t_j^k$ for all $j\in [\nu ]$. This concludes the construction.

We next prove that all shortest $s_i$-$t_i$-paths are of the form

for some $j\in [\nu ]$ and where the $s_1$-$t_1$-paths go directly from $s_i^j$ to $u_{j,1}^{1,2}$ and the $s_k$-$t_k$-paths go directly from $y_{1,j}^{k-1,k}$ 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_i^j$ is the same value $x=\lceil \log (\nu )\rceil +1$ 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 $t_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 $s_i$-$t_i$-path of length at most $y$ contains an edge of the form $y_{1,b}^{i,i+1}$ to $u_{b,1}^{i+1,i+2}$. 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_{j,b}^{i^{\prime },a}$ for any values $i^{\prime }\le i\le 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 .³³3We mention that there are some pairs of vertices $x_{j_1,b_1}^{i_1,a_1}$ and $x_{j_2,b_2}^{i_2,a_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,1}^{1,2}=u_{1,1}^{1,2},x_{2,2}^{1,2})$ in Figure 1 with a distance of $4$. However, in all examples it holds that $i_1\nu -j_1\ne i_2\nu -j_2$ and $a_1\nu +b_1\ne 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_{1,b}^{i,i+1}$ to $u_{b,1}^{i+1,i+2}$ and the shortest path from $s_i^j$ to some vertex $y_{1,b}^{i,i+1}$ is to the vertex $y_{1,j}^{i,i+1}$. Note that the other endpoint of the specified edge is $u_{j,1}^{i,i+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 . 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_{j_i,j_{i^{\prime }}}^{i,i^{\prime }}\ne x_{j_i,j_{i^{\prime }}}^{i,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},\mathrm{\dots },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\ne r\in [p]$. Let $q,r$ be two arbitrary distinct indices in $[p]$ and let without loss of generality be . Note that the two mentioned paths can only overlap in vertices $u_{j_q,j_r}^{i_q,i_r},v_{j_q,j_r}^{i_q,i_r},x_{j_q,j_r}^{i_q,i_r},$ or $y_{j_q,j_r}^{i_q,i_r}$ and that the $j_q$^th canonical path for $i_q$ only contains vertices $u_{j_q,j_r}^{i_q,i_r}$ and $v_{j_q,j_r}^{i_q,i_r}$ and the $j_r$^th canonical path for $i_r$ only contains $x_{j_q,j_r}^{i_q,i_r}$ and $y_{j_q,j_r}^{i_q,i_r}$. Moreover, since by assumption $v_{j_q}^{i_q}$ and $v_{j_r}^{i_r}$ are adjacent, it holds by construction that $u_{j_q,j_r}^{i_q,i_r},v_{j_q,j_r}^{i_q,i_r},x_{j_q,j_r}^{i_q,i_r}$, and $y_{j_q,j_r}^{i_q,i_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 have degree one, and the construction can be computed in polynomial time. $◀$

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

We continue with an unparameterized lower bound by establishing that computing a $m^{\frac{1}{2}-\epsilon }$-approximation is NP-hard. We mention that the reduction is quite similar to the reduction in the proof for Theorem 1.

It is known that computing a $n^{1-\epsilon }$-approximation for Clique is NP-hard [19, 30]. 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 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.

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 . 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},\mathrm{\dots },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\ne r\in [p]$. Let $q,r$ be two arbitrary distinct indices in $[p]$ and let without loss of generality be . 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 $m^{1-\epsilon }$ as the number of vertices in the original instance and the number of edges in the constructed instance are not identical. Still, the number $m$ of edges in the constructed instance is at most $3N^2$, where $N$ is the number of vertices in the original instance of Clique. Hence, any $m^{1/2-\epsilon }$-approximation for Maximum Vertex-Disjoint Shortest Paths corresponds to a ${(3N^2)}^{1/2-\epsilon }=N^{1-{\epsilon }^{\prime }}$-approximation for Clique for some  and therefore computing a $m^{1/2-\epsilon }$-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 3 also holds for the edge disjoint version of Maximum Vertex-Disjoint Shortest Paths. However in this case, a very similar result was already known before. Guruswami et al. [18] showed that computing a $m^{1/2-\epsilon }$-approximation is NP-hard for a related problem called Length Bounded Edge-Disjoint Paths. Their reduction immediately implies the same hardness for Maximum Edge-Disjoint Shortest Paths. To the best of our knowledge, the best known unparameterized approximation lower bound for Maximum Vertex-Disjoint Shortest Paths was the $2-\epsilon$ lower bound due to Chitnis et al. [8] and we are not aware of any lower bound for Maximum Vertex-Disjoint 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{\mathrm{\ell }}\rceil$-approximation. Note that we can always assume that $\mathrm{\ell }\le 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 [23, 24].

Let $\mathrm{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$.⁴⁴4The 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 ${\mathrm{\ell }}_j$ be the number of arcs in the found path. Our algorithm iteratively picks the shortest $s_j$-$t_j$-path using ${\mathrm{\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 ${\mathrm{\ell }}_j$. We distinguish whether ${\mathrm{\ell }}_j+1\le \min (\sqrt{n},\lceil \sqrt{\mathrm{\ell }}\rceil )$ or not.

While ${\mathrm{\ell }}_j+1\le \min (\sqrt{n},\lceil \sqrt{\mathrm{\ell }}\rceil )$, note that we removed at most ${\mathrm{\ell }}_j+1$ terminals pairs in $\mathrm{OPT}$. Hence, if ${\mathrm{\ell }}_j+1\le \min (\sqrt{n},\lceil \sqrt{\mathrm{\ell }}\rceil )$ holds at every stage, then we connected at least $\left|\mathrm{OPT}\right|/\min (\sqrt{n},\lceil \sqrt{\mathrm{\ell }}\rceil )$ terminal pairs, that is, we found a $\min (\sqrt{n},\lceil \sqrt{\mathrm{\ell }}\rceil )$-approximation.

So assume that at some point ${\mathrm{\ell }}_j>\min (\sqrt{n},\lceil \sqrt{\mathrm{\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\cdot \min (\sqrt{n},\lceil \sqrt{\mathrm{\ell }}\rceil )$ terminal pairs from $\mathrm{OPT}$ thus far. We now make a case distinction whether or not $\sqrt{n}\le \lceil \sqrt{\mathrm{\ell }}\rceil$. If ${\mathrm{\ell }}_j+1>\lceil \sqrt{\mathrm{\ell }}\rceil \ge \sqrt{n}$, then we note that all remaining paths in $\mathrm{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 $\mathrm{OPT}$. Hence, we can infer that $|\mathrm{OPT}|\le (x+1)\cdot \sqrt{n}$. Consequently, even though we might remove all remaining terminal pairs in $\mathrm{OPT}$ by connecting $s_j$ and $t_j$, this is still a $\sqrt{n}$-approximation (and a $\lceil \sqrt{\mathrm{\ell }}\rceil$-approximation as we assumed $\lceil \sqrt{\mathrm{\ell }}\rceil \ge \sqrt{n}$).

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

Let $(G,w,(s_1,t_1),\mathrm{\dots },(s_k,t_k),p)$ be an instance of Maximum Vertex-Disjoint Shortest Paths. First, we guess the value of $\mathrm{\ell }$ by starting with $\mathrm{\ell }=p$ and increasing the value of $\mathrm{\ell }$ by one whenever we cannot find a solution with at least $p$ shortest paths and at most $\mathrm{\ell }$ edges. We start with $\mathrm{\ell }=p$ as any set of $p$ disjoint paths contains at least $\mathrm{\ell }$ edges. Notice that the total number of vertices in a (potential) solution with $p$ paths is at most $\mathrm{\ell }+p$. We use the color-coding technique of Alon, Yuster, and Zwick [2]. We color the vertices of $G$ uniformly at random using $p+\mathrm{\ell }$ colors (the set of colors is $[\mathrm{\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+\mathrm{\ell })!}{{(p+\mathrm{\ell })}^{(p+\mathrm{\ell })}}\ge e^{-(p+\mathrm{\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/equal 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+\mathrm{\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 $𝒞={\{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+\mathrm{\ell }]$ of colors and a positive integer $r\le 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]=\mathrm{\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=\mathrm{\varnothing }$, then we set $f[X,1]=\mathrm{\infty }$. Assume that this is not the case. Then, we use the variant of Dijkstra’s algorithm mentioned in Theorem 4 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\ge 2$, we compute $f[X,r]$ for each $X\subseteq [p+\mathrm{\ell }]$ using the recurrence relation

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+\mathrm{\ell }}\mathrm{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]\le \mathrm{\ell }$.

If there is a colorful solution, then we conclude that $(G,w,(s_1,t_1),\mathrm{\dots },(s_k,t_k),p)$ 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+\mathrm{\ell }}\rceil$ iterations, we obtain that the probability that $(G,w,(s_1,t_1),\mathrm{\dots },(s_k,t_k),p)$ is a yes-instance is at most ${(1-\frac{1}{e^{p+\mathrm{\ell }}})}^{e^{p+\mathrm{\ell }}}\le e^{-1}$. Thus, we return that $(G,w,(s_1,t_1),\mathrm{\dots },(s_k,t_k),p)$ is a no-instance with the error probability upper bounded by . Since the running time in each iteration is $3^{p+\mathrm{\ell }}\mathrm{poly}(n)$ and $p\le \mathrm{\ell }$, the total running time is in $2^{O(\mathrm{\ell })}\mathrm{poly}(n)$. Note that we do the color coding and dynamic programming for each value between $p$ and the actual value $\mathrm{\ell }$. However, this only adds an additional factor of $\mathrm{\ell }\le n$ which disappears in the $\mathrm{poly}(n)$.

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

The FPT result of Theorem 5 immediately raises the question about the existence of a polynomial 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}\mathrm{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,\mathrm{\dots },I_q$ of $L$ belonging to the same equivalence class of $R$ and constructs in $\mathrm{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 [5].

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,\mathrm{\dots },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+1}$ and $v\in V_i$ for some $i\in [\lambda -1]$. 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.

It is quite straight-forward to prove that Layered Vertex-Disjoint Shortest Paths is NP-complete.

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,\mathrm{\dots },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,\mathrm{\dots },v_m^i\}$ and $W_i=\{w_1^i,w_2^i,\mathrm{\dots },w_m^i\}$. The set of edges in the selection gadget is

The constructed instance will have $m+1$ terminal pairs and is depicted in Figure 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,\mathrm{\dots },t_m$.

Since the construction 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 an arbitrary 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 $\mathrm{\ell }$ by providing an OR-cross-composition from its unparameterized version to the version parameterized by $\mathrm{\ell }$.

We present an OR-cross-composition from Layered Vertex-Disjoint Shortest Paths into Layered Vertex-Disjoint Shortest Paths parameterized by $\mathrm{\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 prove 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.

To show that the construction works correctly, first assume that one of the two 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\ne 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\ne 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 $\mathrm{\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 Vertex-Disjoint Shortest Paths (and therefore of Maximum Vertex-Disjoint Shortest Paths), Theorem 7 also excludes polynomial kernels for these problems parameterized by $\mathrm{\ell }$.