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_1,t_1),(s_2,t_2),\ldots ,(s_k,t_k)$$(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 \le 1$$c≤1
is a constant. (One can guess 1/
c
terminal pairs to connect in
$$k^{O({1}/{c})}$$kO(1/c)
time and then utilize Lochet’s algorithm to compute the solution in
$$n^{f({1}/{c})}$$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){{\,\textrm{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}-\varepsilon }$$m1/2-ε
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)$$2O(ℓ)poly(n)
time, but does not admit a polynomial kernel in
$$\ell $$ℓ
. Moreover, it cannot be solved in
$$2^{o(\ell )}{{\,\textrm{poly}\,}}(n)$$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.