Collapsibility to a subcomplex of a given dimension is NP-complete

DOI10.1007/S00454-017-9915-6MaRDI QIDQ1702356zbMATH OpenOpenAlexFDO

Authors Giovanni Paolini

Publication date 28 February 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.06983

zbMATH Keywords

discrete Morse theorysimplicial complexesNP-hardnesscollapsibility

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of simplicial complexes (05E45)

Abstract: In this paper we extend the works of Tancer and of Malgouyres and Franc'es, showing that $(d,k)$-collapsibility is NP-complete for $dgeqk+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 $dgeq3$). Our extended result, together with the known polynomial-time algorithms for $(2,0)$ and $d=k+1$, answers the question completely.

Recommendations

• Recognition of collapsible complexes is NP-complete
• \(D\)-collapsibility is NP-complete for \(d \geq 4\)
• \(d\)-collapsibility is NP-complete for \(d \geq 4\)
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Recognizing shrinkable complexes is NP-complete

Cites work

• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• A computationally intractable problem on simplicial complexes
• Combinatorial algebraic topology
• Computing Optimal Morse Matchings
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Discrete Morse theory for cellular resolutions
• Morse theory for cell complexes
• On discrete Morse functions and combinatorial decompositions
• Random discrete Morse theory and a new library of triangulations
• Recognition of collapsible complexes is NP-complete

Cited in

(8)

• Some remarks on PL collapsible covers of 2-dimensional polyhedra
• The worst way to collapse a simplex
• scientific article; zbMATH DE number 1762842 (Why is no real title available?)
• Recognition of collapsible complexes is NP-complete
• Parametrized complexity of expansion height
• \(d\)-collapsibility is NP-complete for \(d \geq 4\)
• \(D\)-collapsibility is NP-complete for \(d \geq 4\)
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete

Describes a project that uses

Uses Software

• Library of Triangulations

This page was built for publication: Collapsibility to a subcomplex of a given dimension is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702356)