Document Open Access Logo

Shellability is NP-Complete

Authors Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2018.41.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Shellability
  • simplicial complexes
  • NP-completeness
  • collapsibility

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We prove that for every d >= 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d >= 2 and k >= 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d >= 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.

Cite As Get BibTex

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Shellability is NP-Complete. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.41

Author Details

Xavier Goaoc
Pavel Paták
Zuzana Patáková
Martin Tancer
Uli Wagner

References

  1. S. Arora and B. Barak. Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge, 2009. URL: http://www.cs.princeton.edu/theory/complexity/.
  2. D. Attali, O. Devillers, M. Glisse, and S. Lazard. Recognizing shrinkable complexes is NP-complete. Journal of Computational Geometry, 7(1):430-443, 2016. Google Scholar
  3. R. H. Bing. The geometric topology of 3-manifolds, volume 40 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 1983. URL: http://dx.doi.org/10.1090/coll/040.
  4. A. Björner. Shellable and Cohen-Macaulay partially ordered sets. Trans. Amer. Math. Soc., 260(1):159-183, 1980. URL: http://dx.doi.org/10.2307/1999881.
  5. A. Björner. Topological methods. In Handbook of combinatorics, Vol. 1, 2, pages 1819-1872. Elsevier Sci. B. V., Amsterdam, 1995. Google Scholar
  6. A. Björner and M. Wachs. Bruhat order of Coxeter groups and shellability. Advances in Mathematics, 43(1):87-100, 1982. URL: http://dx.doi.org/10.1016/0001-8708(82)90029-9.
  7. A. Björner and M. Wachs. On lexicographically shellable posets. Trans. Amer. Math. Soc., 277(1):323-341, 1983. URL: http://dx.doi.org/10.2307/1999359.
  8. A. Björner and M. L. Wachs. Shellable nonpure complexes and posets. II. Trans. Amer. Math. Soc., 349(10):3945-3975, 1997. URL: http://dx.doi.org/10.1090/S0002-9947-97-01838-2.
  9. H. Bruggesser and P. Mani. Shellable decompositions of cells and spheres. Mathematica Scandinavica, 29(2):197-205, 1972. Google Scholar
  10. G. Danaraj and V. Klee. Shellings of spheres and polytopes. Duke Mathematical Journal, 41(2):443-451, 1974. Google Scholar
  11. G. Danaraj and V. Klee. A representation of 2-dimensional pseudomanifolds and its use in the design of a linear-time shelling algorithm. Ann. Discrete Math., 2:53-63, 1978. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). Google Scholar
  12. G. Danaraj and V. Klee. Which spheres are shellable? Ann. Discrete Math., 2:33-52, 1978. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). Google Scholar
  13. Ö. Eğecioğlu and T. F. Gonzalez. A computationally intractable problem on simplicial complexes. Comput. Geom., 6(2):85-98, 1996. URL: http://dx.doi.org/10.1016/0925-7721(95)00015-1.
  14. X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Shellability is NP-complete, 2018. Preprint, URL: https://arxiv.org/abs/1711.08436.
  15. B. Grünbaum. Convex polytopes, volume 221 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2003. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. URL: http://dx.doi.org/10.1007/978-1-4613-0019-9.
  16. M. Hachimori. Decompositions of two-dimensional simplicial complexes. Discrete Math., 308(11):2307-2312, 2008. Google Scholar
  17. M. Joswig and M. E. Pfetsch. Computing optimal Morse matchings. SIAM Journal on Discrete Mathematics, 20(1):11-25, 2006. Google Scholar
  18. V. Kaibel and M. E. Pfetsch. Some algorithmic problems in polytope theory. In Algebra, geometry, and software systems, pages 23-47. Springer, Berlin, 2003. Google Scholar
  19. T. Lewiner, H. Lopes, and G. Tavares. Optimal discrete Morse functions for 2-manifolds. Comput. Geom., 26(3):221-233, 2003. URL: http://dx.doi.org/10.1016/S0925-7721(03)00014-2.
  20. R. Malgouyres and A. R. Francés. Determining whether a simplicial 3-complex collapses to a 1-complex is NP-complete. DGCI, pages 177-188, 2008. Google Scholar
  21. J. Matoušek. Using the Borsuk-Ulam theorem. Universitext. Springer-Verlag, Berlin, 2007. Google Scholar
  22. P. McMullen. The maximum numbers of faces of a convex polytope. Mathematika, 17(2):179-184, 1970. Google Scholar
  23. A. Nabutovsky. Einstein structures: Existence versus uniqueness. Geom. Funct. Anal., 5(1):76-91, 1995. Google Scholar
  24. I. Peeva, V. Reiner, and B. Sturmfels. How to shell a monoid. Math. Ann., 310(2):379-393, 1998. Google Scholar
  25. J. S. Provan and L. J. Billera. Decompositions of simplicial complexes related to diameters of convex polyhedra. Math. Oper. Res., 5(4):576-594, 1980. URL: http://dx.doi.org/10.1287/moor.5.4.576.
  26. C. P. Rourke and B. J. Sanderson. Introduction to piecewise-linear topology. Springer Study Edition. Springer-Verlag, Berlin-New York, 1982. Reprint. Google Scholar
  27. J. Shareshian. On the shellability of the order complex of the subgroup lattice of a finite group. Trans. Amer. Math. Soc., 353(7):2689-2703, 2001. URL: http://dx.doi.org/10.1090/S0002-9947-01-02730-1.
  28. R. P. Stanley. Combinatorics and commutative algebra, volume 41 of Progress in Mathematics. Birkhäuser Boston, Inc., Boston, MA, second edition, 1996. Google Scholar
  29. M. Tancer. Recognition of collapsible complexes is NP-complete. Discrete Comput. Geom., 55(1):21-38, 2016. Google Scholar
  30. I.A. Volodin, V.E. Kuznetsov, and A.T. Fomenko. The problem of discriminating algorithmically the standard three-dimensional sphere. Usp. Mat. Nauk, 29(5):71-168, 1974. In Russian. English translation: Russ. Math. Surv. 29,5:71-172 (1974). Google Scholar
  31. M. L. Wachs. Poset topology: Tools and applications. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 497-615. American Mathematical Soc., 2007. Google Scholar
  32. J. H. C. Whitehead. Simplicial spaces, nuclei and m-groups. Proc. London Math. Soc. (2), 45(1):243-327, 1939. URL: http://dx.doi.org/10.1112/plms/s2-45.1.243.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact