2018/10/24 by Ducoffe, Guillaume · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1810.10229
Given an n-vertex m-edge graph G with non negative edge-weights, the girth of G is the weight of a shortest cycle in G. For any graph G with polynomially bounded integer weights, we present a deterministic algorithm that computes, in \cal O(n5/3+m)-time, a cycle of weight at most twice the girth of G. Our approach combines some new insights on the previous approximation algorithms for this problem (Lingas and Lundell, IPL'09; Roditty and Tov, TALG'13) with Hitting Set based methods that are used for approximate distance oracles and date back from (Thorup and Zwick, JACM'05). Then, we turn our algorithm into a deterministic (2+ε)-approximation for graphs with arbitrary non negative edge-weights, at the price of a slightly worse running-time in \cal O(n5/3log^\cal O(1)(1/ε)+m). Finally, if we insist in removing the dependency in the number m of edges, we can transform our algorithms into an \cal O(n5/3)-time randomized 4-approximation for the graphs with non negative edge-weights -- assuming the adjacency lists are sorted. Combined with the aforementioned Hitting Set based methods, this algorithm can be derandomized, thereby yielding an \cal O(n5/3)-time deterministic 4-approximation for the graphs with polynomially bounded integer weights, and an \cal O(n5/3log^\cal O(1)(1/ε))-time deterministic (4+ε)-approximation for the 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.