On shortest disjoint paths in planar graphs
On shortest disjoint paths in planar graphs
复制标题
DOI：
10.1016/j.disopt.2010.05.002
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Yusuke Kobayashi;Christian Sommer
中科院分区：
文献类型：
--
作者：
Yusuke Kobayashi;Christian Sommer
对于图 G 和顶点对集合 {(s1,t1),…,(sk,tk)}，k 个不相交路径问题是找到 k 个顶点不相交路径 P1,…,Pk，其中 Pi 是对于每个 i=1,…,k 从 sito ti 开始的路径。在相应的优化问题（最短不相交路径问题）中，必须选择顶点不相交路径 Pi 以使给定的目标函数最小化。我们考虑两个不同的目标，即最小化总路径长度（最小总和，或简称：Min-Sum），以及最小化最长路径的长度（Min-Max），其中 k=2,3。最小和：我们扩展了 Colin de Verdière 和 Schrijver 的最新结果，证明对于平面图和最多与两个面相邻的终端，可以在多项式时间内解决最小和 2 不相交路径问题。我们还证明，对于以任意顺序与一个面相邻的六个终端，可以在多项式时间内解决最小和 3 不相交路径问题。最小-最大：最小-最大 2 不相交路径问题对于一般图来说是 NP 困难的。我们提出了一种在多项式时间内解决树宽为 2 的图问题的算法。因此，我们缩小了简单实例和困难实例之间的差距，因为对于树宽为 3 的图来说，该问题是弱 NP 困难的。
For a graph G and a collection of vertex pairs {(s1,t1),…,(sk,tk)}, the k disjoint paths problem is to find k vertex-disjoint paths P1,…,Pk, where Piis a path from sito tifor each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths Pihave to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3. Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time. Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.