In this paper we extend the works of Tancer, 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.
Collapsibility to a Subcomplex of a Given Dimension is NP-Complete
Paolini, Giovanni
2018
Abstract
In this paper we extend the works of Tancer, 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
