PreprintarXiv licencearXiv
It's Hard to PArcK
Abstract
We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.
Related
- PArcK trees can get as hot as you want
- Hard Diagrams of Split Links
- Fluid dynamic limit of Boltzmann equation for granular hard-spheres in a nearly elastic regime
- Hard Lefschetz theorem for logarithmic sheaves twisted by pseudo-effective line bundles
- Example of exponential many collisions of identical hard disks in the plane
BibTeX
@misc{burke2026hard,
title = {{It's Hard to PArcK}},
author = {Kyle Burke and Jeffrey Leman and Craig Tennenhouse},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29441},
eprint = {2608.29441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29441},
}
RIS
TY - UNPB
TI - It's Hard to PArcK
AU - Kyle Burke
AU - Jeffrey Leman
AU - Craig Tennenhouse
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2608.29441
UR - https://arxiv.org/abs/2608.29441
AB - We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.
ER -