Czy te gry kolorowanki zostały rozwiązane?

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

graph-colouring pspace two-player-games

— użytkownik32149
źródło

Dlaczego nie zapytasz bezpośrednio Bodlaendera? staff.science.uu.nl/~bodla101

— Gamow

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