|Input:||Finite abstract pure simplicial complex D given by a list of facets|
|Output:||"Yes" if D is shellable, "No" otherwise|
|Status (fixed dim.):||Open|
Given an ordering of the facets of D, it can be tested in
polynomial time whether it is a shelling order. Hence, the problem
The problem can be solved in polynomial time for one-dimensional complexes, i.e., for graphs: a graph is shellable if and only if it is connected. Even for dim(D) = 2, the status is open. In particular, it is unclear if the problem can be solved in polynomial time if D is given by a list of all simplices.
For two-dimensional pseudo-manifolds the problem can be solved in linear time (Danarj and Klee ).
|Related problems:||18, 36|