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 \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(k){{\,\textrm{poly}\,}}(n)\) 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}-\varepsilon }\) 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(\ell )} {{\,\textrm{poly}\,}}(n)\) time, but does not admit a polynomial kernel in \(\ell \) . Moreover, it cannot be solved in \(2^{o(\ell )}{{\,\textrm{poly}\,}}(n)\) 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.
