Anton Christenson: Reachability in the game of Tumbleweed is NP-complete
Tid: Fr 2023-11-10 kl 13.15 - 14.00
Plats: Albano hus 1, Cramér room
Medverkande: Anton Christenson (SU/KTH)
Abstract.
Tumbleweed is a two-player abstract strategy board game invented in 2020 by Mike Zapawa. In 2022, Lear Bahack proved that determining which player has a winning strategy from a given position is PSPACE-complete. In this presentation we instead consider the problem of determining whether a given position can be reached, by some sequence of legal moves, from another given position. We prove that this problem is NP-complete, using a reduction from a Hamiltonian cycle problem on directed graphs.