Estratégia vencedora de um jogo de exclusão de "borda ou vértice isolado"

Este jogo de informações perfeitas, jogado em gráficos, é conhecido / estudado?

Dado um gráfico $G= (V,E)$ , dois jogadores alternam escolhendo uma aresta ou um nó isolado. Se o jogador escolher uma aresta $e = (u,v)$ os dois nós $u$ e $v$ serão excluídos juntamente com as arestas incidentes. Se o jogador escolher um nó isolado, o nó será excluído. O primeiro jogador incapaz de se mover perde o jogo.

Qual é a complexidade de encontrar o vencedor?

Alguma referência a jogos similares?

Publico uma atualização como resposta automática apenas para mantê-la distinta da pergunta ( que ainda está aberta ).

Como mostrado nos comentários (graças a Tsuyoshi Ito), o problema é solucionável em tempo polinomial para caminhos:

$Win(P_n) = 1$$(n \bmod 34) \in \{3,7,23,27\}$

A partir de 0, a sequência (calculada) dos valores nim é periódica:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

Não trabalhei em uma prova matemática rigorosa, mas a ideia é:

suponha que desejamos calcular o elemento , o primeiro movimento (escolha uma aresta) pode dividir o caminho em maneiras diferentes (n-2,0), (n-3, 1), (n-4,2), ...). O novo valor nim é igual a:$Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$$\lceil n / 2 \rceil$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$

Os primeiros 34 elementos do conjunto são produzidos pela primeira sequência não repetida (0,1,1,0, ...) (nim) somada aos elementos da sequência repetida na ordem inversa, a partir do elemento .$(34-2-x) \bmod 34$

Por exemplo: para :$x = 0$

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

Para x = 0..33, a sequência mex resultante é igual à sequência de repetição:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

Os elementos restantes do conjunto são calculados apenas na (s) sequência (s) de : (para os pares são repetidos, portanto eles não alteram o resultado mexicano). A sequência mex resultante para x = 0..33 é:$rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$$j \geq 34$

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Que é igual à sequência de repetição excepto para e ; mas os valores são mais baixos que o mex correspondente na sequência não repetida, portanto:$x=16$$x=33$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ =$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$

e para ,$(k\geq 4, 0 \leq x < 34)$$Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\;$