Estrategia ganadora de un juego de eliminación de "borde o vértice aislado"

¿Es este juego de información perfecto jugado en gráficos conocido / estudiado?

Dado un gráfico $G= (V,E)$ , dos jugadores se alternan eligiendo un borde o un nodo aislado. Si el jugador elige un borde $e = (u,v)$ los dos nodos $u$ y $v$ se eliminan junto con sus bordes incidentes. Si el jugador elige un nodo aislado, el nodo se elimina. El primer jugador que no puede moverse pierde el juego.

¿Cuál es la complejidad de encontrar al ganador?

¿Alguna referencia a juegos similares?

Publico una actualización como respuesta automática solo para mantenerla distinta de la pregunta ( que aún está abierta ).

Como se muestra en los comentarios (gracias a Tsuyoshi Ito), el problema es solucionable en tiempo polinómico para rutas:

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

A partir de 0, la secuencia (calculada) de los valores nim es 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

No trabajé en una prueba matemática rigurosa, pero la idea es:

supongamos que queremos calcular el elemento , entonces el primer movimiento (elegir un borde) puede dividir la ruta en diferentes maneras (n-2,0), (n-3, 1), (n-4,2), ...). El nuevo valor de nim es 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}\}$

Los primeros 34 elementos del conjunto son producidos por la primera secuencia no repetitiva (0,1,1,0, ...) (nim) sumada con los elementos de la secuencia repetitiva en orden inverso a partir del elemento .$(34-2-x) \bmod 34$

Por ejemplo: 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 la secuencia mex resultante es igual a la secuencia repetitiva:

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

Los elementos restantes del conjunto se calculan solo en las secuencias de repetición: (para los pares se repiten, por lo que no alteran el resultado mex). La secuencia mex resultante para x = 0..33 es:$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 es igual a la secuencia de repetición excepto para y ; pero los valores son más bajos que el mex correspondiente en la secuencia no repetida, entonces:$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}\}$

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