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 (s1, t1), (s2, t2), …, (sk, tk) . 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 ≤ 1 is a constant. (One can guess 1/c terminal pairs to connect in kO(1/c) time and then utilize Lochet's algorithm to compute the solution in nf(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) poly (n) time for any function f that only depends on k. Our second result demonstrates the infeasibility of achieving an approximation ratio of m1/2-ε in polynomial time, unless P = NP. We also show that this bound is tight by providing a simple [Formula: see text] -approximation algorithm, where ℓ 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 2O(ℓ) poly (n) time, but does not admit a polynomial kernel in ℓ . Moreover, it cannot be solved in 2o(ℓ) 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.