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

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.