Capturing the drunk robber on a graph

MaRDI QIDQ406701zbMATH OpenFDO

Authors Natasha Komarov, Peter Winkler

Publication date 9 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.4559, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

pursuit games on graphsrandom walks

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: We show that the expected time for a smart "cop" to catch a drunk "robber" on an $n$-vertex graph is at most $n+mo(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+mo(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.

Review text

Summary: We show that the expected time for a smart ``cop to catch a drunk ``robber on an \(n\)-vertex graph is at most \(n +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+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.

Recommendations

• Chasing a drunk robber in many classes of graphs
• Some remarks on cops and drunk robbers
• Cop vs. gambler
• Cops and invisible robbers: the cost of drunkenness
• Cops and robbers in a random graph

Cites work

• A note on \(k\)-cop, \(l\)-robber games on graphs
• A probabilistic approach to Carne's bound
• Collisions Among Random Walks on a Graph
• Gibbs measures and dismantlable graphs
• scientific article; zbMATH DE number 3934148 (Why is no real title available?)
• Maximum diameter of regular digraphs
• Maximum hitting time for random walks on graphs
• On cop-win graphs
• On Cumulative Sums of Random Variables
• On the cop number of a graph
• Projective Planes
• The capture time of a graph
• Vertex-to-vertex pursuit in a graph

Cited in

(7)

• Some remarks on cops and drunk robbers
• Chasing a drunk robber in many classes of graphs
• Cop vs. gambler
• TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS
• Selfish cops and passive robber: qualitative games
• Tipsy cop and tipsy robber: collisions of biased random walks on graphs
• General cops and robbers games with randomness

This page was built for publication: Capturing the drunk robber on a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q406701)