Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

Author Guillaume Ducoffe



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.49.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Guillaume Ducoffe
  • National Institute for Research and Development in Informatics, Romania
  • The Research Institute of the University of Bucharest ICUB, Romania
  • University of Bucharest, Romania

Cite AsGet BibTex

Guillaume Ducoffe. Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.49

Abstract

Given an n-vertex m-edge graph G with non-negative edge-weights, a shortest cycle of G is one minimizing the sum of the weights on its edges. The girth of G is the weight of such a shortest cycle. We obtain several new approximation algorithms for computing the girth of weighted graphs: - For any graph G with polynomially bounded integer weights, we present a deterministic algorithm that computes, in O~(n^{5/3}+m)-time, a cycle of weight at most twice the girth of G. This matches both the approximation factor and - almost - the running time of the best known subquadratic-time approximation algorithm for the girth of unweighted graphs. - Then, we turn our algorithm into a deterministic (2+epsilon)-approximation for graphs with arbitrary non-negative edge-weights, at the price of a slightly worse running-time in O~(n^{5/3}polylog(1/epsilon)+m). For that, we introduce a generic method in order to obtain a polynomial-factor approximation of the girth in subquadratic time, that may be of independent interest. - Finally, if we assume that the adjacency lists are sorted then we can get rid off the dependency in the number m of edges. Namely, we can transform our algorithms into an O~(n^{5/3})-time randomized 4-approximation for graphs with non-negative edge-weights. This can be derandomized, thereby leading to an O~(n^{5/3})-time deterministic 4-approximation for graphs with polynomially bounded integer weights, and an O~(n^{5/3}polylog(1/epsilon))-time deterministic (4+epsilon)-approximation for graphs with non-negative edge-weights. To the best of our knowledge, these are the first known subquadratic-time approximation algorithms for computing the girth of weighted graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Approximation algorithms analysis
Keywords
  • girth
  • weighted graphs
  • approximation algorithms

Metrics

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

References

  1. D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. Google Scholar
  2. S. Baswana and S. Sen. Approximate distance oracles for unweighted graphs in expected O (n 2) time. ACM Transactions on Algorithms (TALG), 2(4):557-577, 2006. Google Scholar
  3. J. A. Bondy and U. S. R. Murty. Graph theory. Grad. Texts in Math., 2008. Google Scholar
  4. W. Brown. On graphs that do not contain a Thomsen graph. Canadian Mathematical Bulletin, 9(2):1-2, 1966. Google Scholar
  5. S. Chechik. Approximate distance oracles with constant query time. In ACM STOC'14, pages 654-663, 2014. Google Scholar
  6. S. Chechik, D. Larkin, L. Roditty, G. Schoenebeck, R. Tarjan, and V. Vassilevska Williams. Better approximation algorithms for the graph diameter. In SODA, pages 1041-1052. SIAM, 2014. Google Scholar
  7. S. Dahlgaard, M. Knudsen, and M. Stöckel. New Subquadratic Approximation Algorithms for the Girth. Technical report, arXiv, 2017. URL: http://arxiv.org/abs/1704.02178.
  8. G. Ducoffe. Faster approximation algorithms for computing shortest cycles on weighted graphs. Technical report, arXiv, 2018. URL: http://arxiv.org/abs/1810.10229.
  9. A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413-423, 1978. Google Scholar
  10. A. Lingas and E. Lundell. Efficient approximation algorithms for shortest cycles in undirected graphs. Information Processing Letters, 109(10):493-498, 2009. Google Scholar
  11. J. Pachocki, L. Roditty, A. Sidford, R. Tov, and V. Vassilevska Williams. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. In SODA, pages 1374-1392. SIAM, 2018. Google Scholar
  12. M. Patrascu and L. Roditty. Distance Oracles beyond the Thorup-Zwick Bound. SIAM Journal on Computing, 43(1):300-311, 2014. Google Scholar
  13. S. Robinson. Toward an optimal algorithm for matrix multiplication. SIAM news, 38(9):1-3, 2005. Google Scholar
  14. L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. In ICALP, pages 261-272. Springer, 2005. Google Scholar
  15. L. Roditty and R. Tov. Approximating the girth. ACM Transactions on Algorithms (TALG), 9(2):15, 2013. Google Scholar
  16. L. Roditty and V. Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In FOCS, pages 180-189. IEEE, 2011. Google Scholar
  17. L. Roditty and V. Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In SODA, pages 833-845. SIAM, 2012. Google Scholar
  18. M. Thorup and U. Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  19. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In FOCS, pages 645-654. IEEE, 2010. Google Scholar
  20. C. Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In ACM/SIAM SODA'12, pages 202-208, 2012. Google Scholar
  21. R. Yuster and U. Zwick. Finding even cycles even faster. SIAM Journal on Discrete Mathematics, 10(2):209-222, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail