# Two-player independent set game

Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \backslash S$ such that $v$ is not adjacent to any vertex of $S$, and adding $v$ to $S$. The player without any valid move options loses.

Consider the class $\mathcal{G_A}$ of graphs for which Alice has a winning strategy. Is there a (feasible) combinatorial graph invariant that is equivalent to membership in $\mathcal{G_A}$? What is the complexity of deciding membership in $\mathcal{G_A}$? Are these questions simpler if we restrict $G$ to be a tree?

• Consider the game as starting with $V$, and removing vertices (along with their neighbors). Than this game can naturally be analyzed using nimbers, since when our graph becomes disconnected, it is essentially a nimber sum. – PyRulez Sep 27 '17 at 4:00
• @PyRulez: you are right of course, but this doesn't allow to answer any of the questions. – Mikhail Tikhomirov Sep 27 '17 at 7:27