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

DOI10.1007/S00454-017-9915-6zbMATH Open1380.05206arXiv1703.06983OpenAlexW2604403314MaRDI QIDQ1702356FDOQ1702356

Authors: Giovanni Paolini 

Publication date: 28 February 2018

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• Parametrized complexity of expansion height
• \(D\)-collapsibility is NP-complete for \(d \geq 4\)
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• The worst way to collapse a simplex
• Some remarks on PL collapsible covers of 2-dimensional polyhedra
• Title not available (Why is that?)
• Recognition of collapsible complexes is NP-complete
• \(d\)-collapsibility is NP-complete for \(d \geq 4\)

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)