Planar Disjoint Shortest Paths is Fixed-Parameter Tractable

Abstract

In the Disjoint Shortest Paths problem one is given a graph $G$ and a set $\mathcal{T}=\{(s_1,t_1),\dots ,(s_k,t_k)\}$ of $k$ vertex pairs. The question is whether there exist vertex-disjoint paths $P_1,\dots ,P_k$ in $G$ so that each $P_i$ is a shortest path between $s_i$ and $t_i$. While the problem is known to be W[1]-hard in general, we show that it is fixed-parameter tractable on planar graphs with positive edge weights. Specifically, we propose an algorithm for Planar Disjoint Shortest Paths with running time $2^{O(k\log k)}\cdot n^{O(1)}$. Notably, our parameter dependency is better than state-of-the-art $2^{O(k^2)}$ for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.

55 pages