License
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://drops.dagstuhl.de/opus/volltexte/2019/10625/
Go to the corresponding LIPIcs Volume Portal


Ducoffe, Guillaume

Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

pdf-format:
LIPIcs-ICALP-2019-49.pdf (0.5 MB)


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
Seminar: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 08.07.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI