Planar Disjoint Shortest Paths is Fixed-Parameter Tractable

In the Disjoint Shortest Paths problem one is given a graph \(G\) and a set \(\mathcal{T} = \{(s_1,t_1),\ldots,(s_k,t_k)\}\) of \(k\) vertex pairs. The question is whether there exist vertex-disjoint paths \(P_1,\ldots,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 \(\textsf{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^{\mathcal{O}(k \log k)} \cdot n^{\mathcal{O}(1)}\). Notably, our parameter dependency is better than state-of-the-art \(2^{\mathcal{O}(k^2)}\) for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.