Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

Area of Science:

• Graph Theory and Algorithms
• Computational Complexity
• Approximation Algorithms

Background:

• The Maximum Vertex-Disjoint Shortest Paths problem seeks to connect the maximum number of terminal pairs using pairwise vertex-disjoint shortest paths.
• Recent breakthroughs have shown polynomial-time solvability for fixed k, implying a ck-approximation.
• Understanding the limits of approximation is crucial for practical applications.

Purpose of the Study:

• To establish the hardness of approximating the Maximum Vertex-Disjoint Shortest Paths problem.
• To determine the best possible approximation ratios achievable in polynomial time.
• To explore the exact complexity and kernelization bounds of the problem.

Main Methods:

• Leveraging the gap-Exponential Time Hypothesis (gap-ETH) to prove inapproximability results.
• Utilizing reductions from known NP-hard problems to demonstrate computational limitations.
• Developing a simple sqrt(l)-approximation algorithm to show tightness of bounds.
• Analyzing exact algorithms and kernelization complexity.

Main Results:

• Assuming the gap-ETH, an o(k)-approximation in f(k)poly(n) time is excluded for any k-dependent function f.
• An approximation ratio of m^(1/2-ε) is infeasible in polynomial time unless P=NP.
• A tight sqrt(l)-approximation algorithm is presented, where l is the number of edges in the optimal solution.
• The problem is solvable in 2^O(l)poly(n) time but does not admit a polynomial kernel in l.
• It cannot be solved in 2^o(l)poly(n) time under ETH.

Conclusions:

• The approximation algorithms for Maximum Vertex-Disjoint Shortest Paths are close to optimal, with hardness results matching known bounds.
• The study provides a comprehensive understanding of the problem's complexity, bridging the gap between theoretical limits and practical solvability.
• Hardness results hold even for undirected graphs with unit weights, while positive results generalize to directed graphs with arbitrary non-negative weights.