Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles

Kyle Burke (1) , Antoine Dailly (2) , Nacim Oijid (3, 4, 5)

1 Florida Southern College
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
3 LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
4 GOAL - Graphes, AlgOrithmes et AppLications
5 UCBL - Université Claude Bernard Lyon 1

Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left. Introduced in 1978, its computational complexity is still open. More recently, subtraction games, where the players cannot disconnect the graph while removing vertices, were introduced. In particular, Arc-Kayles admits a non-disconnecting variant that is a subtraction game. We study the computational complexity of subtraction games on graphs, proving that they are PSPACE-complete even on very structured graph classes (split, bipartite of any even girth). We prove that Non-Disconnecting Arc-Kayles can be solved in polynomial-time on unicyclic graphs, clique trees, and subclasses of threshold graphs. We also show that a sufficient condition for a second player-win on Arc-Kayles is equivalent to the graph isomorphism problem.

Mots clés: Combinatorial games; Vertex deletion games; Subtraction games; Complexity; Arc-Kayles

Domaines: Combinatoire [math.CO]; Mathématique discrète [cs.DM]

Kyle Burke, Antoine Dailly, Nacim Oijid. Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles. 2024. ⟨hal-04495881⟩