betaFeedback

WorksComputer Science

The computational complexity of Undirected Vertex Geography with maximum height 3

Abstract

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 maximum degree 5 and only has heights of 1 and 3.

Paper details

vlnc:W_7mvxmxx7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…