Shortest Disjoint Paths on a Grid - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2024

Shortest Disjoint Paths on a Grid

Mathieu Mari
Michał Pilipczuk
Piotr Sankowski

Résumé

The well-known k-disjoint paths problem involves finding pairwise vertex-disjoint paths between k specified pairs of vertices within a given graph if they exist. In the shortest k-disjoint paths problem one looks for such paths of minimum total length. Despite nearly 50 years of active research on the k-disjoint paths problem, many open problems and complexity gaps still persist. A particularly well-defined scenario, inspired by VLSI design, focuses on infinite rectangular grids where the terminals are placed at arbitrary grid points. While the decision problem in this context remains NP-hard, no prior research has provided any positive results for the optimization version. The main result of this paper is a fixed-parameter tractable (FPT) algorithm for this scenario. It is important to stress that this is the first result achieving the FPT complexity of the shortest disjoint paths problem in any, even very restricted classes of graphs where we do not put any restriction on the placements of the terminals.

Dates et versions

lirmm-04834909 , version 1 (12-12-2024)

Identifiants

Citer

Mathieu Mari, Anish Mukherjee, Michał Pilipczuk, Piotr Sankowski. Shortest Disjoint Paths on a Grid. SODA 2024 - 35th ACM/SIAM Symposium on Discrete Algorithms, Jan 2024, Alexandria, VA, United States. pp.346-365, ⟨10.1137/1.9781611977912.14⟩. ⟨lirmm-04834909⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More