2024/08/07 by Rajesh Chitnis, Chitnis, Rajesh, Samuel Thomas +3
Computer Science · Business, Management and Accounting · #Complexity and Algorithms in Graphs #Facility Location and Emergency Management #Internet Traffic Analysis and Secure E-voting
paper · pdf · doi:10.48550/arxiv.2408.03933
Given a graph G=(V,E) and a set T=\ (si, ti) : 1≤ i≤ k \⊆ V× 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 P1, P2, ..., Pk in G such that, for each 1≤ i≤ k, Pi connects si to ti. 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 individual 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: - Under Gap-ETH, there exists a constant δ>0 such that for any constant 0<ε≤ (1)/(2) and any computable function f, there is no ((1)/(2)+ε)-approx in f(k)⋅ nδ⋅ k time. We further strengthen our results as follows: Directed: Inapprox lower bound for edge-disjoint (resp. vertex-disjoint) paths holds even if the input graph is a planar (resp. 1-planar) DAG with max in-degree and max out-degree at most 2. Undirected: Inapprox lower bound for edge-disjoint (resp. vertex-disjoint) paths hold even if the input graph is planar (resp. 1-planar) and has max degree 4.