The complexity of zero-visibility cops and robber

• DOI: 10.1016/j.tcs.2015.03.022
• Publication Date: 2015-03-26T11:16:15Z
• Authors: Dariusz Dereniowski; Danny Dyer; Ryan M. Tifenbach; Boting Yang
• Keywords: Visibility; Zero (linguistics); Tree (set theory); Zero-sum game

In this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.