文章基本信息

标题：A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
本地全文：下载
作者：Sebastian Brandt ; Yuval Emek ; Jara Uitto 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：82:1-82:13
DOI：10.4230/LIPIcs.ICALP.2017.82
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O(n^{k + 1}) bound is asymptotically tight for any constant k >= 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.
关键词：cops and robbers; capture time; lower bound