DROPS

Artifact

Software

GeographyXPAlgorithm

Authors: Thobias Kvalvik Høivik

Abstract

Cite as

Thobias Kvalvik Høivik. GeographyXPAlgorithm (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27616,
   title = {{GeographyXPAlgorithm}}, 
   author = {H{\o}ivik, Thobias Kvalvik},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:138f852ee494fb59e4a77b073493b0e6a1788c53;origin=https://github.com/ThobiasKH/GeographyXPAlgorithm;visit=swh:1:snp:4c4ae5d6665a2cea419b9a4a8688195d5548fc95;anchor=swh:1:rev:25ff7ad0e4d11fbc82e084f305332a0c82338d17}{\texttt{swh:1:dir:138f852ee494fb59e4a77b073493b0e6a1788c53}} (visited on 2026-08-25)},
   url = {https://github.com/ThobiasKH/GeographyXPAlgorithm},
   doi = {10.4230/artifacts.27616},
}

Document

DOI: 10.4230/LIPIcs.ESA.2026.114

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

Authors: Thobias Kvalvik Høivik and Erlend Raa Vågset

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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.

Cite as

Thobias Kvalvik Høivik and Erlend Raa Vågset. Edge Geography is XNLP-hard for Pathwidth and in XP for Tree-Partition Width. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 114:1-114:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hoivik_et_al:LIPIcs.ESA.2026.114,
  author =	{H{\o}ivik, Thobias Kvalvik and V\r{a}gset, Erlend Raa},
  title =	{{Edge Geography is XNLP-hard for Pathwidth and in XP for Tree-Partition Width}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{114:1--114:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.114},
  URN =		{urn:nbn:de:0030-drops-272504},
  doi =		{10.4230/LIPIcs.ESA.2026.114},
  annote =	{Keywords: Geography games, graph games, pathwidth, parameterized complexity, XNLP-hardness, PSPACE-complete games, tree-partition width}
}

Search Results

Documents authored by Høivik, Thobias Kvalvik

GeographyXPAlgorithm

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message