Computability of the simple-homotopy distance $\ell(K,L)$ and vertex-free expansion to a simplex for complexes simple-homotopy equivalent to a point

Two linked questions left open by Chen–Yau–Yeh's 2001 study of graph homotopy and Graham homotopy. Elementary collapses and their inverses, elementary expansions, generate simple-homotopy equivalence of finite complexes; a normal-form rearrangement (all $m$ expansions before all $n$ collapses, so that $\#(L)=\#(K)+2m-2n$) yields the simple-homotopy distance $\ell(K,L)$: the minimum number of elementary expansions over all expansion-then-collapse representations of $L$ from $K$. Question 1: is there an algorithm computing $\ell(K,L)$ for arbitrary finite complexes — in particular $\ell(K,\mathrm{pt})$, the minimum number of expansions needed before a complex can be collapsed to a point (the value $0$ being exactly collapsibility, whose recognition is NP-complete already in dimension 3)? Question 2: must a finite complex regularly simple-homotopy equivalent to a point admit a sequence of elementary expansions, adding no new vertex, that ends at a simplex — necessarily the full simplex on its vertex set? The authors posit negative answers to both.

Background

Simple homotopy. A finite simplicial complex $K$ is a finite collection of finite sets (vertices, edges, triangles, higher-dimensional simplices) closed under taking non-empty subsets. An ordered pair $(\sigma,\tau)$ of simplices with $\sigma$ a facet (codimension-one face) of $\tau$ is a face pair; it is free in $K$ if $\sigma$ is a face of no simplex of $K$ other than $\tau$. An elementary simplicial collapse deletes a free pair from $K$; an elementary simplicial expansion is the inverse move, adjoining a new pair $(\sigma,\tau)$ such that neither $\sigma$ nor $\tau$ is in $K$ while all faces of $\tau$ other than $\sigma$ are. Two complexes are simple-homotopy equivalent when one is obtained from the other by a finite sequence of these moves; $K$ is collapsible when it collapses to a single vertex. The same definitions, via free pairs of cells, apply to regular CW complexes — cell complexes whose closed cells are homeomorphic to closed simplices with the simplex face ordering — where the moves are called regular CW collapses and expansions; 'regular simple-homotopy' refers to this setting. Simple-homotopy theory is classical (the standard textbook treatment is Cohen's); it refines homotopy type by Whitehead torsion, an algebraic obstruction valued in the Whitehead group of the fundamental group that measures exactly whether a homotopy equivalence decomposes into elementary moves — two homotopy-equivalent complexes need not be simple-homotopy equivalent, though Whitehead proved that they always are when the fundamental group is trivial.

The source paper. Chen–Yau–Yeh studied graph homotopy: the homotopy theory of graphs under the contractible transformations introduced by Ivashchenko (deletions and gluings of vertices and edges with contractible links), originally motivated by digital topology and molecular spaces (combinatorial models of discretized figures built from unit cubes). Their main reduction shows, in their own words, 'that a contractible graph transformation can be decomposed into a series of compositions of elementary CW expansions and collapses of certain associated simplicial complexes, whereby graph homotopy is reduced to a special kind of simple-homotopy': a graph $G$ is sent to its clique complex $\Delta(G)$ — the simplicial complex whose simplices are the complete subgraphs of $G$ — and graph homotopy moves translate into regular CW moves on $\Delta(G)$. In contrast, their Graham homotopy for hypergraphs (from the theory of relational database schemes) satisfies: a hypergraph Graham homotopy equivalent to a point reduces to a point by Graham collapses alone. The paper's running example is Bing's house with two rooms (a standard example of a contractible 2-dimensional complex that admits no collapse), realized as a graph $G_b$, showing that contractibility (even graph-homotopy contractibility) may require expansions (gluings), not merely vertex deletions.

The quantitative and vertex-free questions. The paper establishes a normal form — a simple-homotopy equivalence from $K$ to $L$ can be rearranged so that all $m$ elementary expansions precede all $n$ elementary collapses, $L=K(\sigma_1,\tau_1)\cdots(\sigma_m,\tau_m)(\sigma_1',\tau_1')^{-1}\cdots(\sigma_n',\tau_n')^{-1}$, whence $\#(L)=\#(K)+2m-2n$ — and defines the simple-homotopy distance $\ell(K,L)$ as the minimum number of elementary expansions in any expansion-then-collapse representation of $L$ from $K$ ($\ell(K,L)=\infty$ if $K$ and $L$ are not simple-homotopy equivalent); then $d(K,L)=\ell(K,L)+\ell(L,K)$ is a metric on finite cell complexes, with the analogous regular distance $\ell_r$ on finite regular complexes. On this basis the paper asks the two questions posed below.

The authors' motivation (verbatim from the accessible author preprint). The preprint closes with the observations that, comparing 'elementary collapses to the forward steps in a computer algorithm and elementary expansions to backtracks ... an algorithm with backtracks is essentially different from one without backtracks (possibly the difference is between polynomial and exponential)'; that for simple homotopy 'there is no straightforward algorithm to test whether a simplicial complex is contractible', while Graham homotopy does admit collapse-only reductions; and that 'the numerical characterizations for simple-homotopy and graph homotopy of simplicial complexes are particularly wanted'. For the vertex-free question, the preprint reports Whitehead's observation that 'in the category of simplical complexes one lacks flexibility to construct new cells without introducing new vertices' — the reason Whitehead introduced CW complexes.

Adjacent known results. Recognizing collapsibility — the case $\ell(K,\mathrm{pt})=0$ — is NP-complete for 3-dimensional complexes (Tancer), extending the NP-completeness of deciding whether a simplicial 3-complex collapses to a 1-complex (Malgouyres–Francés). The variant problems of d-collapsibility — reducibility to the empty complex by repeatedly collapsing a face of dimension at most $d-1$ that is contained in a unique maximal face — for $d\ge 4$, and of collapsing to a subcomplex of a given dimension, are NP-complete (Tancer; Paolini). These are polynomial-time hardness results and do not address the existence of any algorithm for $\ell$. The parametrized-complexity work of Bauer–Rathod–Spreer comes closest to Question 1: they study the decision problem whether a given 2-dimensional complex admits a simple-homotopy equivalence to a 1-dimensional complex using at most $p$ expansions ('erasability expansion height'), together with the ordered variant in which all expansions must precede all collapses — the normal form underlying $\ell$ — and prove both W[P]-complete in the parameter $p$, with the 3-expansion variant NP-complete; they note that for CW complexes the ordered and unordered variants coincide by a classical rearrangement argument, while for simplicial complexes the two may differ. Bauer–Rathod–Spreer also record, via the Whitehead observation above, that a finite complex is simple-homotopy equivalent to a point exactly when it is contractible (a contractible complex has trivial fundamental group), so that an algorithm computing $\ell(K,\mathrm{pt})$, including the $\infty$ case, would in particular decide contractibility — whose decidability is open already for 2-dimensional complexes, where it is tied to the open triviality problem for balanced presentations of the trivial group. On the practical side, Benedetti–Lai–Lofano–Lutz implement a randomized heuristic (RSHT) that combines elementary simplicial collapses with pure elementary expansions to reduce complexes, with experiments on contractible spaces and triangulated manifolds. Recognition problems for simplicial complexes can be undecidable: recognizing complexes that are nerves of good covers (a good cover of a space is a cover by open sets whose every finite intersection is empty or contractible; its nerve is the simplicial complex recording which cover elements share a point) is algorithmically unsolvable (Tancer–Tonkonog). In the neighboring Andrews–Curtis framework — which asks whether every balanced presentation of the trivial group, that is, a presentation with equally many generators and relators, can be reduced to the trivial presentation by elementary transformations — Bridson proved superexponential lower bounds on the number of moves needed to trivialize balanced presentations. None of these computes, bounds, or refutes $\ell(K,L)$, and none addresses vertex-free expandability.

Problem Statement

Both questions concern finite complexes. Question 1 is asked for finite simplicial complexes; the definitions below apply unchanged to finite regular CW complexes — cell complexes whose closed cells are closed simplices — where the moves are called regular elementary moves, and Question 2 is posed within that regular category.

Setup. For finite complexes $K$ and $L$, write $\#(K)$ for the number of cells (simplices) of $K$. An elementary expansion adjoins a pair $(\sigma,\tau)$, where $\sigma$ is a face of $\tau$ of codimension one, such that neither $\sigma$ nor $\tau$ belongs to the complex while every face of $\tau$ other than $\sigma$ does; an elementary collapse removes such a pair when it is free, meaning that $\sigma$ is contained in no simplex of the complex other than $\tau$. When $K$ and $L$ are (regularly) simple-homotopy equivalent, a normal form exists in which $L$ is obtained from $K$ by performing all $m$ elementary expansions first and all $n$ elementary collapses afterwards, with $\#(L)=\#(K)+2m-2n$. The simple-homotopy distance $\ell(K,L)$ is the minimum number $m$ of elementary expansions over all expansion-then-collapse representations of $L$ from $K$, with $\ell(K,L)=\infty$ when $K$ and $L$ are not simple-homotopy equivalent.

Question 1 (computability of the distance). Is there an algorithm which, given finite complexes $K$ and $L$, computes $\ell(K,L)$? In particular, is there an algorithm computing $\ell(K,\mathrm{pt})$: deciding whether it is finite, and if so determining the minimum number of elementary expansions needed before $K$ can be collapsed to a point?

Question 2 (vertex-free expandability). Let $K$ be a finite complex regularly simple-homotopy equivalent to a point. Must there exist a sequence of elementary expansions, none of which introduces a new vertex, taking $K$ to a simplex — necessarily the simplex on the full vertex set $V(K)$?

The source authors posit negative answers to both questions.

References

1. Beifang Chen, Shing-Tung Yau, Yeong-Nan Yeh, "Graph homotopy and Graham homotopy", Discrete Mathematics 241 (2001) 153-170. DOI: 10.1016/S0012-365X(01)00115-7, https://doi.org/10.1016/S0012-365X(01)00115-7. Author-hosted preprint: http://www.math.ust.hk/~mabfchen/Paper/Graham-Homotopy.pdf
2. Marshall M. Cohen, "A Course in Simple-Homotopy Theory", Graduate Texts in Mathematics 10, Springer, 1973. DOI: 10.1007/978-1-4684-9372-6, ISBN 9780387900551, https://link.springer.com/book/10.1007/978-1-4684-9372-6
3. Alexander V. Ivashchenko, "Representation of smooth surfaces by graphs. Transformations of graphs which do not change the Euler characteristic of graphs", Discrete Mathematics 122 (1993) 219-233. DOI: 10.1016/0012-365X(93)90297-7, https://doi.org/10.1016/0012-365X(93)90297-7
4. Romain Boulet, Etienne Fieux, Bertrand Jouve, "Simplicial simple-homotopy of flag complexes in terms of graphs", European Journal of Combinatorics 31 (2010) 161-176. DOI: 10.1016/j.ejc.2009.05.003, https://doi.org/10.1016/j.ejc.2009.05.003. Preprint arXiv:0809.1751, https://arxiv.org/abs/0809.1751
5. Jesús F. Espinoza, Martín-Eduardo Frías-Armenta, Héctor A. Hernández-Hernández, "Collapsibility and homological properties of $\mathfrak{I}$-contractible transformations", Boletín de la Sociedad Matemática Mexicana 28 (2022), article 42. DOI: 10.1007/s40590-022-00434-7, https://doi.org/10.1007/s40590-022-00434-7. Preprint arXiv:1808.07461, https://arxiv.org/abs/1808.07461
6. Etienne Fieux, Bertrand Jouve, "A hierarchy of dismantlings in graphs", arXiv:1902.04508 (2019, v2 2020), https://arxiv.org/abs/1902.04508
7. Anton Dochtermann, Jesús F. Espinoza, Martín Eduardo Frías-Armenta, Héctor A. Hernández-Hernández, "Minimal graphs for contractible and dismantlable properties", Discrete Mathematics 346 (2023) 113516. DOI: 10.1016/j.disc.2023.113516, https://doi.org/10.1016/j.disc.2023.113516. Preprint arXiv:2109.06729, https://arxiv.org/abs/2109.06729
8. Anton Dochtermann, Takahiro Matsushita, "Simple homotopy of flag simplicial complexes and contractible contractions of graphs", Topology and its Applications 367 (2025) 109326. DOI: 10.1016/j.topol.2025.109326, https://doi.org/10.1016/j.topol.2025.109326. Preprint arXiv:2312.10976, https://arxiv.org/abs/2312.10976
9. Rémy Malgouyres, Angel R. Francés, "Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete", in: Discrete Geometry for Computer Imagery (DGCI 2008), Lecture Notes in Computer Science 4992, Springer, 2008, pp. 177-188. DOI: 10.1007/978-3-540-79126-3_17, https://doi.org/10.1007/978-3-540-79126-3_17
10. Martin Tancer, "d-collapsibility is NP-complete for d greater or equal to 4", arXiv:0808.1991, https://arxiv.org/abs/0808.1991; conference version in Electronic Notes in Discrete Mathematics 34 (2009) 53-57, DOI: 10.1016/j.endm.2009.07.009, https://doi.org/10.1016/j.endm.2009.07.009
11. Martin Tancer, "Recognition of collapsible complexes is NP-complete", Discrete & Computational Geometry 55 (2016) 21-38. DOI: 10.1007/s00454-015-9747-1, https://doi.org/10.1007/s00454-015-9747-1. Preprint arXiv:1211.6254, https://arxiv.org/abs/1211.6254
12. Giovanni Paolini, "Collapsibility to a subcomplex of a given dimension is NP-complete", Discrete & Computational Geometry 59 (2018) 246-251. DOI: 10.1007/s00454-017-9915-6, https://doi.org/10.1007/s00454-017-9915-6. Preprint arXiv:1703.06983, https://arxiv.org/abs/1703.06983
13. Martin Tancer, Dmitry Tonkonog, "Nerves of Good Covers Are Algorithmically Unrecognizable", SIAM Journal on Computing 42 (4) (2013) 1697-1719. DOI: 10.1137/120891204, https://doi.org/10.1137/120891204. Preprint arXiv:1205.6082 "Good covers are algorithmically unrecognizable", https://arxiv.org/abs/1205.6082
14. Martin R. Bridson, "The complexity of balanced presentations and the Andrews-Curtis conjecture", arXiv:1504.04187 (2015), https://arxiv.org/abs/1504.04187
15. Ulrich Bauer, Abhishek Rathod, Jonathan Spreer, "Parametrized Complexity of Expansion Height", in: Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics (LIPIcs) 144, 2019, pp. 13:1-13:15. DOI: 10.4230/LIPIcs.ESA.2019.13, https://doi.org/10.4230/LIPIcs.ESA.2019.13. Preprint arXiv:1910.09228, https://arxiv.org/abs/1910.09228
16. Bruno Benedetti, Crystal Lai, Davide Lofano, Frank H. Lutz, "Random simple-homotopy theory", Journal of Applied and Computational Topology 8 (2024) 531-555. DOI: 10.1007/s41468-023-00139-4, https://doi.org/10.1007/s41468-023-00139-4. Preprint arXiv:2107.09862, https://arxiv.org/abs/2107.09862