Shellings from relative shellings, with an application to NP-completeness

Andrés Santamaría-Galvis, Russ Woodroofe

Shellings of simplicial complexes have long been a useful tool in topological and algebraic combinatorics. Shellings of a complex expose a large amount of information in a helpful way, but are not easy to construct, often requiring deep information about the structure of the complex. It is natural to ask whether shellings may be efficiently found computationally. In a recent paper, Goaoc, Pat\'ak, Pat\'akov\'a, Tancer and Wagner gave a negative answer to this question (assuming P \neq NP), showing that the problem of deciding whether a simplicial complex is shellable is NP-complete. In this paper, we give simplified constructions of various gadgets used in the NP-completeness proof of these authors. Using these gadgets combined with relative shellability and other ideas, we also exhibit a simpler proof of the NP-completeness of the shellability decision problem.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment