线性时间中的平面不相交路径

作者：Petr A. Golovach,Stavros G. Kolliopoulos,Giannos Stamoulis,Dimitrios M. Thilikos

摘要：不想交路径问题提出在 graphGcan 中固定数量的终端对是否能通过成对不相交路径链接。在这个问题的背景下，Robertson和Seymour引入无关顶点技术，该技术从此成为图算法的标准。该技术包括检测一个顶点，该顶点在其删除创建问题的等效实例的意义上是不相关的。这样，可以解决O（n2）步骤中的问题，因为不相关顶点的检测花费O（n）时间并且可能需要移除最多的时间。在本文中，我们研究了平面不相交路径问题，其中输入图是平面的。我们引入了无关顶点技术的扩展，其中所有不相关的顶点被同时移除，使得平面不相交路径问题的实例可以以线性步数转换为具有有界树宽度的等效顶点。因此，对于每个固定数量的终端，可以在线性时间内解决平面不相交路径问题。

原文标题：Planar Disjoint Paths in Linear Time

原文摘要：The Disjoint Paths problem asks whether a fixed number of pairs of terminals in a graphGcan be linked by pairwise disjoint paths. In the context of this problem, Robertson and Seymour introduced the celebrated irrelevant vertex technique that has since become standard in graph algorithms. The technique consists of detecting a vertex that is irrelevant in the sense that its removal creates an equivalent instance of the problem. That way, one may solve the problem inO(n2)steps, as the detection of an irrelevant vertex takesO(n)time and at mostnvertices may need to be removed. In this paper we study the Planar Disjoint Paths problem where the input graph is planar. We introduce an extension of the irrelevant vertex technique where all the irrelevant vertices are removed simultaneously so that an instance of the Planar Disjoint Paths problem can be transformed in a linear number of steps to an equivalent one that has bounded treewidth. As a consequence, the Planar Disjoint Paths problem can be solved in linear time for every fixed number of terminals.

地址：https://arxiv.org/abs/1907.05940