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) <i>n</i>-vertex graph <i>G</i> along with <i>k</i> terminal pairs <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:mrow><mml:mo>(</mml:mo> <mml:msub><mml:mi>s</mml:mi> <mml:mn>1</mml:mn></mml:msub> <mml:mo>,</mml:mo> <mml:msub><mml:mi>t</mml:mi> <mml:mn>1</mml:mn></mml:msub> <mml:mo>)</mml:mo></mml:mrow> <mml:mo>,</mml:mo> <mml:mrow><mml:mo>(</mml:mo> <mml:msub><mml:mi>s</mml:mi> <mml:mn>2</mml:mn></mml:msub> <mml:mo>,</mml:mo> <mml:msub><mml:mi>t</mml:mi> <mml:mn>2</mml:mn></mml:msub> <mml:mo>)</mml:mo></mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mrow><mml:mo>(</mml:mo> <mml:msub><mml:mi>s</mml:mi> <mml:mi>k</mml:mi></mml:msub> <mml:mo>,</mml:mo> <mml:msub><mml:mi>t</mml:mi> <mml:mi>k</mml:mi></mml:msub> <mml:mo>)</mml:mo></mml:mrow> </mml:mrow> </mml:math> . 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 <i>k</i>. Lochet's result implies the existence of a polynomial-time <i>ck</i>-approximation for Maximum Vertex-Disjoint Shortest Paths, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>c</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn></mml:mrow> </mml:math> is a constant. (One can guess 1/<i>c</i> terminal pairs to connect in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>k</mml:mi> <mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>c</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> </mml:math> time and then utilize Lochet's algorithm to compute the solution in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi> <mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>c</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> </mml:math> 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 <i>o</i>(<i>k</i>)-approximation within <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> <mml:mrow><mml:mspace></mml:mspace> <mml:mtext>poly</mml:mtext> <mml:mspace></mml:mspace></mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> time for any function <i>f</i> that only depends on <i>k</i>. Our second result demonstrates the infeasibility of achieving an approximation ratio of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>m</mml:mi> <mml:mrow><mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ε</mml:mi></mml:mrow> </mml:msup> </mml:math> in polynomial time, unless P <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>=</mml:mo></mml:math> NP. We also show that this bound is tight by providing a simple <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msqrt><mml:mi>ℓ</mml:mi></mml:msqrt> </mml:math> -approximation algorithm, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ℓ</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msup><mml:mn>2</mml:mn> <mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> <mml:mrow><mml:mspace></mml:mspace> <mml:mtext>poly</mml:mtext> <mml:mspace></mml:mspace></mml:mrow> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:mrow> </mml:math> time, but does not admit a polynomial kernel in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ℓ</mml:mi></mml:math> . Moreover, it cannot be solved in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msup><mml:mn>2</mml:mn> <mml:mrow><mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> <mml:mrow><mml:mspace></mml:mspace> <mml:mtext>poly</mml:mtext> <mml:mspace></mml:mspace></mml:mrow> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:mrow> </mml:math> 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.