Para quais famílias de gráficos a Geografia Generalizada está em

11

Como o @Marzio mencionou, o jogo a seguir é conhecido como Geografia Generalizada .

Dado um gráfico e um vértice inicial , o jogo é definido da seguinte forma:G=(V,E)vV

A cada turno (dois jogadores alternando), um jogador escolhe e, em seguida, acontece o seguinte:uN(v)

  1. v , bem como todos os seus bordos, é removida a partir de .G
  2. vocêv (ou seja, é atualizado para ser o vértice ).vvocê

O jogador que é forçado a selecionar um "beco sem saída" (ou seja, um vértice sem arestas de saída) perde.

Em quais famílias de gráficos a estratégia ideal é computável em tempo polinomial?

Por exemplo, é fácil ver que, se é um DAG, podemos calcular facilmente a estratégia ideal para os jogadores.G

RB
fonte
5
O jogo é conhecido como Geografia Generalizada e é completo no PSPACE (mesmo em gráficos direcionados planares). Veja Complexidade de jogos percurso de formao para algumas variantes (também algum tempo polinomial variantes)
Marzio De Biasi
Você pode ser mais específico? Por exemplo, no link de Marzio, você pode ver que a largura da árvore limitada é suficiente.
Domotorp
11
@domotorp: Eu acho que o GG em gráficos de grade sólida não direcionada é um problema aberto não resolvido (talvez também não seja estudado). Vou pesquisar um pouco no Google para ver se é um novo problema. Embora, no caso de gráficos de grade sólida direcionada, pareça fácil simular "furos" usando as arestas direcionadas, portanto deve ser completo no PSPACE.
Marzio De Biasi

Respostas:

8

A Geografia Generalizada (GG) é completa no PSPACE, mesmo em gráficos bipartidos direcionados planares, mas, conforme relatado em:

Hans L. Bodlaender, Complexidade dos jogos de formação de caminhos , Ciência da Computação Teórica, Volume 110, Edição 1, 15 de março de 1993, Páginas 215-245

GG (e algumas outras variantes completas do PSPACE) são linearmente resolvíveis no tempo em gráficos de largura de árvore limitada.

NOTA LATERAL: uma das variantes da Geografia Generalizada que recentemente se mostrou completa no PSPACE é Tron ( jogo Light Cycles ): dado um gráfico não direcionado, dois jogadores escolhem dois vértices iniciais diferentes e depois se revezam, movendo-se para um adjacente vértice do respectivo respectivo anterior em cada etapa. O jogo termina quando os dois jogadores não podem mais se mover. O jogador que atravessou mais vértices vence (foi considerado um PSPACE completo em 1990 por Bodlaender e Kloks).
Tillmann Miltzow, Tron, um jogo combinatório em gráficos abstratos (2011)


n×m

               Width n
           1 2 3 4 5 6 7 8 
         1 A B A B A B A B    Winning matrix up to 8x8
         2   B B B B B B B 
         3     A B A B A B 
Height m 4       B B B B B  
         5         A B A B 
         6           B B B 
         7             A B 
         8               B 

Curiosamente, a mesma matriz é obtida se o jogador A puder escolher um nó inicial arbitrário.

Como dito nos comentários, acho que a complexidade de decidir se existe uma estratégia vencedora quando o GG é jogado em gráficos sólidos (com formas arbitrárias, mas sem buracos) não é conhecida e, provavelmente, não é tão fácil provar algo sobre isso. (na verdade, o problema - de certa forma relacionado - de decidir se um gráfico de grade sólido tem um caminho hamiltoniano ainda está aberto, embora decidir se um gráfico de grade sólido tem um ciclo hamiltoniano é solucionável em tempo polinomial).

Uma nota trivial final: GG também pode ser resolvido no tempo polinomial em gráficos completos.

Marzio De Biasi
fonte
Você tem certeza que o ciclo hamiltoniano no gráfico de grade sólida é passível de solução polinomial? Pelo que me lembro, é desconhecido, por outro lado, se essa grade sólida tiver algumas estruturas (como forma de L, forma de T, mxn, ...), é polinomial solucionável em tempo, mas não me lembro de nenhum papel que a resolva em tempo polinomial em geral, gráficos de grade sólida. Você tem uma referência?
Saeed
11
@Saeed Parece que Umans e Lenhart resolveram o antigo problema aberto, veja Ciclos Hamiltonianos em sólidos Grid Grid . Há pouco tempo, procurei resultados recentes / relacionados sobre o caminho hamiltoniano em gráficos de grade sólida, mas não encontrei nada. (Eu acho que há também uma questão relacionada em algum lugar cstheory)
Marzio De Biasi
Obrigado, isso é realmente ótimo e também não é um FOCS1997 muito novo , mas nunca o vi antes!
Saeed
Ótima resposta @MarzioDeBiasi. Na verdade, me deparei com esse problema em um cenário diferente, que pode ser modelado como um gráfico de grade, mas estava curioso sobre sua generalização.
RB
Passei meia hora, mas não consegui encontrar nenhuma referência para a Geografia Generalizada Indireta. Tenho certeza que deve ter sido demonstrado por alguém para ser completo no PSPACE. Você talvez saiba sobre isso?
Domotorp 27/09/14
3

1 1cG-c0 0c1 1

Saeed
fonte