pipette
ESEspañol

Partitionability is NP-complete

Russ Woodroofe

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 14 pages; 4 figures