Zero-Visibility Cops-and-Robber Problems on Graphs (Boting Yang)

Abstract

In this talk, we consider the zero-visibility cops-and-robber game, which differs from the classical cops-and-robber game in one way: the robber is invisible. We show that the zero-visibility cop-number of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility cop-number can be bounded both above and below by positive multiples of the pathwidth.

We also consider the computational complexity aspects of the zero-visibility cops-and-robber game. On the one hand, we provide an algorithm that computes the zero-visibility cop-number of a tree in linear time. On the other hand, we show that the corresponding decision problem is NP-complete even for starlike graphs.

Time

Speaker

Room