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

11/07/2022

∙

by   Kyungjin Cho, et al.

∙

0

∙

share

In this paper, we study the 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 𝒫 of k pairwise vertex-disjoint paths connecting s_i and t_i for all indices i∈{1,…,k}. We present a 2^O(k^2)n-time algorithm for the 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].