2 papers
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…
math.CO2024
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…