2026-08-07T08:00:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10625 2024-03-06T10:46:18Z ddc:004 open_access

Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs Ducoffe, Guillaume girth weighted graphs approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Ducoffe 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.49 urn:nbn:de:0030-drops-106254 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.49 eng https://creativecommons.org/licenses/by/3.0/legalcode