Col is PSPACE-complete on Triangular Grids
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916583843037184 |
|---|---|
| author | Burke, Kyle Tennenhouse, Craig |
| author_facet | Burke, Kyle Tennenhouse, Craig |
| contents | We demonstrate that Col is PSPACE-complete on triangular grid graphs via a reduction from Bounded Two-Player Constraint Logic. This is the most structured graph family that Col is known to be computationally hard for. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Col is PSPACE-complete on Triangular Grids Burke, Kyle Tennenhouse, Craig Computational Complexity Combinatorics 91A46 F.1.3; G.2.1; F.2.2 We demonstrate that Col is PSPACE-complete on triangular grid graphs via a reduction from Bounded Two-Player Constraint Logic. This is the most structured graph family that Col is known to be computationally hard for. |
| title | Col is PSPACE-complete on Triangular Grids |
| topic | Computational Complexity Combinatorics 91A46 F.1.3; G.2.1; F.2.2 |
| url | https://arxiv.org/abs/2501.06574 |