Edge Geography is XNLP-hard for Pathwidth and in XP for Tree-Partition Width

Thobias Kvalvik Høivik, Erlend Raa Vågset

Directed Edge Geography and Undirected Edge Geography are classical PSPACE-complete two-player graph games in which players alternately make moves along edges, deleting each one af…