{"ID":5935802,"CreatedAt":"2026-07-07T01:22:02.77346169Z","UpdatedAt":"2026-07-07T02:10:06.972658124Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.03189","arxiv_id":"2607.03189","title":"Edge Geography is XNLP-hard for Pathwidth and in XP for Tree-Partition Width","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.","short_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 ques...","url_abs":"https://arxiv.org/abs/2607.03189","url_pdf":"https://arxiv.org/pdf/2607.03189v1","authors":"[\"Thobias Kvalvik Høivik\",\"Erlend Raa Vågset\"]","published":"2026-07-03T10:47:49Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}