Document Open Access Logo

Shellability is NP-Complete

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

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

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

Cite AsGet 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

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.
Keywords
  • Shellability
  • simplicial complexes
  • NP-completeness
  • collapsibility

Metrics

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

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact