1. Shellability is NP-Complete
- Author
-
Zuzana Patáková, Pavel Paták, Uli Wagner, Xavier Goaoc, Martin Tancer, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Mathematics and Statistics [Brno], Faculty of Science [Brno] (SCI / MUNI), Masaryk University [Brno] (MUNI)-Masaryk University [Brno] (MUNI), Institute of Science and Technology [Austria] (IST Austria), Department of Applied Mathematics [Prague] (KAM), Charles University [Prague] (CU), Bettina Speckmann and Csaba D. Tóth, Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Austria] - IST Austria (IST Austria), Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,Reduction (recursion theory) ,0102 computer and information sciences ,Collapsibility ,02 engineering and technology ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Contractible space ,01 natural sciences ,Combinatorics ,Simplicial complex ,Mathematics - Geometric Topology ,Corollary ,Artificial Intelligence ,Simple (abstract algebra) ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,[INFO]Computer Science [cs] ,[MATH]Mathematics [math] ,0101 mathematics ,Mathematics ,000 Computer science, knowledge, general works ,Simplicial complexes ,010102 general mathematics ,Geometric Topology (math.GT) ,020207 software engineering ,NP-completeness ,010201 computation theory & mathematics ,Hardware and Architecture ,Control and Systems Engineering ,Computer Science ,Computer Science - Computational Geometry ,020201 artificial intelligence & image processing ,Combinatorics (math.CO) ,NP-complete ,Partially ordered set ,Software ,Information Systems ,Shellability - Abstract
We prove that for every $d\geq 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 \ge 2$ and $k \ge 0$, deciding if a pure, $d$-dimensional, simplicial complex is $k$-decomposable is NP-hard. For $d \ge 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., Version 2: 17 pages, 11 figures. Improved readability at various places. Proof in Section 6 simplified
- Published
- 2018
- Full Text
- View/download PDF