2 papers
math.CO2025
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…
cs.CC2025
Battle Sheep is PSPACE-complete
Kyle Burke, Hirotaka Ono
Battle Sheep is a board game published by Blue Orange Games. With two players, it is a combinatorial game that uses normal play rules. We show that it is PSPACE-complete, even when…