11
$\begingroup$

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?

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Jan 26, 2013 at 13:42
  • 2
    $\begingroup$ @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). $\endgroup$
    – Marzio De Biasi
    Jan 26, 2013 at 20:02
  • 5
    $\begingroup$ @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). $\endgroup$
    – user13136
    Jan 27, 2013 at 17:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Jan 27, 2013 at 23:12
  • 1
    $\begingroup$ @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 $\endgroup$
    – Marzio De Biasi
    Jan 27, 2013 at 23:51

1 Answer 1

Reset to default
2
$\begingroup$

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)\; $

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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\}$. $\endgroup$
    – user13136
    Feb 1, 2013 at 11:11
  • $\begingroup$ @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). $\endgroup$
    – Marzio De Biasi
    Feb 1, 2013 at 11:48
  • $\begingroup$ 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. $\endgroup$
    – user13136
    Feb 1, 2013 at 15:48
  • $\begingroup$ Sorry, I have to leave now. $\endgroup$
    – user13136
    Feb 1, 2013 at 18:16
  • $\begingroup$ $(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) $\endgroup$
    – Marzio De Biasi
    Feb 1, 2013 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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