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. Commented Sep 27, 2017 at 4:00
• @PyRulez: you are right of course, but this doesn't allow to answer any of the questions. Commented Sep 27, 2017 at 7:27

The game you describe is equivalent to a generalization of Kayles, called "Node-Kayles".

Christopher King's comment, suggesting the use of nimbers, aligns with what I see in the literature on this problem. For example: Nimber Sequences of Node-Kayles Games [Brown et al., 2020].

In the above paper, the authors answer a variant of your first question, by determining membership in $$\mathcal{G}_A$$ for "various families of graphs, including 3-paths, lattice graphs, prism graphs, chained cliques, linked cliques, linked cycles, linked diamonds, hypercubes, and generalized Petersen graphs."

You will be able to use the techniques from this paper to determine the winning player for Node-Kayles played on other graphs. For example, the analysis in Section 2 immediately extends to caterpillar trees.

The problem of winner determination is solved in polynomial time for any family of graphs with bounded asteroidal number:

The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component.

These authors answer your second question, on the computational complexity of these problems, and your third question on the specific case of trees:

Node Kayles is known to be PSPACE-complete, whereas the winner determination is solvable in polynomial time on graphs of bounded asteroidal numbers such as cocomparability graphs and cographs by using Sprague-Grundy theory. For general graphs, Bodlaender et al. propose an $$O(1.6031^n)$$-time algorithm. Furthermore, they show that the winner of Node Kayles can be determined in time $$O(1.4423^n)$$ on trees.