In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that (d,k)-collapsibility is NP-complete for d≥k+2 except (2,0). By (d,k)-collapsibility we mean the following problem: determine whether a given d-dimensional simplicial complex can be collapsed to some k-dimensional subcomplex. The question of establishing the complexity status of (d,k)-collapsibility was asked by Tancer, who proved NP-completeness of (d,0) and (d,1)-collapsibility (for d≥3). Our extended result, together with the known polynomial-time algorithms for (2,0) and d=k+1, answers the question completely.

Giovanni Paolini (2018). Collapsibility to a Subcomplex of a Given Dimension is NP-Complete. DISCRETE & COMPUTATIONAL GEOMETRY, 59(1), 246-251 [10.1007/s00454-017-9915-6].

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

Giovanni Paolini
2018

Abstract

In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that (d,k)-collapsibility is NP-complete for d≥k+2 except (2,0). By (d,k)-collapsibility we mean the following problem: determine whether a given d-dimensional simplicial complex can be collapsed to some k-dimensional subcomplex. The question of establishing the complexity status of (d,k)-collapsibility was asked by Tancer, who proved NP-completeness of (d,0) and (d,1)-collapsibility (for d≥3). Our extended result, together with the known polynomial-time algorithms for (2,0) and d=k+1, answers the question completely.
2018
Giovanni Paolini (2018). Collapsibility to a Subcomplex of a Given Dimension is NP-Complete. DISCRETE & COMPUTATIONAL GEOMETRY, 59(1), 246-251 [10.1007/s00454-017-9915-6].
Giovanni Paolini
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/943214
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact