Le jeu Dracula

Contexte
Cette question est motivée par un jeu de société appelé «Dracula». Dans ce jeu, il y a un vampire et quatre chasseurs, le but des chasseurs est d'attraper le vampire. Le jeu se déroule en Europe. Le jeu se présente comme suit:
1. Le joueur chasseur place tous les chasseurs dans les villes. Plus d'un chasseur peut être placé dans la même ville.
2. Le joueur vampire place le vampire dans une ville.
3. Les joueurs déplacent alternativement leurs créatures vers les villes voisines.
4. Le joueur chasseur peut déplacer à son tour autant de chasseurs qu'il le souhaite.
5. La principale difficulté est que le joueur vampire sait tout le temps où se trouvent les chasseurs, mais le joueur chasseur ne connaît que la position de départ du vampire.
6. Lorsqu'un chasseur et le vampire se rencontrent dans une ville, le joueur vampire perd.

Question
Pour un graphique donné et les nombres n et k , y a-t-il une stratégie qui garantit au joueur chasseur, qui contrôle n chasseurs, d'attraper le vampire en moins de k tours? On peut supposer que G est plan. Ce problème a-t-il été étudié? Quelques références seraient appréciées.$G$$n$$k$$n$$k$$G$

Le jeu que vous avez décrit ressemble beaucoup au jeu de k Cops et 1 Robber, comme décrit dans cet article de Clarke et Macgillivray: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . Fondamentalement, il est joué en plaçant k flics et un voleur sur les sommets d'un graphique et en demandant aux flics d'attraper le voleur en se déplaçant le long des bords.

La principale différence avec votre jeu et celui-ci est la visibilité partielle des chasseurs, alors que chez les flics et les voleurs classiques, les flics savent exactement où se trouve le voleur et vice-versa. De plus, chez les flics et les voleurs, le temps n'est pas limité.

Même avec des informations complètes, si le temps n'est pas limité, il a été démontré que déterminer si les k-cops pourraient éventuellement capturer le voleur en temps fini lorsque le voleur et les flics jouent de manière optimale est un temps exponentiel complet ( http://arxiv.org /abs/1309.5405 ) lorsque k n'est pas fixe. Par conséquent, comme votre jeu est plus difficile à jouer pour les flics, je suppose qu'il ne peut pas non plus être résolu en temps polynomial lorsque le temps n'est pas limité. Je pense que le nombre de mouvements nécessaires pour que k flics attrapent un voleur peut être limité ci-dessus, disons c, et si le nombre de pas k permis aux chasseurs est proche de ce nombre c, alors le jeu des chasseurs et des vampires serait au moins aussi difficile à résoudre que k flics et voleur (voir l'article de Bonato et al.: Le temps de capture du graphe).

Comme indiqué par @MarcusRitt dans les commentaires, cela s'appelle la recherche de graphiques. Je voudrais ajouter, cependant, que la variante spécifique que vous décrivez (c'est-à-dire, reliant le nombre de tours joués avec le nombre de chercheurs employés) a également été étudiée, ce qui n'est pas noté dans l'article de Wikipedia. Il est intéressant de noter que la transition de l'espace de recherche au temps de recherche conserve les caractérisations du problème (en introduisant des versions "doubles" appropriées des paramètres respectifs).

Voir l'article "Recherche de graphes et temps de recherche" de Brandebourg et Herrmann au SOFSEM 2006.

Si nous généralisons la condition de jeu, elle est égale au jeu Cop-Robber de largeur de chemin. La seule relaxation est que le voleur peut se déplacer vers n'importe quel sommet$v$ il veut s'il y a un chemin propre (pas de flic le long de ce chemin) de sa position actuelle à $v$. Ensuite, le nombre minimum de flics nécessaires pour attraper le voleur est la largeur du chemin (G) -$1$. Si les flics sont autorisés à voir un voleur dans un jeu similaire à celui que j'ai indiqué, alors le nombre minimum de flics nécessaires pour attraper le voleur est égal à la largeur de l'arbre (G) -$1$. Dans les deux cas, il existe un algorithme polynomial pour trouver le voleur pour un$k$, également pour un graphe planaire, il est possible d'approximer le nombre de flics (puis d'obtenir la décomposition correspondante) en temps polynomial. Peut-être êtes-vous intéressé à lire plus de ces notes de cours.