Homological reconstruction and simplification in \(\mathbb{R}^3\) (Q2354925)

Suppose that one has a simplicial pair \((K,L)\), can the image of the map in homology \(H_{*}(L) \rightarrow H_{*}(K)\) be realized by that of some subcomplex \(X\) where \(L \subset X \subset L\). The authors call such a subcomplex a homological reconstruction and \((K,L)\) is called reconstructible when such a complex exists. The main results show that finding such a complex is NP-hard. Similar results are obtained for the case of persistent homology arising from a level map \(K \rightarrow {\mathbb R}\). In a more positive direction the authors define a notion of an \textit{easily \(p\)-reconstructible pair}, \(p\) referring to a single dimension for the homology groups, and describe an efficient algorithm for finding a \(p\)-reconstruction of \((K,L)\). The proofs of NP-hardness use special purpose complexes, a variable gadget and a clause gadget, to produce a \(3\)-SAT problem equivalent to that of finding a reconstruction.