Shellability is NP-complete

Abstract : We prove that for every $d\geq 2$, deciding if a pure, $d$-dimensional, simplicial complex is shellable is \textup{NP}-hard, hence \textup{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 \textup{NP}-hard. For $d \ge 3$, both problems remain \textup{NP}-hard when restricted to contractible pure $d$-dimensional complexes.
Type de document :
Communication dans un congrès
Bettina Speckmann and Csaba D. Tóth. International Symposium on Computational Geometry, 2018, Budapest, Hungary. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, 34th International Symposium on Computational Geometry (SoCG 2018)
Liste complète des métadonnées

https://hal-upec-upem.archives-ouvertes.fr/hal-01744101
Contributeur : Xavier Goaoc <>
Soumis le : mardi 27 mars 2018 - 10:03:00
Dernière modification le : jeudi 5 juillet 2018 - 14:45:33

Lien texte intégral

Identifiants

  • HAL Id : hal-01744101, version 1
  • ARXIV : 1711.08436

Citation

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Shellability is NP-complete. Bettina Speckmann and Csaba D. Tóth. International Symposium on Computational Geometry, 2018, Budapest, Hungary. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, 34th International Symposium on Computational Geometry (SoCG 2018). 〈hal-01744101〉

Partager

Métriques

Consultations de la notice

31