Constructing a Distance Sensitivity Oracle with Subcubic Preprocessing Time
This research focuses on constructing a Distance Sensitivity Oracle (DSO) in subcubic preprocessing time, breaking previous barriers, and achieving constant query time. Various algorithms, techniques, and results in the realm of graph algorithms and All-Pairs Shortest Paths are discussed and compared. The main result presents a DSO with significant improvements over previous solutions. The study explores innovative approaches, such as symbolic adjacency matrix operations and unique strategies for efficient computation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Constructing a Distance Sensitivity Oracle in ? ??.????Time Hanlin Ren, IIIS, Tsinghua University Joint work with Yong Gu ? ? ? 1 / 15
Distance Sensitivity Oracles (DSOs) Given a directed graph ? = ?,? Query ?,?,? : the shortest ? ? path not passing through ?? ? ? ? A natural and well-studied problem in graph algorithms. 2 / 15
Previous Work Na ve algorithm: Precompute the answer for every ?,?,? Space complexity ?3, query time ? 1 [Demetrescu et al.]: space complexity ? ?2, query time ? 1 But requires ? ??2+ ?3log? preprocessing time! [Bernstein-Karger]: ? ?? preprocessing time Matching the currently best running time for All-Pairs Shortest Paths! Still, an interesting setting: unweighted graphs? APSP is in ? ?2.5286time, using fast matrix multiplication! We consider unweighted graphs in this talk, for simplicity. Our results extend to graphs with small positive integer weights. 3 / 15
Previous Work via Fast Matrix Mult? Question: can we achieve subcubic preprocessing time? [Weimann-Yuster 10]: Yes! Preprocessing time ? ?1 ?+?, query time ? ?1+? Question: can we achieve sublinear query time? [Grandoni-Williams 12]: Yes! Preprocessing time ? ??+1/2+ ??+? 4 ?, query time ? ?1 ? Question: can we achieve constant query time? [Chechik-Cohen 20, Ren 20]: Yes! Preprocessing time ? ?2.7233, query time ? 1 ? 2.3729: matrix multiplication exponent ? 0,1 is a parameter 4 / 15
The ??/? Barrier Preprocessing time of previous DSOs: Algorithm Preprocessing time Prep. time if ? = ? ? ?8/3 Grandoni-Williams 12* ? ?2.8729 ? ?14/5 Chechik-Cohen 20 ? ?2.8729 ? ?8/3 Ren 20 ? ?2.7233 *Plus a transformation in [Ren 20] to bring the query time to ? 1 Other problems solvable by FMM have seen progress: All-pairs bottleneck path: ? ?8/3[VWY 07] ? ?5/2[DP 09] Is there a barrier at ?8/3 or can we do faster? All-pairs non-decreasing path: ? ?11/4[V 08] ? ?8/3 [DGZ 18] ? ?5/2[DJW 19] Also assuming ? = 2 here 5 / 15
Our Result Main result: a DSO with ? ?2.5794preprocessing time and constant query time Improving all previous results Breaking the ?8/3barrier Techniques: Adjoint of symbolic adjacency matrix Bootstrapping DSOs in [Ren 20] Unique & consistent APSP in ? ?2.5286time 6 / 15
?-Truncated DSO An ?-truncated DSO is a DSO that returns the correct answer if the answer is ?, and returns ? otherwise ?-truncated DSO prep. time ? query time ? (Normal) DSO Implicit in [Ren 20] prep. time ? + ? ?2? + ? ?3/? query time ? 1 Now, our goal is to construct ?-truncated DSO prep. time ? ??? query time ? ? (Normal) DSO prep. time ? ?3+? /2 query time ? 1 Setting ? = ?3 ? /2 prep. time ? ???+ ?2? + ?3/? Already breaks ?8/3 barrier if ? = 2; Use fast rect. MM to speed up to ?2.5794 7 / 15
Symbolic Adjacency Matrix Let ? be a directed (unweighted) graph. Let ??,?be random numbers. Actually, ??,? are analyzed as symbols that are in the end substituted by random numbers, hence the name symbolic adjacency matrix . 1 ??,?? 0 ? = ? ? ? ? otherwise SA ??,?= 1 0 0 0 0 0 38? 1 65? 0 0 0 22? 0 1 0 0 0 0 81? 0 0 19? 1 0 0 2 28? 70? 1 0 0 37? 0 0 60? 1 6 5 SA ? = 1 4 3 8 / 15
Adjoint of ?? ? Adjoint: adj ? = det ? ? 1 Theorem [Sankowski 05]. Whp over the choice of ??,?, the distance from ? to ? is the lowest degree of ? in adj SA ? ?,?. 2 1 0 0 0 0 0 38? 1 65? 0 0 0 22? 0 1 0 0 0 0 81? 0 0 19? 1 0 0 6 28? 70? 1 0 0 37? 0 0 60? 1 5 1 SA ? = 4 3 e.g. adj SA ? so the distance from 3 to 6 is 2. 3,6= 2 074 800?4 79 800?3+ 2 405?2, 1 ??,?? 0 ? = ? ? ? ? otherwise SA ??,?= 9 / 15
Handling a Vertex Failure (For simplicity, only consider vertex failures, not edge failures) Observation [Brand-Saranurak 19]: vertex failure = rank-1 update to SA ? SA ? ? = SA ? + ?? where ??is a certain rank-1 matrix ??Tassociated with ? Maintaining adj SA ? under rank-1 updates: Proof: Sherman-Morrison-Woodbury formula + matrix determinant lemma. 1 ??,?? 0 ? = ? ? ? ? otherwise SA ??,?= 10 / 15
The ?-Truncated DSO ?-truncated DSO prep. time ? ??? query time ? ? Preprocessing: compute adj SA ? Only care about the lowest ? terms! Inverting a matrix takes ? ?? arithmetic operations , and each such operation is over degree-? polynomials Time complexity: ? ? ?? Query ?,?,? : What we want is adj SA ? ? mod ?? Can be accelerated by fast rectangular mat. mult.! The final trade-off turns out to be ? ?2.5794. Shortest path from ? to ?, ? is the failed vertex ?,?= adj SA ? + ??T 1 + ?T? 1? ? 1 ? 1??T? 1 ?,? adj ? + ??T= det ? (Turns out) we only need ? 1 arithmetic operations Theorem [Sankowski 05]. Whp over the choice of ??,?, the distance from ? to ? is the lowest degree of ? in adj SA ? ?,?. 11 / 15
Summary Step 1: ?-truncated DSO via adj SA ? Idea 1: adj SA ? Idea 2: vertex failures are low-rank updates to SA ? ! (Brand-Saranurak) mod ??encodes distances up to ? (Sankowski) Step 2: From ?-truncated DSO to full DSO Essentially in [Ren 20] ?-truncated DSO prep. time ? ??? query time ? ? (Normal) DSO prep. time ? ?3+? /2 query time ? 1 Setting ? = ?3 ? /2 12 / 15
Unique & Consistent Shortest Paths (We somehow need this result to bootstrap an ?-truncated DSO to a full DSO) Problem: given an unweighted directed graph, compute incoming & outgoing shortest path trees that are consistent If a ? ? path exists in two different trees, they should be the same path ? ? ?in? ? ? ? ? ? ? ? ? ? ? ? ? ?in? ?out? ? ? 13 / 15
Unique & Consistent Shortest Paths Na ve attempt: randomly pertube the edge weights! But then you need ?3time to compute APSP Na ve attempt 2: Zwick s ?2.5286-time APSP algorithm indeed gives you shortest path trees Are they consistent? Our result: a consistent set of incoming and outgoing shortest path trees can be computed in randomized ? ?2.5286time! Matching Zwick s algorithm for APSP! Other applications of this besides DSO? 14 / 15
Further Directions Can we match DSO with APSP? Direction 1: for directed graphs, can we improve ?2.5794to ?2.5286 (matching Zwick s APSP algorithm)? I believe ?2.5794is the best we could do. But don t trust me, I used to believe the ?8/3 barrier was inherent, too! Direction 2: undirected DSO in ? ??time? Two drawbacks of our DSO: We don t support negative edge weights. (A drawback of [Ren 20].) We can only report distances, but don t support path queries. (A drawback of the algebraic methods in this work.) 15 / 15
