Delphi.science

The computational complexity of Undirected Vertex Geography with maximum height 3

Source: arxiv.org/abs/2611.24709

Craig Tennenhouse, Kanae Yoshiwatari

arXivarxiv/2611.24709Nov 18, 2026cs.CCscore 0

The impartial game Undirected Vertex Geography is known to be polynomial time solvable. The variant in which vertices are assigned heights with maximum value m that reduce by 1 whenever the token is moved from that vertex, denoted UIRm, is known to be polynomial time solvable when m=2 and PSPACE-complete when m=4. We solve the open question of the computational complexity of UIR3 by a reduction from Directed vertex geography, and show that the complexity holds when the underlying graph is planar and (a) has degree at most 3, (b) is bipartite with maximum degree 4, or (c) is bipartite with…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.24709
curl -X POST /api/v1/records/arxiv/2611.24709/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.24709/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'