research-article

Shellability is NP-complete

Authors:

Zuzana Patáková,

Uli WagnerAuthors Info & Claims

Journal of the ACM (JACM), Volume 66, Issue 3

Article No.: 21, Pages 1 - 18

https://doi.org/10.1145/3314024

Published: 14 June 2019 Publication History

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. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.

References

[1]

S. Arora and B. Barak. 2009. Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge. http://www.cs.princeton.edu/theory/complexity/.

[2]

D. Attali, O. Devillers, M. Glisse, and S. Lazard. 2016. Recognizing shrinkable complexes is NP-complete. Journal of Computational Geometry 7, 1 (2016), 430--443.

[3]

R. H. Bing. 1983. The Geometric Topology of 3-Manifolds. American Mathematical Society Colloquium Publications, Vol. 40. American Mathematical Society, Providence, RI. x+238 pages.

[4]

A. Björner. 1980. Shellable and Cohen-Macaulay partially ordered sets. Transaction of the American Mathematical Society 260, 1 (1980), 159--183.

[5]

A. Björner. 1995. Topological methods. In Handbook of Combinatorics, Vol. 1, 2. Elsevier Science B. V., Amsterdam, 1819--1872.

Digital Library

[6]

A. Björner and M. Wachs. 1982. Bruhat order of Coxeter groups and shellability. Advances in Mathematics 43, 1 (1982), 87--100.

[7]

A. Björner and M. Wachs. 1983. On lexicographically shellable posets. Transactions of the American Mathematical Society 277, 1 (1983), 323--341.

[8]

A. Björner and M. L. Wachs. 1997. Shellable nonpure complexes and posets. II. Transactions of the American Mathematical Society 349, 10 (1997), 3945--3975.

[9]

H. Bruggesser and P. Mani. 1972. Shellable decompositions of cells and spheres. Mathematica Scandinavika 29, 2 (1972), 197--205.

[10]

G. Danaraj and V. Klee. 1974. Shellings of spheres and polytopes. Duke Mathematical Journal 41, 2 (1974), 443--451.

[11]

G. Danaraj and V. Klee. 1978. A representation of 2-dimensional pseudomanifolds and its use in the design of a linear-time shelling algorithm. Ann. Discrete Math. 2 (1978), 53--63. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976).

[12]

G. Danaraj and V. Klee. 1978. Which spheres are shellable? Annals of Discrete Mathematics 2 (1978), 33--52. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976).

[13]

Ö. Eğecioğlu and T. F. Gonzalez. 1996. A computationally intractable problem on simplicial complexes. Computational Geometry 6, 2 (1996), 85--98.

Digital Library

[14]

B. Grünbaum. 2003. Convex Polytopes (2 ed.). Graduate Texts in Mathematics, Vol. 221. Springer-Verlag, New York. xvi+468 pages. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler.

[15]

M. Hachimori. 2000. Combinatorics of Constructible Complexes. Ph.D. Dissertation. Graduate School of Arts and Sciences, the University of Tokyo.

[16]

M. Hachimori. 2008. Decompositions of two-dimensional simplicial complexes. Discrete Mathematics 308, 11 (2008), 2307--2312.

Digital Library

[17]

M. Joswig and M. E. Pfetsch. 2006. Computing optimal Morse matchings. SIAM Journal on Discrete Mathematics 20, 1 (2006), 11--25.

Digital Library

[18]

V. Kaibel and M. E. Pfetsch. 2003. Some algorithmic problems in polytope theory. In Algebra, Geometry, and Software Systems. Springer, Berlin, 23--47.

[19]

T. Lewiner, H. Lopes, and G. Tavares. 2003. Optimal discrete Morse functions for 2-manifolds. Computational Geometry 26, 3 (2003), 221--233.

Digital Library

[20]

R. Malgouyres and A. R. Francés. 2008. Determining whether a simplicial 3-complex collapses to a 1-complex is NP-complete. DGCI (2008), 177--188.

Digital Library

[21]

J. Matoušek. 2007. Using the Borsuk-Ulam Theorem. Springer-Verlag, Berlin.

[22]

P. McMullen. 1970. The maximum numbers of faces of a convex polytope. Mathematika 17, 2 (1970), 179--184.

[23]

A. Nabutovsky. 1995. Einstein structures: Existence versus uniqueness. Geometric and Functional Analysis 5, 1 (1995), 76--91.

[24]

I. Peeva, V. Reiner, and B. Sturmfels. 1998. How to shell a monoid. Mathematische Annalen 310, 2 (1998), 379--393.

[25]

J. S. Provan and L. J. Billera. 1980. Decompositions of simplicial complexes related to diameters of convex polyhedra. Mathematics of Operations Research 5, 4 (1980), 576--594.

Digital Library

[26]

C. P. Rourke and B. J. Sanderson. 1982. Introduction to Piecewise-Linear Topology. Springer-Verlag, Berlin-New York. viii+123 pages. Reprint.

[27]

J. Shareshian. 2001. On the shellability of the order complex of the subgroup lattice of a finite group. Transactions of the American Mathematical Society 353, 7 (2001), 2689--2703.

[28]

R. P. Stanley. 1996. Combinatorics and Commutative Algebra (2 ed.). Progress in Mathematics, Vol. 41. Birkhäuser Boston, Inc., Boston, MA. x+164 pages.

[29]

M. Tancer. 2016. Recognition of collapsible complexes is NP-complete. Discrete and Computational Geometry 55, 1 (2016), 21--38.

Digital Library

[30]

I. A. Volodin, V. E. Kuznetsov, and A. T. Fomenko. 1974. The problem of discriminating algorithmically the standard three-dimensional sphere. Uspekhi Matematicheskikh Nauk 29, 5 (1974), 71--168. In Russian. English translation: Russian Mathematical Surveys 29, 5 (1974), 71--172.

[31]

M. L. Wachs. 2007. Poset topology: Tools and applications. In Geometric Combinatorics. IAS/Park City Math. Ser., Vol. 13. American Mathematical Society, 497--615.

[32]

J. H. C. Whitehead. 1939. Simplicial spaces, nuclei and m-groups. Proceedings of the London Mathematical Society (2) 45, 1 (1939), 243--327.

Cited By

Welschinger J(2023) Shellable tilings on relative simplicial complexes and their h -vectors Advances in Geometry10.1515/advgeom-2023-000123:2(191-206)Online publication date: 31-Jan-2023
https://doi.org/10.1515/advgeom-2023-0001
Paták PTancer MSaha BServedio R(2023)Shellability Is Hard Even for BallsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585152(1271-1284)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585152
Skotnica MTancer M(2023)NP-Hardness of Computing PL Geometric Category in Dimension 2SIAM Journal on Discrete Mathematics10.1137/22M152396037:3(2016-2029)Online publication date: 6-Sep-2023
https://doi.org/10.1137/22M1523960
Show More Cited By

Index Terms

Shellability is NP-complete
1. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Collapsibility to a Subcomplex of a Given Dimension is NP-Complete

In this paper we extend the works of Tancer, Malgouyres and Francés, showing that $$(d,k)$$(d,k)-Collapsibility is NP-complete for $$d\ge k+2$$dźk+2 except (2, 0). By $$(d,k)$$(d,k)-Collapsibility we mean the following problem: determine whether a given ...
Obstructions to shellability, partitionability, and sequential Cohen-Macaulayness

For a property P of simplicial complexes, a simplicial complex @C is an obstruction to P if @C itself does not satisfy P but all of its proper restrictions satisfy P. In this paper, we determine all obstructions to shellability of dimension =<2, ...
A note on shellability and acyclic orientations

In this short note we discuss the shellability of (nonpure) simplicial complexes in terms of acyclic orientations of the facet-ridge incidence graphs, which shows that we can decide shellability only from the facet-ridge incidences and the total number ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 66, Issue 3

June 2019

221 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3324923

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2019

Accepted: 01 February 2019

Revised: 01 December 2018

Received: 01 April 2018

Published in JACM Volume 66, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

IST Austria
Czech-French collaboration project EMBEDS II
Charles University project
GAČR
Improvement of Internationalization in the Field of Research and Development at Charles University
IUF. M. Tancer
MSCA-IF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
335
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Welschinger J(2023) Shellable tilings on relative simplicial complexes and their h -vectors Advances in Geometry10.1515/advgeom-2023-000123:2(191-206)Online publication date: 31-Jan-2023
https://doi.org/10.1515/advgeom-2023-0001
Paták PTancer MSaha BServedio R(2023)Shellability Is Hard Even for BallsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585152(1271-1284)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585152
Skotnica MTancer M(2023)NP-Hardness of Computing PL Geometric Category in Dimension 2SIAM Journal on Discrete Mathematics10.1137/22M152396037:3(2016-2029)Online publication date: 6-Sep-2023
https://doi.org/10.1137/22M1523960
Magnard TSkotnica MTancer M(2021)Shellings and Sheddings Induced by CollapsesSIAM Journal on Discrete Mathematics10.1137/19M129082635:3(1978-2002)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1137/19M1290826
Santamaría-Galvis AWoodroofe R(2021)Shellings from Relative Shellings, with an Application to NP-CompletenessDiscrete & Computational Geometry10.1007/s00454-020-00273-166:2(792-807)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s00454-020-00273-1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents