PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Undirected Partizan Edge Geography

Yuto Okada

arXiv:2609.18330v1cs.DSmath.CO

TL;DR

Winner determination for Geography is known to be PSPACE-complete on directed graphs, but the paper addresses the undirected case for Partizan Edge Geography. Using a reduction built from game gadgets, it proves PSPACE-completeness on bipartite undirected graphs of maximum degree 3, including when the tokens cannot share a vertex.

  • Problem

    The paper studies the complexity of winner determination for Partizan Edge Geography on undirected graphs, complementing known PSPACE-completeness results for directed Geography.

    Source: §1 · pp. 1–2

  • Method

    The reduction uses variable, clause, and judge gadgets to encode quantified-formula play as Partizan Edge Geography.

    Source: §2 · pp. 4, 6

  • Results

    Rooted Partizan Edge Geography and Rooted Distinct Partizan Edge Geography are PSPACE-complete on bipartite undirected graphs of maximum degree 3.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The same reduction establishes hardness even when the two tokens cannot occupy the same vertex.

    Source: §1 · p. 2

    The reduction assumes n and m are sufficiently large and takes n odd; even n can be padded with a dummy variable and clause.

    Source: §2 · p. 2

Abstract

from arXiv · show

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

1 Introduction

The paper establishes PSPACE-completeness for Rooted Partizan Edge Geography on bipartite undirected graphs of maximum degree 3. The same reduction yields PSPACE-completeness for the distinct-token variant.

  • Winner determination for Geography was already known to be PSPACE-complete on directed graphs, while this paper addresses its Partizan Edge variant on undirected graphs.The paper frames its result as the undirected counterpart of prior directed-graph work.Source: §1 · pp. 1–2
  • Partizan Edge Geography asks whether blue can win when each player moves their own token along an edge and removes that edge.The first player unable to move loses.Source: §1 · p. 1
  • Rooted Partizan Edge Geography is PSPACE-complete on bipartite undirected graphs of maximum degree 3.Source: §1 · p. 2
  • Rooted Distinct Partizan Edge Geography is also PSPACE-complete on bipartite undirected graphs of maximum degree 3.The variant forbids placing both tokens on the same vertex, and the same reduction applies.Source: §1 · p. 2

2 PSPACE-Completeness

The reduction from 3-TQBF establishes PSPACE-hardness for Rooted Partizan Edge Geography on connected bipartite graphs of maximum degree 3, while the problem is in PSPACE. Its correctness follows from forcing the players’ token routes and matching the winner to the quantified formula’s truth; the same reduction supports the distinct-token variant.

Construction

  • The reduction encodes each quantified variable with a parity-specific variable gadget and links clause gadgets to the variable gadgets for their literals.The graph also includes a judge gadget and connecting paths, with path lengths adjusted to preserve bipartiteness.Source: §2 · p. 4
  • The constructed graph is connected, bipartite, has maximum degree 3, and is polynomial in size, yielding PSPACE-hardness on this restricted class.The construction uses ℓ = O(nm); combined with PSPACE membership, this gives PSPACE-completeness.Source: §2 · pp. 2, 4

Forced play

  • A player who first leaves the prescribed token route loses, allowing the proof to analyze only the intended play.The proof argues that the player who remains on track can reach a winning route before the opponent can interfere.Source: §2 · pp. 4, 6

Correctness

  • The blue player wins exactly when the quantified 3-CNF formula is true, establishing the reduction’s correctness.The construction assigns truth values through variable-gadget paths and uses clause detours to distinguish true from false formulas.Source: §2 · pp. 6–7
  • When the formula is false, the blue token cannot traverse at least two of three length-ℓ3 subtrees, leaving fewer available moves than the red player.The blue player’s available edges are bounded by (4m + 2 + o(1))ℓ3, below the red player’s available moves for sufficiently large n and m.Source: §2 · p. 7, Figure 5 · p. 7

Distinct-token variant

  • The same reduction proves PSPACE-completeness when the two tokens may not occupy the same vertex.The proof notes that the prescribed play avoids shared vertices and that the tokens become adjacent only at B1 and R1 before following the same optimal routes.Source: §2 · p. 7

3 Conclusions

The paper establishes PSPACE-completeness for Rooted Partizan Edge Geography and its distinct-token variant, then identifies planar directed and unrooted versions as open conjectures.

3 Conclusions

  • The paper establishes PSPACE-completeness for Rooted Partizan Edge Geography and Rooted Distinct Partizan Edge Geography.The conclusion then poses open problems.Source: §3 · p. 8
  • The authors conjecture that both problems remain PSPACE-complete on planar directed graphs of maximum degree 3.Source: §3 · p. 8
  • The authors conjecture that the unrooted variants are PSPACE-complete and suggest that resolving any one of three similar problems could inform the others.Trail Trap is already known to be NP-hard for testing whether the second player wins, and its authors conjectured PSPACE-completeness [2, Conjecture 23].Source: §3 · p. 8

AI Usage Statement

The author reports that the proofs were developed without generative AI, while named models were used for literature searches, proof checking, and writing improvements.

AI Usage Statement

Loading 2609.18330v1…