Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

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),\dots ,(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\le 1$ is a constant. (One can guess 1/c terminal pairs to connect in $k^{O(1/c)}$  time and then utilize Lochet's algorithm to compute the solution in $n^{f(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)-approximation within $f\left(k\right)\text{poly}\left(n\right)$  time for any function f that only depends on k. Our second result demonstrates the infeasibility of achieving an approximation ratio of $m^{1/2-\epsilon }$ in polynomial time, unless P $=$ NP. We also show that this bound is tight by providing a simple $\sqrt{\ell }$ -approximation algorithm, where $\ell$ is the number of edges in all paths of an optimal solution. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths can be solved in $2^{O\left(\ell \right)}\text{poly}\left(n\right)$ time, but does not admit a polynomial kernel in $\ell$ . Moreover, it cannot be solved in $2^{o\left(\ell \right)}\text{poly}\left(n\right)$ time under ETH. 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.