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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10625/
Ducoffe, Guillaume
Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10625},
URN = {urn:nbn:de:0030-drops-106254},
doi = {10.4230/LIPIcs.ICALP.2019.49},
annote = {Keywords: girth, weighted graphs, approximation algorithms}
}
|
Keywords: |
|
girth, weighted graphs, approximation algorithms |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
