PhD Defence: Localization, Burning, and Constraint Satisfaction

Candidate: John Marcoux

Supervisors: Dr. Anthony Bonato and Dr. Dejan Delic 

Abstract
We first consider the Localization game, in which a team of cops attempts to locate a moving, invisible robber on a graph using distance probes. We study a variant of the game in which the cops’ distance probes cannot distinguish distances beyond a fixed threshold, which we refer to as the visibility parameter. We first study the game on trees, with the visibility parameter a function of the tree’s radius. We determine the asymptotics required of this function to ensure only a constant number of cops are required. We also consider the problem of subdividing a tree in order to only require a single cop. We show that, as long as the visibility parameter is at least 2, such a subdivision always exists.

In Chapter 3 we study a two player variant of the burning problem, a well studied problem where a single player attempts to spread a contagion through a graph as quickly as possible. In our variant, a second player restricts the first player from prolonging the process. We first present a preliminary study of this process on paths and general graphs, and introduce a class of graphs in which the first player can play optimally while ignoring the second player’s strategy. We then give an in-depth study of various Cartesian products with a focus on hypercubes and square grids. We give exact values for certain cases on the hypercube using a variant of Sperner sets and tight bounds for all cases on the square grid. Finally, we show that the problem of determining the length of this game is a PSPACE complete problem.

In Chapter 4, we study the constraint satisfaction problem. We introduce a new type of core condition and show that, if we assume the instance satisfies this core condition, then the problem is in a particular subclass of logspace with counting. We conclude with some open problems in Chapter 5.