Partitionability of simplicial complexes is hard to decide in higher dimensions
Partitionability is NP-complete
Computational Complexity
Summary
Figuring out if a complex geometric shape called a simplicial complex can be broken into simpler parts in a specific way is a tough computer problem. The authors proved this problem is as hard as the most challenging problems in computer science, even when the shapes have dimension two or more. This answers a question that was open since 1995. Basically, this means there is no easy recipe to solve this problem quickly for complicated shapes.
What this means in practice
- •For topological data analysts: Know the limits of efficiently checking partitionability in shapes that represent data structures.
- •For algorithm designers: Avoid seeking efficient algorithms for deciding partitionability in higher-dimensional complexes due to its NP-completeness.
A theory result. No direct application yet.
Authors
Russ Woodroofe
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.