| Input: | Finite abstract pure simplicial complex D given by a list of facets |
|---|---|
| Output: | "Yes" if D is shellable, "No" otherwise |
| Status (general): | Open |
|---|---|
| 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
in NP.
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 [13]). |
| Related problems: | 18, 36 |
|---|