首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Induced disjoint paths problem in a planar digraph
Authors:Yusuke Kobayashi  
Institution:aUniversity of Tokyo, Tokyo 113-8656, Japan
Abstract:As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s1,t1),…,(sk,tk)}. The objective is to find k paths P1,…,Pk such that Pi is a path from si to ti and Pi and Pj have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.
Keywords:Disjoint paths  Induced subgraph  Planar digraph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号