Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

Jakub Pachocki, Liam Roditty, Aaron Sidford +2

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and g…