Shellability is NP-complete

11/22/2017
by   Xavier Goaoc, et al.
0

We prove that for every d≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d > 2 and k > 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d > 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset