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₁,t₁),(s₂,t₂),… ,(sₖ,tₖ) ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , ( 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 ≤ 1 c ≤ 1 is a constant. (One can guess 1/ c terminal pairs to connect in k^O(1/c) k O ( 1 / c ) time and then utilize Lochet’s algorithm to compute the solution in n^f(1/c) 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)\,poly\,(n) 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 m^1/2-ε m 1 / 2 - ε in polynomial time, unless P $$=$$ = NP. We also show that this bound is tight by providing a simple √ ℓ -approximation algorithm, where ℓ