El juego de Drácula

Antecedentes
Esta pregunta está motivada por un juego de mesa llamado 'Drácula'. En este juego hay un vampiro y cuatro cazadores, el objetivo de los cazadores es atrapar al vampiro. El juego tiene lugar en Europa. El juego tiene el siguiente aspecto:
1. El jugador cazador coloca a todos los cazadores en las ciudades. Se puede colocar más de un cazador en la misma ciudad.
2. El jugador vampiro pone al vampiro en una ciudad.
3. Los jugadores mueven alternativamente sus criaturas a las ciudades vecinas.
4. El jugador cazador en su turno puede mover tantos cazadores como quiera.
5. La principal dificultad es que el jugador vampiro sabe todo el tiempo dónde están los cazadores, pero el jugador cazador solo conoce la posición inicial del vampiro.
6. Cuando un cazador y el vampiro se encuentran en una ciudad, el vampiro pierde.

Pregunta
Para un gráfico dado y números n y k , ¿existe una estrategia que garantice que el jugador cazador, que controla n cazadores, atrape vampiros en menos de k turnos? Se puede suponer que G es plano. ¿Se ha estudiado este problema? Se agradecerán algunas referencias.$G$$n$$k$$n$$k$$G$

El juego que has descrito se parece mucho al juego de k Cops y 1 Robber, como se describe en este artículo de Clarke y Macgillivray: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . Básicamente, se juega colocando k policías y un ladrón en los vértices de un gráfico y pidiéndole a los policías que atrapen al ladrón moviéndose a lo largo de los bordes.

La principal diferencia de tu juego y este es la visibilidad parcial de los cazadores, mientras que en los policías y ladrones clásicos, los policías saben exactamente dónde está el ladrón y viceversa. Además, en policías y ladrones el tiempo no es limitado.

Incluso con información completa, si el tiempo no es limitado, se ha demostrado que determinar si los policías k podrían capturar al ladrón en un tiempo finito cuando el ladrón y los policías juegan de manera óptima es un tiempo exponencial completo ( http://arxiv.org /abs/1309.5405 ) cuando k no está arreglado. Por lo tanto, dado que su juego es más difícil de jugar para los policías, supongo que tampoco se puede resolver en tiempo polinómico cuando el tiempo no es limitado. Creo que la cantidad de movimientos necesarios para que los policías k atrapen a un ladrón se puede acotar arriba, por decir c, y si la cantidad de pasos k permitidos para los cazadores es cercana a este número c, entonces el juego de cazadores y vampiros sería al menos tan difícil de resolver como k policías y ladrones (ver el artículo de Bonato et al.: El tiempo de captura del gráfico).

Como señaló @MarcusRitt en los comentarios, esto se conoce como búsqueda de gráficos. Sin embargo, me gustaría agregar que la variante específica que usted describe (es decir, relacionar el número de rondas jugadas con el número de buscadores empleados) también ha sido investigada, lo que no se menciona en el artículo de Wikipedia. Curiosamente, la transición del espacio de búsqueda al tiempo de búsqueda conserva las caracterizaciones del problema (al introducir versiones "duales" apropiadas de los parámetros respectivos).

Consulte el artículo "Búsqueda gráfica y tiempo de búsqueda" de Brandenburg y Herrmann en SOFSEM 2006.

$v$$v$$1$$1$$k$, también para gráficos planos es posible aproximar el número de policías (y luego obtener la descomposición correspondiente) en tiempo polinómico. Puede estar interesado en leer más de estas notas de la conferencia.