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 Õ(mn1–a) time computes an O(na)-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(na), 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.

All Pairs Shortest Path (APSP) is a classic problem in graph theory. While for general weighted graphs there is no algorithm that computes APSP in O(n^{3-epsilon}) time (epsilon > 0), by using fast matrix multiplication algorithms, we can compute APSP in O(n^{omega}*log(n)) time (omega < 2.373) for undirected unweighted graphs, and in O(n^{2.5302}) time for directed unweighted graphs. In the current state of matters, there is a substantial gap between the upper bounds of the problem for undirected and directed graphs, and for a long time, it is remained an important open question whether it is possible to close this gap. In this paper we introduce a new parameter that measures the symmetry of directed graphs (i.e. their closeness to undirected graphs), and obtain a new parameterized APSP algorithm for directed unweighted graphs, that generalizes Seidel's O(n^{omega}*log(n)) time algorithm for undirected unweighted graphs. Given a directed unweighted graph G, unless it is highly asymmetric, our algorithms can compute APSP in o(n^{2.5}) time for G, providing for such graphs a faster APSP algorithm than the state-of-the-art algorithms for the problem.

In this paper we present two new routing techniques that allow us to obtain the following new routing schemes: A routing scheme for n-nodes, m-edges unweighted graphs that uses Õ(1/ε n2/3) space at each vertex and Õ(1/ε)-bit headers, to route a message between any pair of vertices u,v ∈ V on a (2 + ε,1)-stretch path, i.e., a path of length at most (2 + ε)• d+1, where d is the distance between u and v. This should be compared to the (2,1)-stretch and Õ(n5/3) space distance oracle of patrascu and Roditty [FOCS'10 and SIAM J. Comput. 2014] and to the (2,1)-stretch routing scheme of Abraham and Gavoille [DISC'11] that uses Õ(n3/4) space at each vertex. It follows from patrascu, Thorup and Roditty [FOCS'12] that a 2-stretch distance oracle with Õ(m2/3) space at each vertex is optimal, assuming a hardness conjecture on set intersection holds. A routing scheme for n-nodes weighted graphs with normalized diameter D, that uses Õ(1/ε n1/3log D) space at each vertex and Õ(1/ε log D)-bit headers, to route a message between any pair of vertices on a (5+ε)-stretch path. This should be compared to the 5-stretch and Õ(n4/3) space distance oracle of Thorup and Zwick [STOC'01 and J. ACM. 2005] and to the 7-stretch routing scheme of Thorup and Zwick [SPAA'01] that uses Õ(n1/3) space at each vertex. Since a 5-stretch routing scheme must use tables of Ω(n1/3) space our result is almost tight. For an integer l>1, a routing scheme for n-nodes unweighted graphs that uses Õ(l 1/ε nl/(2 l pm 1)) space at each vertex and O(1/ε)-bit headers, to route a message between any pair of vertices on a (3 pm 2 / l + ε,2)-stretch path. This should be compared to the distance oracles of patrascu, Thorup and Roditty [FOCS'12] for weighted graphs with a stretch of (3 pm 2/l) and Õ(l m1+l/(2 l pm 1)) total space. A routing scheme for n-nodes weighted graphs, that for any integer k>2, uses Õ(1/ε n1/klog D) space at each vertex and Õ(1/ε log D)-bit headers, to route a message between any pair of vertices on a (4k-7+ε)-stretch path. This improves the (4k-5)-stretch routing scheme of Thorup and Zwick [SPAA'01] and can also be used in the recent ((4 - α)k - β)-stretch routing scheme of Chechik [PODC'13] to obtain slightly better values for α and β.

This article considers the problem of computing a minimum weight cycle in weighted undirected graphs. Given a weighted undirected graph G = ( V , E , w ), let C be a minimum weight cycle of G , let w ( C ) be the weight of C , and let w max ( C ) be the weight of the maximum edge of C . We obtain three new approximation algorithms for the minimum weight cycle problem: (1) for integral weights from the range [1, M ], an algorithm that reports a cycle of weight at most 4 3 w ( C ) in O ( n 2 log n (log n + log M )) time; (2) For integral weights from the range [1, M ], an algorithm that reports a cycle of weight at most w ( C ) + w max ( C ) in O ( n 2 log n (log n + log M )) time; (3) For nonnegative real edge weights, an algorithm that for any ε > 0 reports a cycle of weight at most (4 3 + ε ) w ( C ) in O (1 ε n 2 log n (log log n )) time. In a recent breakthrough, Williams and Williams [2010] showed that a subcubic algorithm, that computes the exact minimum weight cycle in undirected graphs with integral weights from the range [1, M ], implies a subcubic algorithm for computing all-pairs shortest paths in directed graphs with integral weights from the range [− M , M ]. This implies that in order to get a subcubic algorithm for computing a minimum weight cycle, we have to relax the problem and to consider an approximated solution. Lingas and Lundell [2009] were the first to consider approximation in the context of minimum weight cycle in weighted graphs. They presented a 2-approximation algorithm for integral weights with O ( n 2 log n (log n + log M )) running time. They also posed, as an open problem, the question whether it is possible to obtain a subcubic algorithm with a c -approximation, where c < 2. The current article answers this question in the affirmative, by presenting an algorithm with 4/3-approximation and the same running time. Surprisingly, the approximation factor of 4/3 is not accidental. We show, using the new result of Williams and Williams [2010], that a subcubic combinatorial algorithm with (4/3 − ε )-approximation, where 0 < ε ≤ 1/3, implies a subcubic combinatorial algorithm for multiplying two boolean matrices.

This paper considers the problem of computing a minimum weight cycle in weighted undirected graphs. Given a weighted undirected graph G(V, E, w), let C be a minimum weight cycle of G, let w(C) be the weight of C and let wmax (C) be the weight of the maximal edge of C. We obtain three new approximation algorithms for the minimum weight cycle problem: 1. For integral weights from the range [1, M] an algorithm that reports a cycle of weight at most in O(n2 log n(log n + log M)) time. 2. For integral weights from the range [1, M] an algorithm that reports a cycle of weight at most w(C) + wmax (C) in O(n2 log n(log n + log M)) time. 3. For non-negative real edge weights an algorithm that for any ε > 0 reports a cycle of weight at most in time. In a recent breakthrough Vassilevska Williams and Williams [WW10] showed that a subcubic algorithm that computes the exact minimum weight cycle in undirected graphs with integral weights from the range [1, M] implies a subcubic algorithm for computing all-pairs shortest paths in directed graphs with integral weights from the range [–M, M]. This implies that in order to get a subcubic algorithm for computing a minimum weight cycle we have to relax the problem and to consider an approximated solution. Lingas and Lundell [LL09] were the first to consider approximation in the context of minimum weight cycle in weighted graphs. They presented a 2-approximation algorithm for integral weights with O(n2 log n(log n + log M)) running time. They also posed as an open problem the question whether it is possible to obtain a subcubic algorithm with a c-approximation, where c < 2. The current paper answers this question in the affirmative, by presenting an algorithm with 4/3-approximation and the same running time. Surprisingly, the approximation factor of 4/3 is not accidental. We show using the new result of Vassilevska Williams and Williams [WW10] that a subcubic combinatorial algorithm with (4/3 − ε)-approximation, where 0 < ε ≤ 1/3, implies a subcubic combinatorial algorithm for multiplying two boolean matrices.