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

Kyle Burke, Antoine Dailly, Nacim Oijid

Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left, the winner being the player who played the last move. Introduced in 1978, its…