Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

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 (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 ℓ