We show that the expected time for a smart "cop"' to catch a drunk "robber" on an $n$-vertex graph is at most $n + {\rm o}(n)$. More precisely, let $G$ be a simple, connected, undirected graph with distinguished points $u$ and $v$ among its $n$ vertices. A cop begins at $u$ and a robber at $v$; they move alternately from vertex to adjacent vertex. The robber moves randomly, according to a simple random walk on $G$; the cop sees all and moves as she wishes, with the object of "capturing" the robber—that is, occupying the same vertex—in least expected time. We show that the cop succeeds in expected time no more than $n {+} {\rm o}(n)$. Since there are graphs in which capture time is at least $n {-} o(n)$, this is roughly best possible. We note also that no function of the diameter can be a bound on capture time.
@article{10_37236_3398,
author = {Natasha Komarov and Peter Winkler},
title = {Capturing the drunk robber on a graph},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/3398},
zbl = {1298.05224},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3398/}
}
TY - JOUR
AU - Natasha Komarov
AU - Peter Winkler
TI - Capturing the drunk robber on a graph
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3398/
DO - 10.37236/3398
ID - 10_37236_3398
ER -
%0 Journal Article
%A Natasha Komarov
%A Peter Winkler
%T Capturing the drunk robber on a graph
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3398/
%R 10.37236/3398
%F 10_37236_3398
Natasha Komarov; Peter Winkler. Capturing the drunk robber on a graph. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/3398
