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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.