Esses jogos de colorir foram resolvidos?

12

No artigo "Sobre a complexidade de alguns jogos de colorir", Bodlaender faz algumas perguntas em aberto sobre a complexidade de decidir se o jogador 1 ou 2 tem uma estratégia vencedora em alguns jogos de colorir gráficos. Alguém sabe se eles foram resolvidos?

1) Em um jogo, dois jogadores se revezam selecionando um vértice em um gráfico e colorindo-o adequadamente com uma cor de um conjunto finito fixo. O perdedor é o primeiro jogador que não consegue colorir um vértice. No artigo de Schaefer, ele mostra que o pspace é completo com 1 cor e o Bodlaender mostra que ele é pspace completo com 2 cores, mas não dá resposta com mais cores. Ainda está aberto?

2) Em outra variação, os vértices têm números 1..n. No turn de um jogador, ele deve colorir adequadamente o vértice com o número mais baixo que ainda não foi colorido. Novamente, eles estão usando cores de um conjunto fixo e o perdedor é o primeiro jogador que não consegue colorir seu vértice. O Bodlaender mostra que ele é completo no pspace para gráficos gerais. Ele pergunta quem ganha nas árvores, é conhecido?

obrigado

graph-colouring pspace two-player-games user32149
fonte
2
Por que você não pergunta diretamente ao Bodlaender? staff.science.uu.nl/~bodla101
Gamow

Respostas:

2

Parece que este documento tem algo do que você está procurando: http://arxiv.org/abs/1202.5762

A forma geral da primeira pergunta é uma redução realmente simples: usando as cores {0, ..., n-1}, comece com uma instância do Node Kayles e crie um vértice para cada uma das cores de 1 a n-1 e conecte para cada vértice incolor. Agora, essas cores não podem ser reproduzidas e você ainda está jogando o jogo Node Kayles.

Kyle
fonte
Obrigado pelo link, vou dar uma olhada. Nesta questão, não permitimos uma 'pré-coloração'; portanto, não podemos assumir que alguns vértices já tenham uma cor. O jogo começa com todos os vértices sem cor.
user32149
Isso faz sentido, mas muda a questão da dureza. Em muitos jogos, sabe-se qual jogador possui uma estratégia vencedora em uma posição inicial, mas não se sabe qual jogador possui uma estratégia vencedora em uma posição geral. Veja o Hex, por exemplo. Aqui, o primeiro jogador tem uma estratégia vencedora. De uma posição geral, determinar se o próximo jogador a se mover tem uma estratégia vencedora é PSPACE-complete.
21715 Kyle
Sim, você está certo, eu deveria ter esclarecido na pergunta original. Estou falando da complexidade computacional de determinar quem ganha em um determinado gráfico antes que qualquer vértice seja colorido.
user32149
É uma pergunta interessante, com certeza. Especialmente porque você está falando sobre um gráfico geral e não colocando requisitos em sua estrutura. Certamente ficarei interessado em saber se você descobre!
Kyle