Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis

We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the $1$-dimensional homology classes with $\mathbb{Z}_2$ coefficients in a given simplicial complex $K$. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al., runs in $O(N^\omega + N^2 g)$ time, where $N$ denotes the number of simplices in $K$, $g$ denotes the rank of the $1$-homology group of $K$, and $\omega$ denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex $K$. The first algorithm runs in $\tilde{O}(m^\omega)$ time, where $m$ denotes the number of edges in $K$, whereas the second algorithm runs in $O(m^\omega + N m^{\omega-1})$ time. We also study the problem of finding a minimum cycle basis in an undirected graph $G$ with $n$ vertices and $m$ edges. The best known algorithm for this problem runs in $O(m^\omega)$ time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in $\tilde{O}(m^\omega)$ time.