2024 CMS Winter Meeting
Vancouver/Richmond, Nov 29 - Dec 2, 2024
The Theory of Pursuit-Evasion Games
Org: Rylo Ashmore (Memorial University of Newfoundland), Danny Dyer (Memorial University of Newfoundland) and Erin Meger (Queen's University)
[PDF]
Org: Rylo Ashmore (Memorial University of Newfoundland), Danny Dyer (Memorial University of Newfoundland) and Erin Meger (Queen's University)
[PDF]
- RYLO ASHMORE, Memorial University of Newfoundland
Herding logical cats with Rabin’s Theorem [PDF]
-
In the game of Cat Herding on a graph, one player (the herder) will
omnipresently delete edges, while the other player (the cat) is on a vertex
of the graph, and will move along any path to a new vertex. The cat’s
objective is to avoid capture, while the herder tries to hasten it. In an
optimally played game on a finite graph, the number of cuts the herder
made to isolate the cat is the cat number of the graph.
We discuss automata theory, formal logic, and how these ideas can be used to solve an infinite version of the cat herding game. In particular, we find an equivalence between certain logical sentences and cat-win struc- tures. Using this equivalence with Rabin’s Theorem, we obtain a finite time algorithm for identifying cat-win infinite trees and an explicit (trans- finite) herder strategy for herder-win infinite trees. Time-permitting, we may also discuss applications of automatatic techniques to the firefighting problem.
- ALEX CLOW, Simon Fraser University
Eternal Distance-k Domination in Trees [PDF]
-
This talk considers the eternal distance-$k$ domination problem, a variant of the eternal domination problem where guards can move any distance $t \in \{0,1,\dots, k\}$ on their turn. We prove upper and lower bounds for the eternal distance-$k$ domination number of a graph in terms of order, maximum degree, and $k$, before showing that both bounds are tight for trees. The rest of the talk will present open conjectures regarding the eternal distance-$k$ domination number of trees, along with evidence to support these conjectures.
\vspace{0.5cm} This is joint work with Christopher van Bommel (University of Guelph).
- STEPHEN FINBOW, St. Francis Xavier University
- MELISSA HUGGAN, Vancouver Island University
Cops and Attacking Robbers: A Shift in Power [PDF]
- MELISSA HUGGAN, Vancouver Island University
-
The game of Cops and Attacking Robbers was first introduced in 2013 by Bonato, Finbow, Gordinowicz, Haidar, Kinnersley, Mitsche, Pralat and Stacho. In this Cops and Robbers game variant, the robber is empowered to attack a cop in the same way a cop can capture the robber. In a graph G, the number of cops required to capture a robber in the Cops and Attacking Robbers game is denoted by cc(G). In this talk, we will discuss new results for graphs with specific cycle constraints. We will conclude the talk with several open problems. This is joint work with Alex Clow and Margaret-Ellen Messinger.
- MEAGAN MANN, Queen's University
A Data-Centric Approach to Cops and Robbers [PDF]
-
Meyniel (1985) conjectured that the cop number of any connected graph $G$ of order $n$ is bounded by $O(\sqrt{n})$. In this talk, I introduce a data-centric approach to explore this conjecture by analyzing key properties of graphs, such as genus, tree-width, and planarity. Using computational techniques and automated planning tools, we filter out trivial Meyniel satisfiable graphs to focus on more complex cases. I will walk through the algorithm we developed, which processes graphs into \textsc{networkX} objects, accumulates properties, and calculates the cop number using a PDDL planner (\textsc{Planning Domain Definition Language}). I will then discuss how we plan to scale this approach to handle larger datasets.
- JOY MORRIS, University of Lethbridge
Cop numbers of generalised Petersen graphs [PDF]
-
It was previously proved by Ball et al. (2015) that the cop number of any generalised Petersen graph is at most 4. I will present results that determine the cop number for all of the known generalised Petersen graphs that actually have cop number 4, and that place them in the context of infinite families. The same proof techniques also show that any graph with girth at least 9 and minimum degree $\delta$ has cop number strictly greater than $\delta$; this represents a minor improvement to this special case of Frankl’s more general bound. My talk is based on joint work with Harmony Morris, Tigana Runte, and Adrian Skelton.
- TODD MULLEN, University of Prince Edward Island
An Empowered Robber [PDF]
-
In this talk, multiple variants of Cops and Robber are discussed that empower the Robber to evade teams of cops on even very basic graphs. We discuss the rule changes required to increase the cop number of a given graph and also the reasons why one may favour a variant which empowers the Robber instead of the Cops. In particular, we focus on the Cops and Robber and Tunnels variant which gives the Robber the ability to make fundamental changes to the graph through creating or even destroying edges.
- AMANDA PORTER, University of Victoria
Hyperopic Cops and Robbers: Cops with Vision Problems [PDF]
-
Hyperopic Cops and Robbers (introduced by Bonato, Clarke, Finbow, Mc Inerney, and Messinger in 2017) is a variant of the original game of Cops and Robbers. In this version, the cops are farsighted making the robber invisible if inside the common neighbourhood of all of the cops. In this talk, we investigate the hyperopic cop number of a graph which is the minimum number of hyperopic cops required to guarantee the capture of the robber. First, we will explore results that upperbound the hyperopic cop number of a general graph and move to consider graphs of diameter two. We will conclude with open questions that would improve upon known bounds. This is joint work completed with Nancy Clarke, Stephen Finbow, and Margaret-Ellen Messinger.
- ASIYEH SANAEI, Kwantlen Polytechnic University
Damage Number of Small Graphs [PDF]
-
The damage variation in the game of Cops and Robber on graphs is a version of the game in which the robber damages each distinct vertex that he moves onto without capture. The parameter ``damage number of a graph'' is then the minimum number of unique vertices of the graph that can be damaged by the robber. It has been shown that in almost all graphs the damage number is less than $\frac{n}{2}$, where $n$ is the order of the graph, and upper bounds on the damage number of the graphs with $n\le 8$ are known. After introduction and a brief review of the existing results, recent developments on the damage number of the graphs of order nine will be presented.
- BOTING YANG, University of Regina
Constrained Graph Searching on Trees [PDF]
-
In this talk, we consider edge search and fast search with constraints on vertices.
These two graph search models were introduced by Megiddo et al. (1988) and Dyer et al. (2008), respectively. We give polynomial time algorithms for computing the minimum number of searchers to capture robber on trees under different constraints.