Is this perfect information game played on graphs know/studied?

Given a graph $G= (V,E)$, two players alternate picking an edge or an isolated node. If the player picks an edge $e = (u,v)$ the two nodes $u$ and $v$ are deleted along with their incident edges. If the player picks an isolated node, the node is deleted. The first player unable to move loses the game.

What is the complexity of finding the winner?

Any references to similar games?

  • 1
    I assume the isolated node is removed if picked? If so, player 0 wins also on all nonempty paths by spending the first move subdividing the problem into two equal components and then mirroring the opponents move on the opposite component from then onward to maintain isomorphism. This implies player 1 wins on a cycle, since the first move reduces the problem to a path. – Yonatan N Jan 26 '13 at 13:42
  • 2
    @YonatanN: yes an isolated node can be picked (and removed); but the simmetry strategy works on paths of even length (player 0 picks the 2 central nodes as first move, then mirrors the moves of player 1), but not on the paths of odd length: try to apply the strategy to a path of length 11, and it doesn't work (indeed for a path of length 11 the winner is player 1). – Marzio De Biasi Jan 26 '13 at 20:02
  • 5
    @Marzio De Biasi: I am sorry but when I play nice games I normally play by hand. Unless I made mistakes, player 0 does have a winning strategy: Observe that: a) for P1, P2, P5, and P8, player 0 always wins. b) for P3 and P7, player 1 always wins. c) for P4 and P6, player 0 can decide to win or to lose. Now in case of P11: - Number the nodes of P11 with v1, v2, ... v11. - Player 0 takes the edge v9, v10 and the rest is the isolated node v11 and P8. If player 1 takes v11, player 0 will win because he has an even path. Otherwise, player 0 will win by a), b) and c). – user13136 Jan 27 '13 at 17:06
  • 1
    According to my program, the values of n≤100 such that the first player loses in the game on the path with n vertices are 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91, and 95. Unfortunately, I do not see any pattern other than being odd (which was already known), and OEIS does not show any matches. – Tsuyoshi Ito Jan 27 '13 at 23:12
  • 1
    @TsuyoshiIto: ... take the pairwise difference: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) and you get 4 4 4 4 4 4 ... it seems a pattern :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) and you get 20 20 20 ... another one! :-D – Marzio De Biasi Jan 27 '13 at 23:51

I post an update as a self-answer only to keep it distinct from the question (which is still open).

As shown in the comments (thanks to Tsuyoshi Ito) the problem is polynomial-time solvable for paths:

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

Starting from 0, the (calculated) sequence of the nim values is periodic:

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

I didn't work on a rigorous mathematical proof, but the idea is:

suppose that we want to calculate element $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$, then the first move (pick an edge) can split the path in $\lceil n / 2 \rceil$ different ways (n-2,0),(n-3,1),(n-4,2),...). The new nim value is equal to:

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

The first 34 elements of the set are produced by the first non repeating sequence (0,1,1,0,...) (nim)summed with the elements of the repeating sequence in reverse order starting from element $(34-2-x) \bmod 34$.

For example: for $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

For x=0..33 the resulting mex sequence is equal to the repeating sequence:

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 remaining elements of the set are calulated only on the repeating sequence(s): $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ (for $j \geq 34$ the pairs are repeated, so they don't alter the mex result). The resulting mex sequence for x=0..33 is:

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,

Which is equal to the repeating sequence except for $x=16$ and $x=33$; but the values are lower than the corresponding mex on the non-repeating sequence, so:

$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}\}$

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

  • According to my calculation, the first player does have a winning strategy for $P_{23}$, giving a counter-example to your claim $Win(P_n)= 1$ iff $(n \mod\, 34) \in \{3, 7, 23, 27\}$. – user13136 Feb 1 '13 at 11:11
  • @user13136: did you check the nim values? For $P_{23}$ the nim value is 0 (I got the same values of Tsuyoshi with a different program, but perhaps we are both wrong). – Marzio De Biasi Feb 1 '13 at 11:48
  • I think a possible flaw in your programs could be the ignoring of the $P_0$, in which case the first player always loses. If you want, we can play the case $P_{23}$ now. – user13136 Feb 1 '13 at 15:48
  • Sorry, I have to leave now. – user13136 Feb 1 '13 at 18:16
  • $(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})$ (you can delete the previous comments containing the moves) – Marzio De Biasi Feb 1 '13 at 18:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.