Constant girth approximation for directed graphs in subquadratic time

In this paper we provide a Õ( m √ n ) time algorithm that computes a 3-multiplicative approximation of the girth of a n -node m -edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. O ( mn ). Additionally, for any integer k ≥ 1, we provide a deterministic algorithm for a O ( k loglog n )-multiplicative approximation to the girth in directed graphs in Õ( m 1+1/ k ) time. Combining the techniques from these two results gives us an algorithm for a O ( k log k )-multiplicative approximation to the girth in directed graphs in Õ( m 1+1/ k ) time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs.

Authors

• Shiri Chechik
• Yang P. Liu
• Omer Rotem
• Aaron Sidford

Keywords

• girth
• spanners
• Graphs