1 Introduction

Discrete Morse theory is a powerful combinatorial tool which allows to explicitly simplify cell complexes while preserving their homotopy type [1, 4, 6, 9]. This is obtained through a sequence of “elementary collapses” of pairs of cells. Such a process might decrease the dimension of the starting complex, or sometimes even leave a single point (in which case we say that the starting complex was collapsible).

The problem of algorithmically recognising collapsibility, or finding “good” sequences of elementary collapses, has been studied extensively [2, 3, 5, 8, 10, 11]. Such problems proved to be computationally hard even for low-dimensional simplicial complexes. For 2-dimensional complexes there exists a polynomial-time algorithm to check collapsibility [8, 10], but finding the minimum number of “critical” triangles (without which the remaining complex would be collapsible) is already NP-hard [5]. In dimension \(\ge \)3, collapsibility to some 1-dimensional subcomplex [10] or even to a single point [11] were proved to be NP-complete.

In [11], Tancer also introduced the general \((d,k)\)-Collapsibility problem: determine whether a d-dimensional simplicial complex can be collapsed to some k-dimensional subcomplex. He showed that \((d,k)\)-Collapsibility is NP-complete for \(k\in \{0,1\}\) and \(d\ge 3\), extending the result of Malgouyres and Francés about NP-completeness of \((3,1)\)-Collapsibility [10]. Tancer also pointed out that the codimension 1 case (\(d=k+1\)) is polynomial-time solvable as is the (2, 0) case. He left open the question of determining the complexity status of \((d,k)\)-Collapsibility in general.

In this short paper we extend Tancer’s work, and prove that \((d,k)\)-Collapsibility is NP-complete in all the remaining cases.

Theorem 1.1

The \((d,k)\)-Collapsibility problem is NP-complete for \(d\ge k+2\), except for the case (2, 0).

To do so, we prove that \((d,k)\)-Collapsibility admits a polynomial-time reduction to \((d+1,k+1)\)-Collapsibility (Theorem 3.1). Then the main result follows by induction. The base cases of the induction are given by NP-completeness of \((3,1)\)-Collapsibility (for codimension 2) and of \((d,0)\)-Collapsibility (for codimension \(d\ge 3\)).

2 Collapsibility and Discrete Morse Theory

We refer to [7] for the definition and the basic properties of simplicial complexes, and to [9] for the definition of elementary collapses. The simplicial complexes we consider do not contain the empty simplex, unless otherwise stated.

Our focus is the following decision problem.

figure a

We are now going to recall a few definitions of discrete Morse theory [4, 6, 9], so that we can restate the \((d,k)\)-Collapsibility problem in terms of acyclic matchings.

Given a simplicial complex X, its Hasse diagram H(X) is a directed graph in which the set of nodes is the set of simplexes of X, and an arc goes from \(\sigma \) to \(\tau \) if and only if \(\tau \) is a face of \(\sigma \) and \(\dim (\sigma ) = \dim (\tau ) + 1\). We denote such an arc by \(\sigma \rightarrow \tau \). A matching \(\mathcal {M}\) on X is a set of arcs of H(X) such that every node of H(X) (i.e. every simplex of X) is contained in at most one arc in \(\mathcal {M}\). Given a matching \(\mathcal {M}\) on X, we say that a simplex \(\sigma \in X\) is critical if it does not belong to any arc in \(\mathcal {M}\). Finally we say that a matching \(\mathcal {M}\) on X is acyclic if the graph \(H(X)^\mathcal {M}\), obtained from H(X) by reversing the direction of each arc in \(\mathcal {M}\), does not contain directed cycles.

Notice that the empty set is always a valid acyclic matching, for which all simplices are critical. See Fig. 1 for an example of a non-trivial acyclic matching on the full triangle.

Fig. 1
figure 1

An acyclic matching on the full simplicial complex on three vertices, with critical simplices \(\{1,3\}\), \(\{1\}\), \(\{3\}\)

Full size image

By standard facts of discrete Morse theory (see for instance [9], Sect. 11.2), “collapsibility to some k-dimensional subcomplex” is equivalent to “existence of an acyclic matching such that the critical cells form a k-dimensional subcomplex”. Notice that, given an acyclic matching \(\mathcal {M}\) with no critical simplices of dimension \(> k\), one can always remove from \(\mathcal {M}\) the arcs between simplices of dimension \(\le k\) and obtain an acyclic matching where the critical simplices form a k-dimensional subcomplex.

Therefore the collapsibility problem can be restated as follows.

figure b

To simplify the proof of Theorem 3.1 we quote the following useful result from [9], adapting it to our notation.

Theorem 2.1

(Patchwork  theorem [9, Theorem 11.10]) Let P be a poset. Let \(\varphi :X \rightarrow P\) be an order-preserving map (where X is ordered by inclusion), and assume to have acyclic matchings on subposets \(\varphi ^{-1}(p)\) for all \(p\in P\). Then the union of these matchings is itself an acyclic matching on X.

Notice that the subposets \(\varphi ^{-1}(p)\) are not subcomplexes of X in general, but they still have a well-defined Hasse diagram (the induced subgraph of H(X)). Thus all the previous definitions (matching, critical simplex, acyclic matching) apply also to each subposet.

3 Main Result

Theorem 3.1

Let \(d>k\ge 0\). Then there is a polynomial-time reduction from \((d,k)\)-Collapsibility to \((d+1,k+1)\)-Collapsibility.

Proof

Let X be an instance of \((d,k)\)-Collapsibility, i.e. a d-dimensional simplicial complex. Let \(V = \{v_1, \dots , v_r\}\) be the vertex set of X. Construct an instance \(X'\) of \((d+1,k+1)\)-Collapsibility, i.e. a \((d+1)\)-dimensional complex, as follows. Let \(n\ge 1\) be the number of simplices in X. Introduce new vertices \(w_1, \dots , w_{n+1}\), and define \(X'\) as the simplicial complex on the vertex set \(V' = \{v_1, \dots , v_r, w_1, \dots , w_{n+1}\}\) given by

$$\begin{aligned} X' = X \cup \Big \{ \sigma \cup \big \{w_i\big \} \big | \sigma \in X, \; i=1,\,\dots ,\,n+1 \Big \}. \end{aligned}$$

Then \(X'\) has \(n(n+2)\) simplices. Roughly speaking, \(X'\) is obtained from X by attaching \(n+1\) cones of X to X. We are going to prove that X is a yes-instance of \((d,k)\)-Collapsibility if and only if \(X'\) is a yes-instance of \((d+1,k+1)\)-Collapsibility.

Suppose that X is a yes-instance of \((d,k)\)-Collapsibility. Then there exists an acyclic matching \(\mathcal {M}\) on X such that all critical simplices have dimension \(\le k\). Construct a matching \(\mathcal {M}'\) on \(X'\) as follows:

$$\begin{aligned} \mathcal {M}'= & {} \Big \{ \sigma \cup \big \{ w_1 \big \} \rightarrow \sigma \big | \sigma \in X \Big \} \cup \\&\Big \{ \sigma \cup \big \{ w_i \big \} \rightarrow \tau \cup \big \{ w_i \big \} \big | (\sigma \rightarrow \tau ) \in \mathcal {M}, \; i=2,\,\dots ,\,n+1 \Big \}. \end{aligned}$$

This matching corresponds to collapsing the first cone together with X, and every other “base-less” cone by itself (as a copy of X). Notice that the critical simplices of \(\mathcal {M}'\) do not form a subcomplex of \(X'\), even when the critical simplices of \(\mathcal {M}\) form a subcomplex of X.

To prove that \(\mathcal {M}'\) is acyclic, consider the set \(P = \{ w_1, \dots , w_{n+1} \}\) with the partial order

$$\begin{aligned} w_i < w_j \, \text { if and only if } \, i=1 \text { and } j>1. \end{aligned}$$

Let \(\varphi :X' \rightarrow P\) be the order-preserving map given by

$$\begin{aligned} \varphi (\sigma ) = {\left\{ \begin{array}{ll} w_j &{} \text {if} \, \sigma \, \mathrm{contains} \, w_j \, \mathrm{for \, some} j\ge 2;\\ w_1 &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

Then \(\mathcal {M}'\) is a union of matchings \(\mathcal {M}_j'\) on each fiber \(\varphi ^{-1}(w_j)\). The matching \(\mathcal {M}_1'\) is acyclic on \(\varphi ^{-1}(w_1)\), since the arcs of \(\mathcal {M}_1'\) define a cut of the Hasse diagram of \(\varphi ^{-1}(w_1)\). The Hasse diagram of each \(\varphi ^{-1}(w_j)\) for \(j\ge 2\) is isomorphic to \(H(X \cup \{\varnothing \})\) via the map \(\sigma \cup \{w_j\} \mapsto \sigma \), and the matching \(\mathcal {M}_j\) maps to \(\mathcal {M}\). Since \(\mathcal {M}\) is acyclic on H(X), each \(\mathcal {M}_j\) is also acyclic on \(\varphi ^{-1}(w_j)\). By the Patchwork Theorem (Theorem 2.1), \(\mathcal {M}'\) is acyclic on \(X'\).

The set of critical simplices of \(\mathcal {M}'\) is

$$\begin{aligned} \text {Cr}(X', \mathcal {M}') = \big \{ w_1 \big \} \cup \Big \{ \sigma \cup \big \{ w_i \big \} \big | \sigma \in \text {Cr}(X, \mathcal {M}) \cup \big \{\varnothing \big \}, \; i=2,\,\dots ,\,n+1 \Big \}. \end{aligned}$$

In particular, all critical simplices have dimension \(\le k+1\). Therefore \(X'\) is a yes-instance of \((d+1,k+1)\)-Collapsibility.

Conversely, suppose now that \(X'\) is a yes-instance of \((d+1,k+1)\)-Collapsibility. Let \(\mathcal {M}'\) be an acyclic matching on \(X'\) such that all critical simplices have dimension \(\le k+1\). Since X contains n simplices, and there are \(n+1\) cones, there must exist an index \(j\in \{1,\,\dots ,\,n+1\}\) such that

$$\begin{aligned} \Big (\sigma \cup \big \{w_j\big \} \rightarrow \sigma \Big ) \not \in \mathcal {M}' \quad \forall \; \sigma \in X. \end{aligned}$$

In other words, simplices containing \(w_j\) are only matched with simplices containing \(w_j\). Then we can construct a matching \(\mathcal {M}\) on X as follows:

$$\begin{aligned} \mathcal {M}= \Big \{ \sigma \rightarrow \tau \big | \sigma , \tau \in X \text { satisfying } \Big (\sigma \cup \big \{ w_j \big \} \rightarrow \tau \cup \big \{ w_j \big \}\Big ) \in \mathcal {M}' \Big \}. \end{aligned}$$

Notice that if there is some 0-dimensional simplex \(\sigma = \{v\}\in X\) such that \((\{v, w_j\} \rightarrow \{w_j\}) \in \mathcal {M}'\), then \(\{v\}\) is critical with respect to \(\mathcal {M}\) (it would be matched with \(\tau =\varnothing \), which does not exist in X). The Hasse diagram of X injects into the Hasse diagram of the j-th cone via the map

$$\begin{aligned} \iota :\sigma \mapsto \sigma \cup \{ w_j \}, \end{aligned}$$

and by construction \(\mathcal {M}\) maps to \(\mathcal {M}'\). Since \(\mathcal {M}'\) is acyclic, \(\mathcal {M}\) is also acyclic. The set of critical simplices of \(\mathcal {M}\) is

$$\begin{aligned} \text {Cr}(X, \mathcal {M}) = \Big \{ \sigma \in X \big | \sigma \cup \big \{ w_j \big \} \in \text {Cr}(X', \mathcal {M}') \,\text { or }\, \Big (\sigma \cup \big \{w_j\big \} \rightarrow \big \{w_j\big \}\Big ) \in \mathcal {M}' \Big \}. \end{aligned}$$

In the first case \(\sigma \cup \{w_j\}\) has dimension \(\le k+1\), and in the second case \(\sigma \) is 0-dimensional. In particular, all critical simplices have dimension \(\le k\). Therefore X is a yes-instance of \((d,k)\)-Collapsibility. \(\square \)

The \((d,k)\)-Collapsibility problem admits a polynomial-time solution when \(d=k+1\) and also for the case (2, 0) [8, 10, 11]. Malgouyres and Francés [10] proved that \((3,1)\)-Collapsibility is NP-complete, and Tancer [11] extended this result to \((d,k)\)-Collapsibility for \(k\in \{0,\, 1\}\) and \(d\ge 3\). Using this as the base step and Theorem 3.1 as the induction step, we obtain the following result.

Theorem 3.2

The \((d,k)\)-Collapsibility problem is NP-complete for \(d\ge k+2\), except for the case (2, 0).