论文标题
有效的图形未成年人理论和（平面）不相交路径的参数化算法
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
论文作者
论文摘要
在“脱节路径问题”中，输入由$ n $ vertex Graph $ g $和$ k $顶点对的集合，$ \ {（s_i，t_i）\} _ {i = 1}^k $组成，目的是确定是否存在$ \ \ \ \ k $ k $ k^k; $ g $中的顶点 - 二十一个路径，其中$ p_i $的最终媒体为$ s_i $和$ t_i $。该问题显示出Robertson和Seymour的$ F（k）n^3 $ - 时间算法（Graph Minors XIII，Disshoint Paths问题，JCTB）。在现代术语中，这意味着与$ k $相对于固定的参数可处理（FPT）。值得注意的是，上述脱节路径的算法是整个图形未成年人理论的基石，对$ g（k）n^3 $ - n^3 $ - 时间算法至关重要（给定两个无向图，$ g $，$ g $，$ n $ n $ n $和$ k $ pertices的$ h $，分别确定$ g $ g $是否$ h $ can $ h $ h $ h $ h $ h。 在这个半肺活量中，我们将首先对图形未成年人理论进行阐述，并从参数化复杂性的角度强调效率。其次，我们将回顾有关脱节路径和平面偏离路径问题的最新技术状况。最后，我们将讨论一种新算法背后的主要思想，该算法结合了缩小树宽度和代数方法来解决平面段路径的时间$ 2^{k^{k^{o（1）}} n^{o（1）} $（对于无向图）。
In the Disjoint Paths problem, the input consists of an $n$-vertex graph $G$ and a collection of $k$ vertex pairs, $\{(s_i,t_i)\}_{i=1}^k$, and the objective is to determine whether there exists a collection $\{P_i\}_{i=1}^k$ of $k$ pairwise vertex-disjoint paths in $G$ where the end-vertices of $P_i$ are $s_i$ and $t_i$. This problem was shown to admit an $f(k)n^3$-time algorithm by Robertson and Seymour (Graph Minors XIII, The Disjoint Paths Problem, JCTB). In modern terminology, this means that Disjoint Paths is fixed parameter tractable (FPT) with respect to $k$. Remarkably, the above algorithm for Disjoint Paths is a cornerstone of the entire Graph Minors Theory, and conceptually vital to the $g(k)n^3$-time algorithm for Minor Testing (given two undirected graphs, $G$ and $H$ on $n$ and $k$ vertices, respectively, determine whether $G$ contains $H$ as a minor). In this semi-survey, we will first give an exposition of the Graph Minors Theory with emphasis on efficiency from the viewpoint of Parameterized Complexity. Secondly, we will review the state of the art with respect to the Disjoint Paths and Planar Disjoint Paths problems. Lastly, we will discuss the main ideas behind a new algorithm that combines treewidth reduction and an algebraic approach to solve Planar Disjoint Paths in time $2^{k^{O(1)}}n^{O(1)}$ (for undirected graphs).
