On shortest disjoint paths in planar graphs |
| |
Authors: | Yusuke Kobayashi Christian Sommer |
| |
Institution: | a Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan;b Department of Computer Science, Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-0033, Japan |
| |
Abstract: | 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 Pi is a path from si to ti for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths Pi have 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. |
| |
Keywords: | Disjoint paths Shortest path Planar graph Objective function Minimum cost flow |
本文献已被 ScienceDirect 等数据库收录! |
|