Exclusive graph searching vs. pathwidth

详细信息    查看全文

• 作者：Euripides Markou^a ; ¹ ; ^{emarkou@ucg.gr} ; Nicolas Nisse^b ; ^{Nicolas.Nisse@inria.fr} ; Sté ; phane Pé ; rennes^c ; ^{stephane.perennes@inria.fr}
• 关键词：Graph searching ; Pathwidth
• 刊名：Information and Computation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：252
• 期：Complete
• 页码：243-260
• 全文大小：670 K
• 卷排序：252

文摘

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph.In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard.