Wurden diese Färbespiele gelöst?

12

In dem Artikel "Über die Komplexität einiger Malvorlagen" gibt Bodlaender einige offene Fragen zur Komplexität der Entscheidung, ob Spieler 1 oder 2 in einigen Grafik-Malvorlagen eine Gewinnstrategie verfolgt. Weiß jemand, ob sie gelöst wurden?

1) In einem Spiel wählen zwei Spieler abwechselnd einen Scheitelpunkt in einer Grafik aus und färben ihn korrekt mit einer Farbe aus einer festen endlichen Menge. Der Verlierer ist der erste Spieler, der keinen Scheitelpunkt färben kann. In Schaefers Papier wird gezeigt, dass es mit 1 Farbe pspace-complete ist, und Bodlaender zeigt, dass es mit 2 Farben pspace-complete ist, gibt aber keine Antwort mit mehr Farbe. Ist es noch offen

2) In einer anderen Variante haben die Eckpunkte die Nummern 1..n. In der Runde eines Spielers muss er den Scheitelpunkt mit der niedrigsten Zahl, die noch nicht gefärbt wurde, richtig färben. Auch hier verwenden sie Farben aus einem festen Satz und der Verlierer ist der erste Spieler, der seinen Scheitelpunkt nicht färben kann. Bodlaender zeigt, dass es für allgemeine Grafiken vollständig ist. Er fragt, wer auf Bäumen gewinnt, ist das bekannt?

Vielen Dank

graph-colouring pspace two-player-games user32149
quelle
2
Warum fragst du Bodlaender nicht direkt? staff.science.uu.nl/~bodla101
Gamow

Antworten:

2

Es hört sich so an, als hätte dieses Papier etwas von dem, wonach Sie suchen: http://arxiv.org/abs/1202.5762

Die allgemeine Form der ersten Frage ist eine wirklich einfache Reduktion: Verwenden Sie die Farben {0, ..., n-1}, beginnen Sie mit einer Node Kayles-Instanz und erstellen Sie einen Scheitelpunkt für jede der Farben von 1 bis n-1, und verbinden Sie sich sie zu jedem ungefärbten Scheitelpunkt. Jetzt können diese Farben nicht gespielt werden und du spielst immer noch das Node Kayles-Spiel.

Kyle
quelle
Danke für den Link, ich werde mal schauen. In dieser Frage erlauben wir keine "Vorfärbung", daher dürfen wir nicht annehmen, dass einige Scheitelpunkte bereits eine Farbe haben. Das Spiel beginnt mit allen Scheitelpunkten, die nicht gefärbt sind.
User32149
Das macht Sinn, ändert aber die Frage nach der Härte. Für viele Spiele ist bekannt, welcher Spieler eine Gewinnstrategie von einer Anfangsposition aus hat, aber es ist nicht bekannt, welcher Spieler eine Gewinnstrategie auf einer allgemeinen Position hat. Nehmen wir zum Beispiel Hex. Hier hat der erste Spieler eine Gewinnstrategie. Aus einer allgemeinen Position heraus ist PSPACE-vollständig, wenn festgestellt wird, ob der nächste Spieler, der zieht, eine Gewinnstrategie hat.
Kyle
Ja du hast recht, ich hätte es in der ursprünglichen Frage klarstellen sollen. Ich spreche von der Komplexität der Berechnung, mit der ermittelt wird, wer in einem bestimmten Diagramm gewinnt, bevor Scheitelpunkte eingefärbt werden.
user32149
Das ist natürlich eine interessante Frage. Zumal Sie von einem allgemeinen Graphen sprechen und keine Anforderungen an dessen Struktur stellen. Ich würde mich auf jeden Fall interessieren, wenn Sie es herausfinden!
Kyle