Variations on Cops and Robbers - math.cmu.edu

1 Variations on Cops and RobbersAlan Frieze Michael Krivelevich Po-Shen Loh AbstractWe consider several variants of the classical Cops and Robbers game. We treat the versionwhere the robber can moveR >1 edges at a time, establishing a general upper bound ofn/ (1 o(1)) log n, where = 1 +1R, thus generalizing the best known upper bound for theclassical caseR= 1 due to Lu and Peng. We also show that in this case, the cop number ofann-vertex graph can be as large asn1 1R 2for finiteR, but linear innifRis infinite. ForR= 1, we study the directed graph version of the problem, and show that the cop number ofany strongly connected digraph onnvertices is at mostO(n(log logn)2/logn). Our approachis based on IntroductionThe game ofCops and Robbers , introduced by Nowakowski and Winkler [23] and independentlyby Quillot [24], is a perfect information game played on a fixed graphG.

2 There are two players,a set ofccops, for some integerc 1, and a robber . Initially, the cops are placed onto verticesof their choice inG(where more than one cop can be placed at a vertex). Then the robber , beingfully aware of the cops placement, positions himself in oneof the vertices ofG. Then the cops andthe robber move in alternate rounds, with the cops moving first; however, players are permitted toremain stationary on their turn if they wish. The players usethe edges ofGto move from vertex tovertex. The cops win and the game ends if eventually a cop steps into the vertex currently occupiedby the robber ; otherwise, , if the robber can elude the cops indefinitely, the robber numberofG, denoted byc(G), is the minimum number of cops needed to win onG.

3 This parameter was introduced by Aigner and Fromme [1], andthere is now an extensiveliterature on this fascinating problem. We direct the reader to the surveys [3], [16], and [12] fordetailed accounts of the known results. All results focus onconnected graphs, because the problemfor a disconnected graph obviously decomposes into the sum of the answers for each most well known open question in this area is Meyniel s conjecture, published by Frankl in[13]. It states that for every connected graphGonnvertices,O( n) cops are enough to win. Thisconjecture, if true, is best possible, as projective plane graphs (n-vertex graphs without cycles of Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, Research supported in part by NSF award DMS-0753472.)

4 School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University,Tel Aviv 69978, Israel, e-mail: supported in part by USA-Israel BSF grant 2006322,by grant 1063/08 from the Israel Science Foundation, and by aPazy memorial award. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15217, e-mail: 3 and 4, and with all degrees at leastc n) are easily seen to require at leastc ncops. Sofar, the progress towards establishing Meyniel s conjecture has been rather slow. Frankl [13] provedthe upper bound ofO(nlog logn/logn); some twenty years later Chiniforooshan [9] improved ittoO(n/logn). Finally, the upper bound ofn/2(1 o(1)) lognwas established by Lu and Peng [20],and very recently Scott and Sudakov [25] posted an alternative proof of this result.

5 Bounds onthe typical behavior of the cop number for the random graphGn,phave been obtained for variousvalues ofp=p(n) by Bollob as, Kun and Leader [7] and by Luczak and Pra lat [20]. Many otherversions and ramifications of the above described classicalsetting have been studied, such as theranged version in [8], limited visibility in [19], etc., butwe do not pursue them employ an approach based on the notion ofexpansion, which has had many applications inmathematics and theoretical computer science. Recall thata graph is said to be ac-expanderifevery subsetSof at mostn/2 vertices has|N(S)\S|> c|S|. In particular, using this approach weare able to provide another proof for the Lu-Peng bound mentioned also allows us to address the directed graph version of theCops and Robbers problem.

6 Thesetting here is a straightforward adaptation of the undirected setting described above, with theonly difference being that the players need to respect the direction of any edge while moving alongit. Problems for directed graphs (digraphs) are usually much more difficult. To the best of ourknowledge, there have been no results on this problem in thiscase. In Section 3, we observe thatthe essence of the problem is to consider onlystrongly connecteddigraphs, , those which havedirected paths from any vertex to any other vertex. We prove the following general upper strongly connected digraph onnvertices has cop number at mostO(n (log logn)2logn).We then use a purely expansion-based argument to provide an alternate proof of Lu and Peng sresult for general graphs [20].

7 Theorem connected graph onnvertices has cop number at mostn/2(1 o(1)) approach has the added advantage that it still works in the case when the robber movesfaster than the cops. Indeed, this setting was recently considered by [11]. (It is not an interestingproblem if a cop can move faster than the robber , because thenone cop is sufficient: he can chasedown the robber .) So we consider the case when the robber moves at speedR >1 and cop moves atspeed 1; the robber can take any walk of lengthRfrom his current position, but he is not allowedto pass through any vertex occupied by a cop. With our alternate approach, we are able to provean result analogous to that of Lu and Peng, but for a faster 1be a given finite constant, and let = 1 +1R.

8 In every connected graphonnvertices,n/ (1 o(1)) log ncops are sufficient to catch any robber who moves at that for the original caseR= 1, the constant is precisely 2. Therefore, thisextends all current best results in the traditional is also interesting to note that in the fast robber setting, the cop number can be drasticallydifferent. Indeed, Proposition in Section 5 exhibits ann-vertex graph for which the cop numberjumps from 2 to ( n) when the robber s speed increases from 1 to 2. For higher speeds, we alsoshow that the general lower bound climbs beyondn1/2, and even reaches (n) for an any given robber speedR >2, the following hold for sufficiently largen.(i)IfR < , there exists ann-vertex graph which requires at leastn1 1R 2cops.

9 (ii)IfR= , there exists ann-vertex graph which requires at our paper, we will omit floor and ceiling signs whenever they are not essential, toimprove clarity of presentation. All logarithms are in basee unless otherwise specified. Thefollowing asymptotic notation will be utilized extensively. For two functionsf(n) andg(n), we writef(n) g(n),f(n) =o(g(n)), org(n) = (f(n)) if limn f(n)/g(n) = 0, andf(n) =O(g(n)) org(n) = (f(n)) if there exists a constantMsuch that|f(n)| M|g(n)|for all sufficiently number of verticesnis assumed to be sufficiently large where PreliminariesPrevious attempts to solve the general case of this problem have relied on the following two obser-vations. Recall thatc(G) denotes the cop number a connectedn-vertex graph.

10 (i)Ifvis a vertex of maximum degree , thenc(G) 1 +c(G ), whereG is a connected graphwith at mostn 1 vertices.(ii)Ifv1v2.. vtis a geodesic ofG, thenc(G) 1 +c(G ), whereG is a connected graph with atmostn part (i), permanently station a cop atv. LetG[U1], .. , G[Uk] be the connectedcomponents ofG\({v} N(v)). Since the robber can never enter{v} N(v), he must stay inwhichever component he starts in, sayG[Uj]. The cops can pass through each other, so as long asthere are maxic(G[Ui]) other cops, they can all move intoG[Uj] and capture the robber there. As i|Ui|=n 1 , this completes the first part (ii), a result of Aigner and Fromme [1] shows that onecop is sufficient to patrol{v1.}