Enquêter dans les graphes

International audienceLes jeux combinatoires à deux joueurs impliquant des agents mobiles dans les graphes (e.g., jeu des gendarmes et du voleur, jeu du dominant éternel, etc.) ont été beaucoup étudiés car ils permettent, d'une part, de comprendre comment coordonner des individus afin de réaliser une tâche commune, et d'autre part d'étudier les propriétés structurelles des graphes. Outre la définition et l'étude d'un nouveau de ces jeux, une contribution importante de cet article est de montrer que la programmation linéaire permet de nouveaux progrès dans l'étude de ce type de jeux. Nous définissons le jeu dans lequel un premier agent, le Suspect, se déplace dans un graphe à vitesse s ≥ 2 à la recherche d'une position à distance au moins d + 1 de tous les autres agents, les Détectives, qui veulent le surveiller (i.e. s'assurer qu'il y ait toujours au moins un détective à distance au plus d du suspect). Etant donné un graphe G, le nombre minimum de détectives nécessaires pour satisfaire cet objectif est noté $gn_{s,d}(G)$. Le problème est de calculer $gn_{s,d}(G)$ ainsi qu'une stratégie correspondante pour les détectives. Ce jeu à deux joueurs (suspect et détectives) ressemble aux jeux de gendarmes et voleur et généralise celui du Dominan éternel. Nous étudions la complexité du calcul de $gn_{s,d}(G)$ et présentons des stratégies gagnantes pour les détectives dans diverses classes de graphes. Certaines de nos preuves sont combinatoires, tandis que d'autres sont basées sur l'utilisation de la Programmation Linéaire dont nous espérons démontrer ainsi l'intérêt dans l'analyse de ce type de jeux