Cover Image

Paintbucket on graphs is PSPACE-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Saunders, Ethan J., Selinger, Peter
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Computational Complexity 91A46 (Primary) 91A05, 68Q17 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hive is PSPACE-Hard
by: Andel, Daniël, et al.
Published: (2025)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

On the $\mathcal{P}$-positions of some infinite families of Slow $A$-Nim
by: Heubach, Silvia, et al.
Published: (2024)

Cuts, Cats, and Complete Graphs
by: Ashmore, Rylo, et al.
Published: (2024)

Two-player Domino games
by: de Menibus, Benjamin Hellouin, et al.
Published: (2023)

Temperatures of Robin Hood
by: Dargad, Ankita, et al.
Published: (2025)

Structure-biased Maker-Breaker Games
by: Pegden, Wesley, et al.
Published: (2025)

Nim on Integer Partitions and Hyperrectangles
by: Gottlieb, Eric, et al.
Published: (2025)

Battle Sheep is PSPACE-complete
by: Burke, Kyle, et al.
Published: (2025)

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
by: Tewolde, Emanuel, et al.
Published: (2024)

Snort Played on Triangular Grids
by: Gauthier, Melanie, et al.
Published: (2024)

Constructing All Birthday 3 Games as Digraphs
by: Clow, Alexander, et al.
Published: (2025)

On the equivalence of semidefinite programming and zero-sum semidefinite games
by: Elliott, Jesse, et al.
Published: (2026)

Computing Game Symmetries and Equilibria That Respect Them
by: Tewolde, Emanuel, et al.
Published: (2025)

How to pick your football team
by: Narayanan, Bhargav
Published: (2026)

On 3-terminal positions in Hex
by: Demer, Eric, et al.
Published: (2025)

Maximum Nim and Josephus Problem algorithm
by: Takahashi, Shoei, et al.
Published: (2024)

The Value of Recall in Extensive-Form Games
by: Berker, Ratip Emin, et al.
Published: (2024)

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

Additive Subtraction Games
by: Larsson, Urban, et al.
Published: (2026)

All passable games are realizable as monotone set coloring games
by: Demer, Eric, et al.
Published: (2021)

Misère Cricket Pitch
by: Nowakowski, Richard J., et al.
Published: (2024)

Impartial Chess on Integer Partitions
by: Gottlieb, Eric, et al.
Published: (2025)

A Characterization of Complexity in Public Goods Games
by: Gilboa, Matan
Published: (2023)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

Trail Trap: a variant of Partizan Edge Geography
by: Buchanan, Calum, et al.
Published: (2024)

On graph automorphisms related to Snort
by: Ashmore, Rylo, et al.
Published: (2025)

On edge-colouring-games by Erdős, and Bensmail and Mc Inerney
by: Cambie, Stijn, et al.
Published: (2025)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

On marginal feature attributions of tree-based models
by: Filom, Khashayar, et al.
Published: (2023)

Invertibility in the misère multiverse
by: Davies, Alfie, et al.
Published: (2024)

Node-Kayles on Trees
by: Songsuwan, Nuttanon
Published: (2025)

Unique Winning Opening Move in Three-Row Chomp
by: Sheiner, Erez
Published: (2026)

Cumulative Games: Who is the current player?
by: Larsson, Urban, et al.
Published: (2020)

Maximum Nim and Josephus Problem
by: Takahashi, Shoei, et al.
Published: (2024)

A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights
by: Legacci, Davide, et al.
Published: (2024)

Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
by: Su, Yiheng, et al.
Published: (2025)

The rectangular spiral or the $n_1 \times n_2 \times \cdots \times n_k$ Points Problem
by: Ripà, Marco
Published: (2024)

Markets are competitive if and only if P != NP
by: Maymin, Philip Z.
Published: (2026)