Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
By: Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk
Potential Business Impact:
Finds many separate shortest paths in maps.
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.
Similar Papers
Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
Data Structures and Algorithms
Finds two separate shortest paths at once.
Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
Data Structures and Algorithms
Finds two separate shortest paths at once.
Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
Data Structures and Algorithms
Finds shortest paths with many stops faster.