Réunion d'été SMC 2019
Regina, 7 - 10 juin 2019
Org: Danny Dyer (Memorial) et Ryan Tifenbach (Mount Allison)
[PDF]
- ANTHONY BONATO, Ryerson University
Limited information Cops and Robbers games [PDF]
-
In limited information variants of Cops and Robbers games, the robber is either invisible or partially visible during gameplay. Although they were studied for decades, there is now a renewed interest in limited information games among graph theorists and theoretical computer scientists. We present results on two recent variants, the localization game and Hyperopic Cops and Robbers. In the localization game, we settle a recent conjecture of Bosek et al. by providing an upper bound on the localization number as a function of the chromatic number.
- ANDREA BURGESS, University of New Brunswick Saint John
Cops that surround a robber [PDF]
-
In this talk, we introduce a variant of the game of cops and robber in which the winning condition for the cops is to ``surround'' the robber by occupying all of his adjacent vertices. The surrounding cop number $s(G)$ is the minimum number of cops required to guarantee that the cops have a winning strategy. Trivially, $s(G)$ is bounded below by $\delta(G)$, the minimum degree of $G$. It is easy to see that the cop number $c(G)$ is also a lower bound for $s(G)$, since once the cops surround the robber they can occupy his position in the next round; thus $s(G)$ cops win the traditional cops and robber game. While $s(G)$ is close to $\max \{ c(G), \delta(G)\}$ for some graph classes, the difference between $s(G)$ and both $c(G)$ and $\delta(G)$ can be arbitrarily large.
We present some results and observations on the surrounding cops and robber game. This includes an exploration of the game for various classes of graphs, such as generalized Petersen graphs, incidence and intersection graphs of designs, and certain product graphs.
This is joint work with Rosalind Cameron, Nancy Clarke, Peter Danziger and David Pike.
- RYAN HAYWARD, University of Alberta
Searching for Winning Strategies in Hex [PDF]
-
Hex is the classic 2-player alternate-turn connection game played on a hexagonal n-by-by grid. John Nash famously used strategy-stealing to prove that there exists a winning strategy for the first player, but finding explicit strategies for arbitrary Hex positions is P-space-complete. To date, such strategies are known only up to 10-by-10.
Go expert Jing Yang was first to find such strategies for 7-by-7 through 9-by-9. 10-by-10 was first solved by computer. I will show one way to find strategies both for arbitrary positions. I will also discuss a recent attempt to find new empty-board 10-by-10 and 11-by-11 strategies.
This is joint work with Chao Gao, Wai Yi Low, Justin Francis, Jarrett Knauer and Scott Dupasquier. For more on Hex, see Hex, the Full Story (Hayward and Toft, CRC Press, 2019).
- SHAHIN KAMALI, University of Manitoba
On the complexity of burning and broadcasting problems [PDF]
-
Given an unweighted, undirected graph, there are many broadcasting and burning protocols for the dissemination of information in (or burning of) the graph. We review some of these protocols from an algorithmic point of view. The focus of the talk will be on telephone broadcasting, the firefighter problem, and the graph burning problem. Finding optimal dissemination schemes is NP-hard in all of these problems. Despite similarities like this, these problems have different behaviour with respect to approximation algorithms. We review a recently-introduced algorithm for the graph burning problem which has a constant approximation factor. Meanwhile, the existing hardness result indicates that the firefighter problem is APX-hard. For telephone broadcasting, the presence of an approximation algorithm with constant factor is an open problem. We review the existing approximation algorithms for telephone broadcasting and pose a few open problems relating the burning and broadcasting problems.
- DAVID PIKE, Memorial University of Newfoundland
The Firebreak Problem [PDF]
-
Suppose we have a network that is represented by a graph $G$. Potentially a fire (or other type of contagion) might erupt at some vertex of $G$.
We are able to respond to this outbreak by establishing a firebreak at $k$ other vertices of $G$, so that the fire cannot pass through these
fortified vertices. The question that now arises is which $k$ vertices will result in the greatest number of vertices being saved from the fire,
assuming that the fire will spread to every vertex that is not fully behind the $k$ vertices of the firebreak. This is the essence of the
Firebreak decision problem, which we establish is intractable on the class of split graphs as well as on the class of bipartite graphs, but can
be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection
graphs.
This is joint work with Kathleen Barnetson, Andrea Burgess, Jessica Enright, Jared Howell, and Brady Ryan.