O jogo Drácula

Antecedentes
Esta questão é motivada por um jogo de tabuleiro chamado 'Drácula'. Neste jogo, há um vampiro e quatro caçadores, o objetivo dos caçadores é capturar o vampiro. O jogo acontece na Europa. O jogo é o seguinte:
1. O jogador caçador coloca todos os caçadores nas cidades. Mais de um caçador pode ser colocado na mesma cidade.
2. O jogador de vampiros coloca o vampiro em uma cidade.
3. Os jogadores movem suas criaturas alternadamente para as cidades vizinhas.
4. O jogador caçador, por sua vez, pode mover quantos caçadores quiser.
5. A principal dificuldade é que o jogador vampiro sabe o tempo todo onde os caçadores estão, mas o jogador caçador conhece apenas a posição inicial do vampiro.
6. Quando um caçador e um vampiro se encontram em uma cidade, o jogador perde.

Pergunta
Para um dado gráfico e os números e , existe uma estratégia que garanta ao jogador caçador, que controla caçadores, capturar vampiros em menos de turnos? Pode-se supor que é plano. Este problema foi estudado? Algumas referências seriam apreciadas.n k n k $G$$n$$k$$n$$k$$G$

O jogo que você descreveu parece muito com o jogo de k Cops e 1 Robber, conforme descrito neste artigo por Clarke e Macgillivray: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . Basicamente, ele é jogado colocando k policiais e um ladrão nos vértices de um gráfico e pedindo aos policiais para pegá-lo movendo-se pelas bordas.

A principal diferença do seu jogo e essa é a visibilidade parcial dos caçadores, enquanto nos policiais e ladrões clássicos, os policiais sabem exatamente onde está o ladrão e vice-versa. Além disso, em policiais e ladrões, o tempo não é limitado.

Mesmo com informações completas, se o tempo não for limitado, foi demonstrado que determinar se os policiais de K podem capturar o ladrão em tempo finito quando o ladrão e os policiais jogam da melhor maneira possível é exponencial ( http://arxiv.org /abs/1309.5405 ) quando k não for corrigido. Portanto, como seu jogo é mais difícil de jogar para a polícia, acho que ele também não pode ser resolvido no tempo polinomial, quando o tempo não é limitado. Eu acho que o número de movimentos necessários para k policiais pegar um ladrão pode ser limitado acima, digamos c, e se o número de etapas k permitido aos caçadores for próximo desse número c, então o jogo de caçadores e vampiros seria pelo menos, mais difícil de resolver do que k policiais e ladrões (veja o artigo de Bonato et al.: O tempo de captura do gráfico).

Conforme observado por @MarcusRitt nos comentários, isso é conhecido como pesquisa de gráficos. Gostaria de acrescentar, no entanto, que a variante específica que você descreve (ou seja, relacionar o número de rodadas disputadas com o número de pesquisadores empregados) também foi investigada, o que não é observado no artigo da Wikipedia. Curiosamente, a transição do espaço de busca para o tempo de busca mantém as caracterizações do problema (introduzindo versões "duplas" apropriadas dos respectivos parâmetros).

Veja o artigo "Pesquisa de gráfico e tempo de pesquisa" de Brandenburg e Herrmann no SOFSEM 2006.

Se generalizarmos a condição do jogo, será igual ao jogo Cop-Robber da largura do caminho. O único relaxamento é que o ladrão pode se mover para qualquer vértice ele deseja, se houver um caminho limpo (nenhum policial ao longo desse caminho) de sua posição atual para . Em seguida, o número mínimo de policiais necessários para capturar o ladrão é a largura do caminho (G) - . Se os policiais puderem ver um ladrão em um jogo semelhante ao que eu disse, o número mínimo de policiais necessário para capturá-lo é igual à largura da árvore (G) - . Nos dois casos, existe um algoritmo polinomial para encontrar o ladrão por um fixov 1 1 $v$$v$$1$$1$$k$, também para gráficos planares, é possível aproximar o número de policiais (e obter a decomposição correspondente) em tempo polinomial. Talvez você esteja interessado em ler mais sobre as notas desta palestra.