Testing simplicial complexes for shellability
As you point out (relayed from Frank Lutz), it seems likely that checking shellability is NP-hard.
But all is not lost:
A complex that is shellable usually has lots of shellings, and it's often quick to find them by recursively trying to extend a partial shelling. The above-mentioned answer mentions some ways that this can be made more efficient.
A (pure) complex that is not shellable often has a negative component in its $h$-vector, a certain re-encoding of the $f$-vector. See
http://en.wikipedia.org/wiki/H-vector
For non-pure complexes, you can check the so-called $h$-triangle -- see Björner and Wachs, "Shellable nonpure complexes and posets I".
Since shellable complexes (more generally sequentially Cohen-Macaulay complexes) have positive $h$-triangles, this gives a quick way of eliminating some complexes that are not shellable.
You could get a little more involved with (2), and check for positive $h$-triangles of every link in the complex, since a link in a shellable complex is shellable.
In practice, when I've had complexes that I've wanted to computationally check shellability on, I've generally found the combination of the two approaches to give me an answer. You can either first check for obvious non-shellability with (2), and if everything is positive apply (1); or else first check shellability with (1), and if the computation appears to hang, then look for a negative entry in the $h$-triangle.
(But this works for me partly because the complexes I look at usually arise from some kind of "nice" combinatorial object or process.)
Since there were no answers for a few months, I asked this question to my colleague and triangulation expert Frank Lutz. Since his response was wonderful and exhaustive, I am reproducing it here for the benefit of others who find such matters interesting.
Spoiler alert: it is very hard to test for shellability.
Testing shellability is a mess. The complexity status is open, but believed to be NP complete. There is an implementation in the polymake package:
--> Follow the links:
Objects
+ SimplicialComplex
+ Combinatorics
+ Shellable
As far as I remember, the polymake implementation is based on the Shellability checker of Masahiro Hachimori. The bad news is that the procedure uses backtracking/reverse search and thus basically goes through all possible permutations. The good news is that local conditions on homology vectors are checked, which allows one to cut the search tree and speed up computations.
In the special case of triangulated 3-balls/3-spheres, I wrote backtracking code for testing shellability myself:
# vertices # triangulated 3-balls # non-shellable 3-balls
4 1 -
5 3 -
6 12 -
7 167 -
8 10211 -
9 2451305 29
10 1831363502 277479
See http://arxiv.org/pdf/math/0604018 and http://arxiv.org/abs/math/0610022
I had a look at the 29 non-shellable 9-vertex 3-balls, the smallest of these is described here. Among these, there are rather different types. In particular, for being "shellable" or "non-shellable" it really can matter in which way some tetrahedron is attached to what has been built before, which makes testing difficult.
My guess would be that there is no way arround backtracking, although local conditions can help to achieve some speed up. For testing explicit examples (of dimension at least 3), the following will happen:
- If some example is shellable, there is a good chance
to find a shelling sequence with backtracking.
- If some example is non-shellable (and has, say, 20 or more vertices),
it will be hopeless to complete the backtrack search.
In a very recent work (https://arxiv.org/abs/1711.08436) it was shown that deciding shellability is NP-complete.