Edge Geography is XNLP-hard for Pathwidth and in XP for Tree-Partition Width
2026-07-03 • Computational Complexity
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study two complex two-player graph games where players move along edges, removing each edge after use, and the one who cannot move loses. They prove that solving these games is very hard (XNLP-hard) when looking at a certain graph property called pathwidth. However, they find that one game is easier to solve when using other graph properties like treewidth combined with the maximum degree. They also show both games can be solved in a reasonable time for graphs with small tree-partition width. Their work advances understanding of how graph structure affects the difficulty of these games.
Directed Edge GeographyUndirected Edge GeographyPSPACE-completeXNLP-hardpathwidthtreewidthmaximum degreetree-partition widthtwo-player graph games
Authors
Thobias Kvalvik Høivik, Erlend Raa Vågset
Abstract
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 after use; the first player unable to move loses. We prove that both problems are XNLP-hard when parameterized by pathwidth, addressing a question raised by Bodlaender over 30 years ago. On the positive side, we observe that Directed Edge Geography is fixed-parameter tractable when parameterized by treewidth and maximum degree. We also prove that both problems are in XP on simple graphs when parameterized by tree-partition width. These results develop modern lower-bound and decomposition-based algorithmic methods for width-based questions in PSPACE-complete graph games.