Nim-Geografía bipartita

Question

Dos jugadores juegan una partida en un grafo bipartito en el que todas las aristas son nim-heaps de distintos tamaños. Una ficha comienza en uno de los vértices, y en su turno debe mover la ficha sobre una arista y recoger algunos de los palos de fósforo en el montón de nim correspondiente a esa arista. Si todas las aristas que se encuentran en el vértice que contiene la ficha están vacías al comenzar el turno, pierdes.

¿Existe un algoritmo de tiempo polinómico para decidir este juego?

Motivación:

Estoy interesado en un juego combinatorio multijugador que se juegue de la siguiente manera: entre cada par de personas se sienta un juego combinatorio. Un jugador comienza con una ficha de "patata caliente". Quien tiene la ficha debe hacer un movimiento en uno de los juegos incidentes a él para pasar la ficha al otro jugador que juega ese juego. Si no puede hacer un movimiento en ninguno de los juegos adyacentes a él, pierde y todos los demás ganan.

Como los juegos multijugador son difíciles de analizar, podemos simplificar el problema dividiendo a los jugadores en dos equipos, en los que cada equipo quiere que la patata acabe en manos del otro. Para simplificar aún más el juego, también podemos suponer que no hay dos jugadores del mismo equipo que tengan una partida entre ellos. Incluso entonces, si todos los juegos son números, este problema es una geografía bipartita dirigida que estoy bastante seguro de que es PSPACE-completa, así que asumo que todos los juegos son imparciales también.

Sin embargo, si todos los nim-heaps tienen tamaño uno o cero, entonces este problema se convierte en geografía bipartita no dirigida, que puede resolverse en tiempo polinómico, por lo que sospecho firmemente que la nim-geografía bipartita también debería tener una solución en tiempo polinómico.

Answer 1

Supongo que ya lo sabes, pero acabo de toparme con este artículo que estudia exactamente el mismo juego que has descrito:

M. Fukuyama, Un juego de Nim en gráficos, Theoret. Comput. Sci. 304 (2003), 387-399.

$\text{Section 3}$ de este trabajo estudia el juego Nim en un grafo bipartito simple en el que todos los vértices de un lado son de grado (como máximo) $2$ . Al principio del juego, se supone que la ficha está en un vértice del lado sin la condición de grado. Pongo el término "como máximo" entre paréntesis porque se demuestra que esto es irrelevante en el documento, de modo que se puede asumir con seguridad que todos los vértices del lado restringido son de grado $2$ . El autor da las condiciones necesarias y suficientes para que el primer jugador tenga una estrategia ganadora.

Para decidir si el primer jugador puede ganar utilizando las condiciones necesarias y suficientes dadas en este documento, si mi comprensión a través de hojear el documento es correcta, se comprueba si las siguientes tres condiciones se mantienen para cada vértice $u$ en el lado con la restricción de grado:

1. El número $h$ de fósforos en el montón de nim en un borde con $u$ ya que su punto final es diferente al de la otra arista con $u$ como su punto final, (En lo siguiente, $h$ se supone que es menor).

2. Dividir el vértice $u$ en $u_1$ y $u_2$ y con el fin de suponer que la única arista de la cual $u_1$ es un punto final después de la división es de peso $h$ . La capacidad mínima de $u_1$ - $u_2$ cortes es igual a $h$ .

3. Para cualquier mínimo $u_1$ - $u_2$ corte, el vértice en el que se encuentra la ficha está conectado a $u_2$ (es decir, el que tiene más cerillas en su borde).

Comprobar la primera condición es trivial. La segunda sólo necesita calcular la capacidad mínima, lo que puede hacerse en tiempo polinómico. Para la tercera condición, aunque comprobar si dos vértices están conectados en un grafo puede hacerse rápidamente, es posible que tengamos que enumerar todos los mínimos $u_1$ - $u_2$ cortes. Google me consiguió este documento que menciona un algoritmo para enumerar todos los mínimos $s$ - $t$ recortes para los fijos $s$ y $t$ donde el tiempo de ejecución depende del número total de mínimos $s$ - $t$ cortes para todos los pares $s, t$ en el conjunto de vértices, que puede ser exponencial... Los detalles están relegados a otro informe técnico de los mismos autores (Ref. [GN1] en el PDF enlazado), y parece que hay una mejora de esto en dicho informe técnico. Pero no he podido encontrarlo en Internet.

He buscado un documento similar que no imponga la condición de grado, pero mi google-fu me ha fallado.