Czy te gry kolorowanki zostały rozwiązane?

12

W artykule „O złożoności niektórych gier koloryzujących” Bodlaender podaje kilka otwartych pytań na temat złożoności decydowania, czy gracz 1 lub 2 ma strategię wygrywającą w niektórych grach kolorystycznych. Czy ktoś wie, czy zostały rozwiązane?

1) W jednej grze dwóch graczy wybiera kolejno jeden wierzchołek na wykresie i odpowiednio koloruje go kolorem ze stałego zestawu skończonego. Przegrany jest pierwszym graczem, który nie jest w stanie pokolorować wierzchołka. Na papierze Schaefera pokazano, że jest wypełniony spacjami z 1 kolorem, a Bodlaender pokazuje, że jest wypełniony spacjami z 2 kolorami, ale nie odpowiada na więcej kolorów. Czy to jest nadal otwarte?

2) W innej odmianie wierzchołki mają liczby 1..n. Podczas tury gracz musi odpowiednio pokolorować wierzchołek o najniższej liczbie, która nie została jeszcze pokolorowana. Ponownie używają kolorów z ustalonego zestawu, a przegrany jest pierwszym graczem, który nie jest w stanie pokolorować swojego wierzchołka. Bodlaender pokazuje, że jest on wypełniony spacjami dla ogólnych wykresów. Pyta, kto wygrywa na drzewach, czy to wiadomo?

Dzięki

użytkownik32149
źródło
2
Dlaczego nie zapytasz bezpośrednio Bodlaendera? staff.science.uu.nl/~bodla101
Gamow

Odpowiedzi:

2

Wygląda na to, że ten artykuł zawiera część tego, czego szukasz: http://arxiv.org/abs/1202.5762

Ogólna forma pierwszego pytania to naprawdę prosta redukcja: używając kolorów {0, ..., n-1}, zacznij od instancji Node Kayles i utwórz wierzchołek dla każdego z kolorów od 1 do n-1 i połącz je do każdego bezbarwnego wierzchołka. Teraz nie można grać w te kolory i nadal grasz w grę Node Kayles.

Kyle
źródło
Dzięki za link, spojrzę. W tym pytaniu nie zezwalamy na „wstępne kolorowanie”, więc nie możemy zakładać, że niektóre wierzchołki mają już kolor. Gra rozpoczyna się od wszystkich kolorowych wierzchołków.
user32149,
To ma sens, ale zmienia kwestię twardości. W przypadku wielu gier wiadomo, który gracz ma strategię wygraną z pozycji początkowej, ale nie wiadomo, który gracz ma strategię wygraną na pozycji ogólnej. Weźmy na przykład Hex. Tutaj pierwszy gracz ma zwycięską strategię. Z ogólnej pozycji ustalenie, czy następny gracz, który przejdzie, ma strategię wygrywającą, jest kompletne z PSPACE.
Kyle,
Tak, masz rację, powinienem był wyjaśnić w pierwotnym pytaniu. Mówię o złożoności obliczeniowej określania, kto wygra na danym wykresie, zanim jakiekolwiek wierzchołki zostaną pokolorowane.
user32149,
Z pewnością jest to interesujące pytanie. Zwłaszcza, że ​​mówisz o ogólnym wykresie i nie stawiasz żadnych wymagań dotyczących jego struktury. Z pewnością będę zainteresowany, jeśli to wymyślisz!
Kyle