Séminaire
|
Date : 16 mai 2024 15:30 - Salle :Amphi 3 - Pôle commun
Shortest Disjoint Paths on a GridMathieu MARI, Maître de conférences - LIRMM |
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. This work is joint work with Anish Mukherjee, Michal Pilipczuk and Piotr Sankowski. This paper
was presented in SODA 2024.