Sampling conditions for recovering the homology of a set using topological persistence are much weaker than sampling conditions required by any known algorithm for producing a topologically correct reconstruction. Under the former sampling conditions which we call weak sampling conditions, we give an algorithm that outputs a topologically correct reconstruction. Unfortunately, even though the algorithm terminates, its time complexity is unbounded. Motivated by the question of knowing if a polynomial time algorithm for reconstruction exists under the weak sampling conditions, we identify at the heart of our algorithm a test which requires answering the following question: given two 2-dimensional simplicial complexes L ⊂ K, does there exist a simplicial complex containing L and contained in K which realizes the persistent homology of L into K? We call this problem the homological simplification of the pair (K,L) and prove that this problem is NP-complete, using a reduction from 3SAT.
Travail réalisé en collaboration avec Dominique Attali.
This document was translated from LATEX by HEVEA.