Roei Tov

TCS Journal 2023 Journal Article

Approximate distance oracles with improved stretch for sparse graphs

• Liam Roditty
• Roei Tov

SODA Conference 2018 Conference Paper

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

• Jakub Pachocki
• Liam Roditty
• Aaron Sidford
• Roei Tov
• Virginia Vassilevska Williams

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 girth-related structures in directed weighted m -edge and n -node graphs require Ω(min{ n ω, mn }) time (for 2 ≤ ω < 2. 373). In this paper, we drastically improve these runtimes as follows: • Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in Õ ( m ) time computes an Õ (1)-multiplicative approximation of the girth as well as an Õ (1)-multiplicative roundtrip spanner with Õ ( n ) edges with high probability (w. h. p). • Nearly Tight Additive Approximations: For unweighted graphs and any a ∊ (0, 1) we give an algorithm that in Õ ( mn 1– a ) time computes an O ( n a )-additive approximation of the girth, w. h. p. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial boolean matrix multiplication. We also show that if the girth is O ( n a ), then the same guarantee can be achieved via a deterministic algorithm. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than Ω( mn ) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.

SODA Conference 2011 Conference Paper

Approximating the Girth

• Liam Roditty
• Roei Tov