 License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.49
URN: urn:nbn:de:0030-drops-106254
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10625/
 Go to the corresponding LIPIcs Volume Portal

### Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

 pdf-format:

### 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.

### BibTeX - Entry

```@InProceedings{ducoffe:LIPIcs:2019:10625,
author =	{Guillaume Ducoffe},
title =	{{Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs}},
booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages =	{49:1--49:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-109-2},
ISSN =	{1868-8969},
year =	{2019},
volume =	{132},
editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 