The node deletion game NODE KAYLES is a two persons perfect information game played on a graph $G$. Players alternate picking a node from the graph $G$; the node and its adjacent nodes are deleted. The first player unable to move loses the game. Deciding the winner of a NODE KAYLES game is $\mathsf{PSPACE}$-complete [1]. Similarly in the EDGE KAYLES [1] game the two players must pick an edge; the edge is deleted along with the two endpoint nodes and the edges incident to its two endpoint nodes. The complexity of finding the winner of a EDGE KAYLES game is unknwon. On the Q&A site cstheory.stackexchange.com I submitted a mix of the two games; I call it the BRIDGES AND ISLANDS game: at each turn each player must pick an edge (a “bridge”) or an isolated node (an “island”); if a player picks a node the node is deleted along with its incident edges, if it picks an edge, the edge is deleted along with its two endpoint nodes and the edges incident to them. Like the other two games, the first player unable to move loses the game. I didn’t succeed in finding the complexity of BRIDGES AND ISLANDS.
However decideng the winner is polynomial time solvable when the three games are played on a path. Here I give a quick proof for EDGE KAYLES; the proof for the other two games is similar.When the games are played on a path then we can apply the theory of impartial games and in particular the Sprague-Grundy theorem: every impartial game is equivalent to a Nim game with a single heap of a certain size (the size is called nimber).
If EDGE KAYLES is played on a path with $n$ nodes ($n-1$ edges), at every turn the edge removed generates one or two smaller independent subgames and the nim values can be easily calculated using the Sprague-Grundy theorem:
n = 0 -> g(0) = 0 (player B wins)
n = 1 -> g(1) = 0 (player B wins)
n = 2 -> g(2) = 1 (player A wins)
n = 3 -> g(3) = mex({ g(1) }) = mex({ 0 }) = 1
n = 4 -> g(4) = mex({ g(2), g(1)+g(1) }) = mex({ 1, 0 }) = 2
...
Note: + represents the nim-addition
The sequence of the first 170 values of the Sprague-Grundy function is:
0,0,1,1,2,0,3,1,1,0,3,3,2,2,4,0,5,2,2,3,3,0,1,1,3,0,2,1,1,0,4,5,2,7, 4,0,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,2,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7, 4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7, 4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7, 4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7, ...
You can notice that after the first 68 numbers, the function seems periodic with period length 34 and the repeated sequence is:
R = 4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7.
To prove that it is periodic, we can examine the values of the Sprague-Grundy function $g(n)$ for $n = 34*k + x_i,\; k \geq 5,\; 0 \leq x_i < 34$.
We assume that $g(34 * m+x_i)=g(34 *(m+1)+x_i)$ for $2\leq m < k$. The first move can split the path in two halves, and the lengths of the two halves can be $(n-2,0), (n-3,1), (n-4,2), …, (n-k,k-2)$ with $k = \lfloor n/2 \rfloor$. The new nim value is equal to:
$g(n) = mex(\{ g(n-2-j) \oplus g(j)\}), 0 \leq j \leq \lfloor n/2 \rfloor$
The first 68 elements of the set are produced by the nim-sum of $g(34*k+x_i-2-j )$ (in decreasing order) and the first elements that belong to the non repeating sequence $g(j), 0 \leq j < 68$ (in increasing order). For example for $x_i = 0$ we get:
0 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 + (nim-sum) 3 5 4 0 1 1 2 0 3 1 1 0 3 3 9 5 5 4 4 2 2 3 3 0 1 1 3 0 2 1 1 8 4 7 3 5 4 0 1 1 2 0 3 1 1 0 3 3 9 5 5 4 4 2 2 3 3 0 1 1 3 0 2 1 1 8 4 7 = 3 5 5 1 3 1 1 1 2 1 2 3 1 1 13 5 0 6 6 1 1 3 2 1 2 1 1 1 3 1 5 13 6 0 7 5 5 1 3 1 1 1 2 1 2 3 1 1 13 1 0 1 6 1 1 3 2 1 2 1 1 1 3 1 5 13 7 0 Mex value: 4
The rest of the values of the set are produced by:
(1) $g(34*(k-2)+x_i – 2 – j) \oplus g(34*2 + j), 0 \leq j < \lfloor n/2 \rfloor$.
If we assume that for $g(34 * m+x_i)=g(34 *(m+1)+x_i)$ for $2\leq m < k$, the nim sums above (1) are equivalent to:
(2) $g( R[(x_i – 2 – j)\bmod 34]) \oplus R[(x_i + j)\bmod 34]), \; 0 \leq j < 34$,
where $R[i]$ is the i-th element of the repeating sequence.
Calculating the mex of the union of the first 68 nim-sums with the periodic nim-sums (2) we obtain again the repeating sequence R:
4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7
So $g(34 *k+x_i) = g(34 *(k+1)+x_i)$ and by induction we can conclude that the sequence will be repeated forever.
Finally we can conclude that player A can win the EDGE KAYLES game played on a path of $n$ nodes if and only if
$n \in \{0,1,35\} \lor (n \bmod 34) \in \{5, 9, 15, 21, 25, 29\}$
$\square$
[1] Thomas J. Schaefer. 1976. Complexity of decision problems based on finite two-person perfect-information games. In Proceedings of the eighth annual ACM symposium on Theory of computing (STOC ’76). ACM, New York, NY, USA, 41-49.