2026-07-26T03:03:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12222 2024-03-06T10:49:44Z ddc:004 open_access

Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis Rathod, Abhishek Computational topology Minimum homology basis Minimum cycle basis Simplicial complexes Matrix computations 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 ℤ₂ 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. [Dey et al., 2018], runs in O(N^ω + N² g) time, where N denotes the number of simplices in K, g denotes the rank of the 1-homology group of K, and ω 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 Õ(m^ω) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(m^ω + N m^{ω-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^ω) time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in Õ(m^ω) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhishek Rathod 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.64 urn:nbn:de:0030-drops-122223 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.64 eng https://creativecommons.org/licenses/by/3.0/legalcode