Ducoffe, Guillaume
Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
Abstract
Given an nvertex medge graph G with nonnegative edgeweights, 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 subquadratictime approximation algorithm for the girth of unweighted graphs.
 Then, we turn our algorithm into a deterministic (2+epsilon)approximation for graphs with arbitrary nonnegative edgeweights, at the price of a slightly worse runningtime in O~(n^{5/3}polylog(1/epsilon)+m). For that, we introduce a generic method in order to obtain a polynomialfactor 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 4approximation for graphs with nonnegative edgeweights. This can be derandomized, thereby leading to an O~(n^{5/3})time deterministic 4approximation for graphs with polynomially bounded integer weights, and an O~(n^{5/3}polylog(1/epsilon))time deterministic (4+epsilon)approximation for graphs with nonnegative edgeweights.
To the best of our knowledge, these are the first known subquadratictime 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:149:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10625},
URN = {urn:nbn:de:0030drops106254},
doi = {10.4230/LIPIcs.ICALP.2019.49},
annote = {Keywords: girth, weighted graphs, approximation algorithms}
}
04.07.2019
Keywords: 

girth, weighted graphs, approximation algorithms 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 