PreprintCC BY-SA 4.0arXiv
Partitionability is NP-complete
Abstract
We show that the problem of deciding whether a simplicial complex is partitionable is NP-complete in dimensions two and higher, answering a 1995 question of Kleinschmidt and Onn.
Related
- A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
- Arc Kayles is PSPACE-complete
- Extension of valuation rings as limits of complete intersection algebras
- K-stability and birational rigidity of Fano 3-fold weighted complete intersections
- A short proof of the complete Crouzeix inequality in dimension three
BibTeX
@misc{woodroofe2026partitionability,
title = {{Partitionability is NP-complete}},
author = {Russ Woodroofe},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27083},
eprint = {2610.27083},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27083},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Partitionability is NP-complete
AU - Russ Woodroofe
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.27083
UR - https://arxiv.org/abs/2610.27083
AB - We show that the problem of deciding whether a simplicial complex is partitionable is NP-complete in dimensions two and higher, answering a 1995 question of Kleinschmidt and Onn.
ER -