Optimal Girth Approximation for Dense Directed Graphs

In this paper we provide a Õ(n2) time algorithm that computes a 2-multiplicative approximation of the girth of an n-node m-edge directed graph with non-negative edge weights. We also provide an additional algorithm that computes a 2-multiplicative approximation of the girth in time 1. Our results naturally provide algorithms for improved constructions of 4-roundtrip spanners, the analog of spanners in directed graphs. Our algorithm is optimal (up to a log n factor) for dense graphs with m = Θ(n2). For comparison, previously, the best approximation ratio with a similar running time for dense graphs was O(log n log log n) [1]. Moreover, unlike previous algorithms, our algorithm neither assumes integer weights, nor does it depend on the maximum edge weight of the graph.