Two-player independent set game

Question

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?

Answer 1

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.

• Winner Determination Algorithms for Graph Games with Matching Structures [Yoshiwatari et al., 2022]

• Exact Algorithms for Kayles [Bodlaender et al., 2015].

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.