Michael Dobbins (Binghamton)

Shellability is NP-Complete

Abstract for the Combinatorics Seminar
2018 February 6

In "Shellability is NP-complete" by X. Goaoc, P. Paták, Z. Patáková, M. Trancer, and U. Wagner, the authors show NP-completeness of deciding whether a given pure simplicial complex of dimension at least 2 is shellable. Moreover, they show this for contractible pure simplicial complexes of dimension at least 3.


To the Combinatorics Seminar Web page.