2016/11/02 by Jakub Pachocki, Liam Roditty, Pachocki, Jakub +7
Computer Science · #Complexity and Algorithms in Graphs #Parallel Computing and Optimization Techniques #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1611.00721
The girth of a graph, i.e. the length of its shortest cycle, is a fundamental\ngraph parameter. Unfortunately all known algorithms for computing, even\napproximately, the girth and girth-related structures in directed weighted\nm-edge and n-node graphs require \Ω(\min n\ω, mn ) time (for\n2\≤\ω<2.373). In this paper, we drastically improve these runtimes as\nfollows:\n * Multiplicative Approximations in Nearly Linear Time: We give an algorithm\nthat in widetildeO(m) time computes an widetildeO(1)-multiplicative\napproximation of the girth as well as an widetildeO(1)-multiplicative\nroundtrip spanner with widetildeO(n) edges with high probability (w.h.p).\n * Nearly Tight Additive Approximations: For unweighted graphs and any \α\n\∈ (0,1) we give an algorithm that in widetildeO(mn1 - \α) time\ncomputes an O(n^\α)-additive approximation of the girth w.h.p, and\npartially derandomize it. We show that the runtime of our algorithm cannot be\nsignificantly improved without a breakthrough in combinatorial Boolean matrix\nmultiplication.\n Our main technical contribution to achieve these results is the first nearly\nlinear time algorithm for computing roundtrip covers, a directed graph\ndecomposition concept key to previous roundtrip spanner constructions.\nPreviously it was not known how to compute these significantly faster than\n\Ω(\min n^\ω, mn ) time. Given the traditional difficulty in\nefficiently processing directed graphs, we hope our techniques may find further\napplications.\n