Publications Details

The Computational Complexity of Multidimensional Persistence

Skryzalin, Jacek S.; Vongmasa, Pawin

We present findings on the computational complexity of computing multidimensional persistent homology. We first show that the worst-case computational complexity of multidimensional persistence is exponential. We then present an algorithm for computing multidimensional persistence which extends the algorithm given by Zomorodian and Carlsson for computing one-dimensional persistence. The computational complexity of our algorithm is polynomial in the size of the persistence module and exponential in the persistence dimension.