# 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)

**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.