Expected Complexity of Barcode Reduction
Open Access
- 25 November 2025
- journal article
- research article
- Published by Springer Nature in Journal of Applied and Computational Topology
- Vol. 9 (4) , 29
Abstract
We study the algorithmic complexity of computing the persistence barcode of a randomly generated filtration. We provide a general technique to bound the expected complexity of reducing the boundary matrix in terms of the density of its reduced form. We apply this technique finding upper bounds for the average fill-in (number of non-zero entries) of the boundary matrix on Čech, Vietoris–Rips and Erdős–Rényi filtrations after matrix reduction, thus obtaining bounds on the expected complexity of the barcode computation. Our method is based on previous results on the expected Betti numbers of the corresponding complexes. Our fill-in bounds for Čech and Vietoris–Rips complexes are asymptotically tight up to a logarithmic factor. In particular, both our fill-in and computation bounds are better than the worst-case estimates. We also provide an Erdős–Rényi filtration realizing the worst-case fill-in and computation.Keywords
Funding Information
- Austrian Science Fund (P 29984-N35, P 29984-N35, W1230)
- Graz University of Technology
This publication has 29 references indexed in Scilit:
- Decomposing filtered chain complexes: Geometry behind barcoding algorithmsComputational Geometry, 2022
- Ripser: efficient computation of Vietoris–Rips persistence barcodesJournal of Applied and Computational Topology, 2021
- Topology of random geometric complexes: a surveyJournal of Applied and Computational Topology, 2018
- The Gudhi Library: Simplicial Complexes and Persistent Homology2014
- javaPlex: A Research Software Package for Persistent (Co)Homology2014
- An output-sensitive algorithm for persistent homologyComputational Geometry, 2013
- Random Geometric ComplexesDiscrete & Computational Geometry, 2011
- Topological Persistence and SimplificationDiscrete & Computational Geometry, 2002
- Random Graphs2000
- Computational Geometry2000