CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Graph Searching Games - Part I
Org: Anthony Bonato (Ryerson University) and Danielle Cox (Mount Saint Vincent University)

ANTHONY BONATO, Ryerson University
Bounds and algorithms for graph burning  [PDF]

Graph burning models the spread of contagion in a network. The burning number of a graph $G$, written $b(G)$, measures the speed of the contagion. The Graph Burning Conjecture, which states that $b(G) \le \lceil \sqrt{n} \rceil$ for a connected graph of order $n$, remains open. We prove the conjecture for spider graphs.

Computing the burning number is NP-hard even for spiders and path forests. We present new approximation algorithms for graph burning, giving an approximation ratio of 3 for general graphs. We present an algorithm for trees with approximation ratio 2, and consider approximation schemes on path forests.

NANCY CLARKE, Acadia University
$\ell$-Visibility Cops and Robber  [PDF]

A variation of the Cops and Robber game is considered in which the cops can only see the robber when the distance between them is at most a fixed parameter $\ell$. The cops' strategy consists of a phase in which they need to ``see" the robber (i.e.~move within distance $\ell$), followed by a phase in which they capture the robber. We present a variety of results, including a characterization of those trees on which $k$ cops are sufficient to guarantee a win for all $\ell \geq 1$.


This is joint work with D.~Cox, C.~Duffy, D.~Dyer, S.L.~Fitzpatrick, & M.E.~Messinger.

SEAN ENGLISH, Ryerson University
Catching Robbers Quickly and Efficiently  [PDF]

Cops and Robbers is a game played on a graph in which a team of cops try to catch a moving robber. In this talk we will discuss cop throttling, in which we are concerned with catching the robber quickly. The capture time with $k$ cops, $\mathrm{capt}_k(G)$, is the length of the longest game of Cops and Robbers possible, assuming optimal play. The cop throttling number is given by \[ \mathrm{th}_c(G):=\min_{k}\{k+\mathrm{capt}_k(G)\}. \] We will give background on Cops and Robbers, and then show that the cop throttling number grows sublinearly with $|V(G)|$.

This project was joint work with Anthony Bonato.

NATASHA KOMAROV, St. Lawrence University
Containing a robber on a graph  [PDF]

We consider ``Containment'': a variation of the graph pursuit game of Cops and Robber in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop), and the cops win by ``containing'' the robber---that is, by occupying all of the edges incident with a vertex v while the robber is at v. We develop several bounds on the minimal number of cops required to contain a robber, in particular relating this number to the well-studied ``cop-number'' in the original Cops and Robber game. (Joint work with John Mackey of Carnegie Mellon University and Danny Crytser of St. Lawrence University.)