On the Complexity of Recognition of 2-collapsibility
Ming Ming Tan · 2008
A simpl icial complex is d-collapsible if it can be reduced to an empty simplex by repeatedly removing face of dimension less than d that it is contained in a unique maximal face. These complexes have been studied since every complex that is the nerve of a family of convex sets in R d is d-collapsible. We sho w that the question whether a given complex is 2-collapsible can be solved in polynomial time.