## Abstract

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph *G* with *m* edges and *n* vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over
\(\mathbb{F}_{2}\)
generated by these vectors is the cycle space of *G*. A set of cycles is called a cycle basis of *G* if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of *G*. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering.

The previous best algorithm for computing a minimum cycle basis has running time *O*(*m*
^{ω}
*n*), where *ω* is the best exponent of matrix multiplication. It is presently known that *ω*<2.376. We exhibit an *O*(*m*
^{2}
*n*+*mn*
^{2}log *n*) algorithm. When the edge weights are integers, we have an *O*(*m*
^{2}
*n*) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in *O*(*m*
^{ω}) time. For any *ε*>0, we also design an 1+*ε* approximation algorithm. The running time of this algorithm is *O*((*m*
^{ω}/*ε*)log (*W*/*ε*)) for reasonably dense graphs, where *W* is the largest edge weight.

## References

- 1.
Cassell, A.C., Henderson, J.C., Ramachandran, K.: Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. Proc. R. Soc. Lond. Ser. A

**350**, 61–70 (1976) - 2.
Chua, L.O., Chen, L.: On optimally sparse cycle and coboundary basis for a linear graph. IEEE Trans. Circuit Theory

**20**, 495–503 (1973) - 3.
Cohen, E., Zwick, U.: All-pairs small-stretch paths. J. Algorithms

**38**, 335–353 (2001) - 4.
Coppersmith, D., Winograd, S.: Matrix multiplications via arithmetic progressions. J. Symb. Comput.

**9**, 251–280 (1990) - 5.
de Pina, J.C.: Applications of shortest path methods. PhD thesis, University of Amsterdam, Netherlands (1995)

- 6.
Deo, N., Prabhu, G.M., Krishnamoorthy, M.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Softw.

**8**, 26–42 (1982) - 7.
Galil, Z., Margalit, O.: All pairs shortest paths for graphs with small integer length edges. J. Comput. Syst. Sci.

**54**, 243–254 (1997) - 8.
Golynski, A., Horton, J.D.: A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In: 8th Scandinavian Workshop on Algorithm Theory (2002)

- 9.
Hartvigsen, D.: Minimum path bases. J. Algorithms

**15**(1), 125–142 (1993) - 10.
Hartvigsen, D., Mardon, R.: When do short cycles generate the cycle space? J. Comb. Theory Ser. B

**57**, 88–99 (1993) - 11.
Hartvigsen, D., Mardon, R.: The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. J. Discret. Math.

**7**(3), 403–418 (1994) - 12.
Horton, J.D.: A polynomial-time algorithm to find a shortest cycle basis of a graph. SIAM J. Comput.

**16**, 359–366 (1987) - 13.
Hubicka, E., Syslo, M.M.: Minimal bases of cycles of a graph. Recent Adv. Graph. Theory, 283–293 (1975)

- 14.
Kavitha, T., Mehlhorn, K., Michail, D.: New approximation algorithms for minimum cycle bases of graphs. In: Proceedings of 24th International Symposium on Theoretical Aspects of Computer Science (STACS) (2007)

- 15.
Kolasinska, E.: On a minimum cycle basis of a graph. Zastos. Mat.

**16**, 631–639 (1980) - 16.
Mehlhorn, K., Michail, D.: Implementing minimum cycle basis algorithms. In: Proceedings of 4th International Workshop on Experimental and Efficient Algorithms. Lecture Notes in Computer Science, vol. 3503, pp. 32–43. Springer, New York (2005)

- 17.
Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res.

**7**, 67–80 (1982) - 18.
Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 267–276 (2002)

- 19.
Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci.

**51**, 400–403 (1995) - 20.
Stepanec, G.F.: Basis systems of vector cycles with extremal properties in graphs. Uspekhi Mat. Nauk.

**19**, 171–175 (1964) - 21.
Tewari, G., Gotsman, C., Gortler, S.J.: Meshing genus-1 point clouds using discrete one-forms. Comput. Graph.

**30**(6), 917–926 (2006) - 22.
Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM

**46**, 362–394 (1999) - 23.
Thorup, M.: Floats, integers, and single source shortest paths. J. Algorithms

**35**, 189–201 (2000) - 24.
Zwick, U.: All pairs shortest paths in weighted directed graphs—exact and approximate algorithms. In: Proceedings of the 39th Annual IEEE FOCS, pp. 310–319 (1998)

- 25.
Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969)

## Author information

### Affiliations

### Corresponding author

## Additional information

A preliminary version of this paper appeared in Kavitha et al. (31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 846–857, 2004).

T. Kavitha and K.E. Paluch were in Max-Planck-Institut für Informatik, Saarbrücken, Germany, while this work was done.

## Rights and permissions

**Open Access** This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (
https://creativecommons.org/licenses/by-nc/2.0
), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.

## About this article

### Cite this article

Kavitha, T., Mehlhorn, K., Michail, D. *et al.* An
\(\tilde{O}(m^{2}n)\)
Algorithm for Minimum Cycle Basis of Graphs.
*Algorithmica* **52, **333–349 (2008). https://doi.org/10.1007/s00453-007-9064-z

Received:

Accepted:

Published:

Issue Date:

### Keywords

- Cycle basis
- Cycle space
- Matrix multiplication
- Polynomial algorithms