论文标题
平面图上的分离路径问题的参数化算法：$ k^2 $的指数和$ n $线性的线性
Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in $k^2$ and Linear in $n$
论文作者
论文摘要
在本文中，我们研究\ textsf {平面脱节路径}问题：给定一个无方向的平面图$ g $，带有$ n $顶点和一套$ t $ t $ of $ k $ pairs $（s_i，t_i，t_i）_ {i = 1}^k $ a $ s_i $和$ t_i $的所有索引$ i \ in \ {1，\ ldots，k \} $。我们提出了$ 2^{o（k^2）} n $ - time算法的\ textsf {planar discart discoint paths}问题。这改善了两种先前最著名的算法：$ 2^{2^{o（k）}} n $ - 时间算法[离散应用数学1995]和$ 2^{o（k^2）} n^6 $ - time time Algorithm [Stoc 2020]。
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,\ldots,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].
