Nouvelles directions dans le modèle «policiers-voleur» de fouilles des graphes

 

Benjamin Seamone

Collège Dawson

 

Domaine : structures abstraites

Programme de recherche pour les chercheurs de collège

Concours 2017-2018

Ce programme de recherche est dédié au développement de nouvelles directions dans le domaine de fouilles des graphes, et dans le modèle «policiers-voleur» en particulier. Le modèle est simple: un ensemble de policiers et un voleur se déplacent en alternance dans un réseau, les policiers cherchant à occuper la position du voleur, qui veut rester libre. Quatre variantes seront étudiées. Je considère le jeu dans lequel aucun agent ne peut rester sur place à son tour.

Ce changement de règle semble rendre certains outils connus pour analyser le jeu moins utiles, ce qui nous force à développer de nouvelles approches au jeu. Je veux également aborder le jeu habituel sur les graphes géométriques, en particulier ceux qui modélisent des réseaux ad hoc sans fil. Je vais aussi étudier le jeu des policiers-voleur sur des graphes infinis en regardant les diverses définitions de «capture».

Finalement, je vais étudier les jeux de policiers-voleur sur des graphes avec des sous-graphes induits interdits. Dans chacun des cas, je vais considérer les questions combinatoires (e.g. combien de policiers faut-il pour gagner sur un graphe donné?) et les questions algorithmiques (e.g. Quelle est la difficulté de décider combien de policier il faut pour gagner sur un graphe?).