CS Seminar

Title: Cops, Robbers, and Barricades
Seminar: Computer Science
Speaker: Erin Meger, Université du Québec à Montréal
Contact: Vaidy Sunderam, vss@emory.edu
Date: 2021-06-14 at 1:00PM
Venue: https://emory.zoom.us/j/93995724437
Download Flyer Add to Calendar
Abstract: Combinatorial games, especially games on graphs, have become more popular as a research interest over the past few decades. Despite their fun nature, some deep conjectures still remain elusive. In this talk, we will focus on what is now a classic game on graphs, Cops and Robbers. We will discuss the history of the game, some basic results and a few variants. Mostly, we will focus on Cops, Robbers and Barricades, where the Robber is allowed to build vertex-barricades. We will include a rigorous characterization of the graphs where a single cop can win, as well as a complexity result for the problem in general.