Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université de Montréal

$40,000.00

Graph searching - structural properties

FY 2022-23

Summary
Cops-and-robbersgames have been studied since the 1980's, especially after thediscovery of connections with various graph widths. Algorithmic and complexity questionsseem to dominate the field because of applications in optimisation, among other things, but some basic questions remain unanswered: the cop-number of a graph, a characterisation of k-cop-win graphs, the length of an optimal game, etc.We wish to study these basic questions for the game as defined by Nowakowski andWinkler, and by Quillot, and to consider new models. Our graph theorygroup (two researchers, up to five students) has been studying theinfluence of loops on the number of cops needed (there are graphs that alternate between cop-winand not with the addition of loops one by one starting with a loopless graph). In the summer 2016we have worked on a version of the game in which the cops have to catchthe robber at a specified vertex (this is no longer a total knowledge game, the robber does not know the vertex). We wish to continuestudying these variants where we have some preliminary results. Our algorithm to decide whether k cops can catch r robbers on a given(finite) graph is used in robotics for robot motion planning and we think that specifying a capture vertex and an algorithm to describe a strategy would also be useful to roboticists.Further, we would like to generalise by considering not only the number of cops needed to catch therobber, but also the cost of doing so. Perhaps having a few more copswould cost less? The main problem here is defining the cost. We have considered severalpossibilities and will continue in this direction.Since finite regular graphs are not cop-win unless complete, Cayley graphs have not been much considered. We think theyare worth looking at again, especially in connection with some of the models (vaguely) describedabove.Last, we wish to study cop-win infinite graphs. We believe that understanding the infinite brings an understanding of the finite. Cops-and-robbers games on infinite graphs are different (there are many cop-win vertex transitive infinite graphs but only complete finite ones). Arecent paper by Lehner suggests that we have been looking the problem backwards, overlooking the fact that the reverse of a well-order is a well-order for finite graphs but not for infinite ones. Thus any attempt atcharacterising infinite cop-win graphs through an ordering like that for finite ones is doomed tofailure. This indicates that even forfinite graphs we should reconsider our approach. We propose to do just that.A part of the study of infinite cop-win graphs are the implications to structural properties of graphs. Generalising aconstruction from our 2009 paper we have examples of universal countable graphs that aredifferent from the unique (ultra)homogeneous countable graph (the random, or Rado, graph).We wish to continue studying such structures.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-05065
Name nom
Hahn, Gena
Department département
Informatique et recherche opérationnelle - Informatique et recherche opérationnelle
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2017
Award amount
40000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:5;6
Partie
2
Nb partie
6
Application title
Graph searching - structural properties
Application summary
Cops-and-robbersgames have been studied since the 1980's, especially after thediscovery of connections with various graph widths. Algorithmic and complexity questionsseem to dominate the field because of applications in optimisation, among other things, but some basic questions remain unanswered: the cop-number of a graph, a characterisation of k-cop-win graphs, the length of an optimal game, etc.We wish to study these basic questions for the game as defined by Nowakowski andWinkler, and by Quillot, and to consider new models. Our graph theorygroup (two researchers, up to five students) has been studying theinfluence of loops on the number of cops needed (there are graphs that alternate between cop-winand not with the addition of loops one by one starting with a loopless graph). In the summer 2016we have worked on a version of the game in which the cops have to catchthe robber at a specified vertex (this is no longer a total knowledge game, the robber does not know the vertex). We wish to continuestudying these variants where we have some preliminary results. Our algorithm to decide whether k cops can catch r robbers on a given(finite) graph is used in robotics for robot motion planning and we think that specifying a capture vertex and an algorithm to describe a strategy would also be useful to roboticists.Further, we would like to generalise by considering not only the number of cops needed to catch therobber, but also the cost of doing so. Perhaps having a few more copswould cost less? The main problem here is defining the cost. We have considered severalpossibilities and will continue in this direction.Since finite regular graphs are not cop-win unless complete, Cayley graphs have not been much considered. We think theyare worth looking at again, especially in connection with some of the models (vaguely) describedabove.Last, we wish to study cop-win infinite graphs. We believe that understanding the infinite brings an understanding of the finite. Cops-and-robbers games on infinite graphs are different (there are many cop-win vertex transitive infinite graphs but only complete finite ones). Arecent paper by Lehner suggests that we have been looking the problem backwards, overlooking the fact that the reverse of a well-order is a well-order for finite graphs but not for infinite ones. Thus any attempt atcharacterising infinite cop-win graphs through an ordering like that for finite ones is doomed tofailure. This indicates that even forfinite graphs we should reconsider our approach. We propose to do just that.A part of the study of infinite cop-win graphs are the implications to structural properties of graphs. Generalising aconstruction from our 2009 paper we have examples of universal countable graphs that aredifferent from the unique (ultra)homogeneous countable graph (the random, or Rado, graph).We wish to continue studying such structures.