Document Open Access Logo

Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis

Author Abhishek Rathod

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.64.pdf
  • Filesize: 0.53 MB
  • 11 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Algebraic topology
Keywords
  • Computational topology
  • Minimum homology basis
  • Minimum cycle basis
  • Simplicial complexes
  • Matrix computations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Abhishek Rathod. Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 64:1-64:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.64

Author Details

Abhishek Rathod
  • Department of Mathematics, Technical University of Munich (TUM), Boltzmannstr. 3, 85748 Garching b. München, Germany

Funding

This research has been supported by the DFG Collaborative Research Center SFB/TRR 109 "Discretization in Geometry and Dynamics".

Acknowledgements

The author would like to thank Ulrich Bauer and Michael Lesnick for valuable discussions, and anonymous reviewers for their useful comments.

References

  1. Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn, and Romeo Rizzi. Breaking the O(m²n) barrier for minimum cycle bases. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, pages 301-312, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  2. Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum cycle and homology bases of surface-embedded graphs. JoCG, 8(2):58-79, 2017. URL: https://doi.org/10.20382/jocg.v8i2a4.
  3. Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, and Yusu Wang. Annotating simplices with a homology basis and its applications. In Fedor V. Fomin and Petteri Kaski, editors, Algorithm Theory - SWAT 2012, pages 189-200, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  4. Chao Chen and Daniel Freedman. Measuring and computing natural generators for homology groups. Comput. Geom. Theory Appl., 43(2):169-181, February 2010. URL: https://doi.org/10.1016/j.comgeo.2009.06.004.
  5. Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete & Computational Geometry, 45(3):425-448, April 2011. URL: https://doi.org/10.1007/s00454-010-9322-8.
  6. Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. J. ACM, 60(5):31:1-31:25, October 2013. URL: https://doi.org/10.1145/2528404.
  7. José Coelho de Pina. Applications of shortest path methods. PhD thesis, Universiteit van Amsterdam, 1995. Google Scholar
  8. Tamal K. Dey, Tianqi Li, and Yusu Wang. Efficient algorithms for computing a minimal homology basis. In Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics, pages 376-398, Cham, 2018. Springer International Publishing. Google Scholar
  9. Tamal K. Dey, Jian Sun, and Yusu Wang. Approximating loops in a shortest homology basis from point data. In Proceedings of the Twenty-sixth Annual Symposium on Computational Geometry, SoCG '10, pages 166-175, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1810959.1810989.
  10. Jean-Guillaume Dumas, Clément Pernet, and Ziad Sultan. Simultaneous computation of the row and column rank profiles. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, pages 181-188, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2465506.2465517.
  11. Jeff Erickson and Kim Whittlesey. Greedy optimal homotopy and homology generators. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 1038-1046, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. Google Scholar
  12. Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. Google Scholar
  13. J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput., 16(2):358-366, April 1987. URL: https://doi.org/10.1137/0216026.
  14. Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann. Rank-profile revealing gaussian elimination and the cup matrix decomposition. Journal of Symbolic Computation, 56:46-68, 2013. URL: https://doi.org/10.1016/j.jsc.2013.04.004.
  15. Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, and Katharina A. Zweig. Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review, 3(4):199-243, 2009. URL: https://doi.org/10.1016/j.cosrev.2009.08.001.
  16. Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail. New approximation algorithms for minimum cycle bases of graphs. Algorithmica, 59(4):471-488, April 2011. URL: https://doi.org/10.1007/s00453-009-9313-4.
  17. Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna Paluch. A faster algorithm for minimum cycle basis of graphs. In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Automata, Languages and Programming, pages 846-857, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  18. Kurt Mehlhorn and Dimitrios Michail. Minimum cycle bases: Faster and simpler. ACM Trans. Algorithms, 6(1):8:1-8:13, December 2009. URL: https://doi.org/10.1145/1644015.1644023.
  19. Arne Storjohann and Shiyun Yang. Linear independence oracles and applications to rectangular and low rank linear systems. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pages 381-388, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2608628.2608673.
  20. Arne Storjohann and Shiyun Yang. A relaxed algorithm for online matrix inversion. In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '15, pages 339-346, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2755996.2756672.
  21. Shiyun Yang. Algorithms for fast linear system solving and rank profile computation. Master’s thesis, University of Waterloo, 2014. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact