Pursuit and evasion from a distance: algorithms and bounds
Anthony Bonato, Ehsan Chiniforooshan · 2009
Cops and Robber is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robber, distance k Cops and Robber, where the cops win if they are distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written ck(G), equals the minimum number of cops needed to win at a given distance k. We supply a classification result for graphs with bounded ck(G) values and develop an O(n2s+3) algorithm for determining if ck(G) ≤ s. In the case k = 0, our algorithm is faster than previously known algorithms. Upper and lower bounds are found for ck(G) in terms of the order of G. We prove that where ck(n) is the maximum of ck(G) over all n-node connected graphs.