Skip to main content

Anton Christenson: Reachability in the game of Tumbleweed is NP-complete

Time: Fri 2023-11-10 13.15 - 14.00

Location: Albano hus 1, Cramér room

Participating: Anton Christenson (SU/KTH)

Export to calendar

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.