Das Dracula-Spiel

Hintergrund
Diese Frage wird durch ein Brettspiel namens "Dracula" motiviert. In diesem Spiel gibt es einen Vampir und vier Jäger. Der Zweck der Jäger ist es, den Vampir zu fangen. Das Spiel findet in Europa statt. Das Spiel sieht folgendermaßen aus:
1. Der Jägerspieler setzt alle Jäger in Städte. In einer Stadt können mehrere Jäger untergebracht werden.
2. Der Vampirspieler setzt den Vampir in eine Stadt.
3. Die Spieler bewegen ihre Kreaturen abwechselnd in die Nachbarstädte.
4. Der Jäger, der an der Reihe ist, darf so viele Jäger ziehen, wie er möchte.
5. Die Hauptschwierigkeit besteht darin, dass der Vampirspieler die ganze Zeit weiß, wo sich die Jäger befinden, aber der Jägerspieler nur die Startposition des Vampirs kennt.
6. Wenn sich ein Jäger und der Vampir in einer Stadt treffen, verliert der Vampirspieler.

Frage Gibt es
für ein gegebenes Diagramm und die Zahlen und eine Strategie, die dem Jägerspieler, der Jäger kontrolliert, garantiert , Vampire in weniger als Runden zu fangen ? Es kann angenommen werden, dass planar ist. Wurde dieses Problem untersucht? Einige Referenzen wären dankbar.$G$$n$$k$$n$$k$$G$

Das Spiel, das Sie beschrieben haben, ähnelt dem Spiel von k Cops und 1 Robber, wie in diesem Artikel von Clarke und Macgillivray beschrieben: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . Grundsätzlich wird gespielt, indem man k Polizisten und einen Räuber auf die Eckpunkte eines Graphen setzt und die Polizisten auffordert, den Räuber zu fangen, indem sie sich entlang der Ränder bewegen.

Der Hauptunterschied zu Ihrem Spiel und diesem ist die teilweise Sichtbarkeit der Jäger, während bei klassischen Bullen und Räubern die Bullen genau wissen, wo sich der Räuber befindet und umgekehrt. Auch bei Bullen und Räubern ist die Zeit nicht begrenzt.

Selbst mit vollständiger Information, wenn die Zeit nicht begrenzt ist, hat sich gezeigt, dass die Bestimmung, ob k-Cops den Räuber in endlicher Zeit einfangen könnten, wenn der Räuber und die Cops optimal spielen, exponentiell abgeschlossen ist ( http://arxiv.org) /abs/1309.5405 ) wenn k nicht festgelegt ist. Da Ihr Spiel für die Bullen schwieriger zu spielen ist, kann es vermutlich auch nicht in polynomieller Zeit gelöst werden, wenn die Zeit nicht begrenzt ist. Ich denke, die Anzahl der Züge, die k Polizisten benötigen, um einen Räuber zu fangen, kann wie folgt eingegrenzt werden: c. Wenn die Anzahl der Schritte, die k den Jägern erlaubt sind, in der Nähe von c liegt, wäre dies das Spiel zwischen Jägern und Vampiren Mindestens so schwer zu lösen wie k Bullen und Räuber (siehe Artikel von Bonato et al.: Die Erfassungszeit der Grafik).

Wie von @MarcusRitt in den Kommentaren erwähnt, wird dies als Diagrammsuche bezeichnet. Ich möchte jedoch hinzufügen, dass die spezifische Variante, die Sie beschreiben (dh die Anzahl der gespielten Runden mit der Anzahl der beschäftigten Sucher in Beziehung setzt), ebenfalls untersucht wurde, was im Wikipedia-Artikel nicht vermerkt ist. Interessanterweise behält der Übergang vom Suchraum zur Suchzeit die Charakterisierung des Problems bei (durch Einführung geeigneter "dualer" Versionen der jeweiligen Parameter).

Siehe den Artikel "Graphensuche und Suchzeit" von Brandenburg und Herrmann auf der SOFSEM 2006.

$v$$v$$1$$1$$k$Auch für ebene Graphen ist es möglich, die Anzahl der Cops (und dann die entsprechende Zerlegung) in Polynomzeit zu approximieren. Vielleicht möchten Sie mehr aus diesem Skript lesen .