Cops and Robbers from a distance

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance kk Cops and Robbers, where the cops win if at least one of them is of distance at most kk from the robber in GG. The cop number of a graph GG is the minimum number of cops needed to capture the robber in GG. The distance kk analogue of the cop number, written ck(G)ck(G), equals the minimum number of cops needed to win at a given distance kk. We study the parameter ckck from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded ck(G)ck(G) values and develop an O(n2s+3)O(n2s+3) algorithm for determining if ck(G)≤sck(G)≤s for ss fixed. We prove that if ss is not fixed, then computing ck(G)ck(G) is NP-hard. Upper and lower bounds are found for ck(G)ck(G) in terms of the order of GG. We prove that (nk)1/2+o(1)≤ck(n)=O(nlog(2nk+1)log(k+2)k+1), where ck(n)ck(n) is the maximum of ck(G)ck(G) over all nn-vertex connected graphs. The parameter ck(G)ck(G) is investigated asymptotically in random graphs G(n,p)G(n,p) for a wide range of p=p(n)p=p(n). For each k≥0k≥0, it is shown that ck(G)ck(G) as a function of the average degree d(n)=pnd(n)=pn forms an intriguing zigzag shape.