Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
摘要
Given a graph \(G=(V,E)\) and a set \(\mathcal {T}=\big \{ (s_i, t_i) : 1\le i\le k \big \}\subseteq V\times V\) of k pairs, the k-Vertex-Disjoint-Paths (resp. k-Edge-Disjoint-Paths) problem asks to determine whether there exist k pairwise vertex-disjoint (resp. edge-disjoint) paths \(P_1, P_2, \ldots , P_k\) in G such that, for each \(1\le i\le k\) , \(P_i\) connects \(s_i\) to \(t_i\) . Both the edge-disjoint and vertex-disjoint versions in undirected graphs are famously known to be FPT (parameterized by k) due to the Graph Minor Theory of Robertson and Seymour. Eilam-Tzoreff [DAM ‘98] introduced a variant, known as the k-Disjoint-Shortest-Paths problem, where each path is further required to be a shortest path connecting its pair. They showed that the k-Disjoint-Shortest-Paths problem is NP-complete on both directed and undirected graphs; this holds even if the graphs are planar and have unit edge lengths. We focus on four versions of the problem, corresponding to considering edge/vertex disjointness, and to considering directed/undirected graphs. Building on the reduction of Chitnis [SIDMA ’23] for k-Edge-Disjoint-Paths on planar DAGs, we obtain the following inapproximability lower bound for each of the four versions of k-Disjoint-Shortest-Paths on n-vertex graphs: We provide a single, unified framework to obtain lower bounds for each of the four versions of k-Disjoint-Shortest-Paths. We are able to further strengthen our results by restricting the structure of the input graphs in the lower bound constructions as follows: The reductions outlined in this paper produce graphs in which half of the terminal pairs are trivially satisfiable, so any improvement of our \((\frac{1}{2} + \epsilon )\) inapproximability factor requires a different approach. As a byproduct of our reductions, we also show that the exact versions of each problem is W[1]-hard and give a \(f(k)\cdot n^{o(k)}\) -time lower bound for them under ETH. This exact lower bound shows that the \(n^{O(k)}\) -time algorithms of Bérczi and Kobayashi [ESA ‘17] for Directed- \(k\) -EDSP and Directed- \(k\) -VDSP are tight.