All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

Christian Sommer
ICALP 2016 - 43rd International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Complexity and Games (pp. 55:1-13)

Given an undirected, unweighted graph \(G\) on \(n\) nodes, there is an \(O(n^2 poly\log n)\)-time algorithm that computes a data structure called distance oracle of size \(O(n^{5/3} poly\log n)\) answering approximate distance queries in constant time. For nodes at distance \(d\) the distance estimate is between \(d\) and \(2d+1\).

This new distance oracle improves upon the oracles of Pătraşcu and Roditty (FOCS 2010), Abraham and Gavoille (DISC 2011), and Agarwal and Brighten Godfrey (PODC 2013) in terms of preprocessing time, and upon the oracle of Baswana and Sen (SODA 2004) in terms of stretch. Our running time analysis is tight (up to logarithmic factors) due to a recent lower bound of Abboud and Bodwin (STOC 2016).

Techniques include dominating sets, sampling, balls, and spanners, and the main contribution lies in the way these techniques are combined. Perhaps the most interesting aspect from a technical point of view is the application of a spanner without incurring its constant additive stretch penalty.

@inproceedings{Som16,
 author    = {Christian Sommer},
 title     = {All-Pairs Approximate Shortest Paths 
              and Distance Oracle Preprocessing},
 year      = {2016},
 booktitle = {43rd International Colloquium on 
              Automata, Languages and Programming (ICALP)},
 pages     = {55:1--13},
 url       = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.55},
 doi       = {10.4230/LIPIcs.ICALP.2016.55}
}

Official version
Local version (578.3 KB)
Slides (1.2 MB)

Knudsen recently discovered a deterministic algorithm to compute an additive spanner in quadratic time. Woodruff's spanner algorithm is randomized (Monte Carlo). Combined with other improvements, Knudsen also provides a randomized (Las Vegas) quadratic-time algorithm that computes a \((2,1)\)-approximate distance oracle using \(O(n^{5/3})\) space, which is the new state of the art. His paper was accepted to ICALP 2017.

Home → Publications → All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing