Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

Abstract

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. For an undirected graph G of unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k + 2 for odd k, in time \(\mathcal{O}(n^{\frac 3 2} \sqrt {\log n }).\) Thus, in general, it yields a \(2{\frac 23}\) approximation. We study also the problem of finding a simple cycle of minimum total weight in an undirected graph with nonnegative edge weights. We present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle in an undirected graph with nonnegative integer edge weights in the range { 1,2,...,M}. This algorithm runs in time \(\mathcal{O}(n^2\log n \log M).\)

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). SIAM J. Comput. 28(4), 1167–1181 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM 42(4), 844–856 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209–223 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baswana, S., Goyal, V., Sen, S.: All-Pairs Nearly 2-Approximate Shortest-Paths in \(\mathcal{O}(n^2 \textnormal{polylog} ~n)\) Time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 666–679. Springer, Heidelberg (2005)

    Google Scholar 

  5. Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. FOCS 2006, pp. 591–602. IEEE, Los Alamitos (2006)

    Google Scholar 

  6. Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 541–552. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  7. Bollobás, B.: Extremal Graph Theory. Academic Press, New York (1978)

    MATH  Google Scholar 

  8. Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms 48, 239–256 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chan, T.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proc. STOC 2007, pp. 590–598 (2007)

    Google Scholar 

  10. Cohen, E., Zwick, U.: All-pairs small-stretch paths. Journal of Algorithms 38(2), 335–353 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1990)

    Google Scholar 

  12. Czumaj, A., Lingas, A.: Finding a heaviest triangle is not harder than matrix multiplication. In: Proc. SODA 2007, pp. 986–994 (2007)

    Google Scholar 

  13. Diestel, R.: Graph Theory. Springer, Heidelberg (2000)

    Google Scholar 

  14. Djidjev, H.: Computing the Girth of a Planar Graph. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 821–831. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  15. Dor, D., Halperin, S., Zwick, U.: All Pairs Almost Shortest Paths. SIAM J. Computing 29, 1740–1759 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  16. Horton, J.D.: A polynomial-time algorithm to find a shortest cycle basis of a graph. SIAM Journal on Computing 16(2), 358–366 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  17. Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM Journal on Computing 7(4), 413–423 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  18. Karger, D.R., Koller, D., Phillips, S.J.: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths. In: Proc. FOCS 1991, pp. 560–568 (1991)

    Google Scholar 

  19. Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: A faster algorithm for Minimum Cycle Basis of graphs. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 846–857. Springer, Heidelberg (2004)

    Google Scholar 

  20. Kavitha, T., Mehlhorn, K., Michail, D.: New Approximation Algorithms for Minimum Cycle Bases of Graphs. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 512–523. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  21. Krivelevich, M., Nutov, Z., Yuster, R.: Approximation Algorithms for Cycle Packing Problems. In: Proc. SODA 2005, pp. 556–561 (2005)

    Google Scholar 

  22. Salavatipour, M.R., Verstraete, J.: Disjoint Cycles: Integrality Gap, Hardness, and Approximation. In: Jünger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol. 3509, pp. 51–65. Springer, Heidelberg (2005)

    Google Scholar 

  23. Schank, T., Wagner, D.: Finding, Counting and Listing all Triangles in Large Graphs, An Experimental Study. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 606–609. Springer, Heidelberg (2005)

    Google Scholar 

  24. Takaoka, T.: A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 278–289. Springer, Heidelberg (2004)

    Google Scholar 

  25. Thorup, M., Zwick, U.: Approximate distance oracles. In: Proc. STOC 2001, pp. 183–192 (2001)

    Google Scholar 

  26. Vassilevska, V., Williams, R., Yuster, R.: Finding the smallest H-subgraph in real weighted graphs and related problems. In: Proc. ICALP 2006, pp. 262–273 (2006)

    Google Scholar 

  27. Vassilevska, V., Williams, R.: Finding a maximum weight triangle in n 3 − δ time, with applications. In: Proc. STOC 2006, pp. 225–231 (2006)

    Google Scholar 

  28. Yuster, R., Zwick, U.: Finding Even Cycles Even Faster. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol. 820, pp. 532–543. Springer, Heidelberg (1994)

    Google Scholar 

  29. Yuster, R., Zwick, U.: Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In: Proc. SODA 2004, pp. 254–260 (2004)

    Google Scholar 

  30. Zwick, U.: All pairs shortest paths using bridging rectangular matrix multiplication. Journal of the ACM 49(3), 289–317 (2002)

    Article  MathSciNet  Google Scholar 

  31. Zwick, U.: Exact and Approximate Distances in Graphs - A survey. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 33–48. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Lund University, 221 00, Lund, Sweden

    Andrzej Lingas & Eva-Marta Lundell

Authors
  1. Andrzej Lingas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eva-Marta Lundell
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lingas, A., Lundell, EM. (2008). Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_63

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_63

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics