2017-06-20 | Zero-Visibility Cops-and-Robber Problems on Graphs
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.
Boting Yang received the B.Sc. degree in mathematics from Fudan University, the M.Sc. and Ph.D. degrees in mathematics from Xi’an Jiaotong University, and the Ph.D. degree in computer science from Memorial University of Newfoundland. He is currently a professor at the University of Regina. He was also a visiting Professor at Chinese University of Hong Kong and the University of Hong Kong respectively.
His main research interests include Algorithmic Graph Theory, Computational Geometry, and Computational Biology. He is an associate Editor of Discrete Mathematics, Algorithms and Applications, and guest editors of four special issues of Theoretical Computer Science and Journal of Combinatorial Optimization. He has published 60 papers in refereed journals and 58 papers in conference proceedings.