Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in $k^2$ and Linear in $n$

Abstract

In this paper, we study the \textsf{Planar Disjoint Paths} problem: Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i{)}_{i=1}^k$ of vertices, the goal is to find a set $\mathcal{P}$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $i\in \{1,\dots ,k\}$. We present a $2^{O(k^2)}n$-time algorithm for the \textsf{Planar Disjoint Paths} problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}{n}^6$-time algorithm [STOC 2020].

SODA 2023