Paintbucket on graphs is PSPACE-complete
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910719903006720 |
|---|---|
| author | Saunders, Ethan J. Selinger, Peter |
| author_facet | Saunders, Ethan J. Selinger, Peter |
| contents | The game of Paintbucket was recently introduced by Amundsen and Erickson. It is played on a rectangular grid of black and white pixels. The players alternately fill in one of their opponent's connected components with their own color, until the entire board is just a single color. The player who makes the last move wins. It is not currently known whether there is a simple winning strategy for Paintbucket. In this paper, we consider a natural generalization of Paintbucket that is played on an arbitrary simple graph, and we show that the problem of determining the winner in a given position of this generalized game is PSPACE-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19373 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Paintbucket on graphs is PSPACE-complete Saunders, Ethan J. Selinger, Peter Combinatorics Computational Complexity 91A46 (Primary) 91A05, 68Q17 (Secondary) The game of Paintbucket was recently introduced by Amundsen and Erickson. It is played on a rectangular grid of black and white pixels. The players alternately fill in one of their opponent's connected components with their own color, until the entire board is just a single color. The player who makes the last move wins. It is not currently known whether there is a simple winning strategy for Paintbucket. In this paper, we consider a natural generalization of Paintbucket that is played on an arbitrary simple graph, and we show that the problem of determining the winner in a given position of this generalized game is PSPACE-complete. |
| title | Paintbucket on graphs is PSPACE-complete |
| topic | Combinatorics Computational Complexity 91A46 (Primary) 91A05, 68Q17 (Secondary) |
| url | https://arxiv.org/abs/2411.19373 |