Achieving Subcubic Preprocessing Time for Distance Sensitivity Oracles
Explore the advancements in achieving subcubic preprocessing time for Distance Sensitivity Oracles (DSOs) in graph algorithms, with a focus on the main results and innovative algorithms developed to improve computational efficiency. Discover how previous works have contributed to this field and the latest algorithmic developments that have simplified the process significantly.
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
Distance Sensitivity Oracles in Subcubic Preprocessing Time Hanlin Ren, IIIS, Tsinghua University ESA 2020
Distance Sensitivity Oracles (DSOs) Given a directed graph ? = ?,? Query ?,?,? : the shortest ? ? path not passing through ?? ? ? ? A natural and well-studied problem in graph algorithms.
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 best running time for All-Pairs Shortest Paths! Natural question: better preprocessing time via fast matrix multiplication? For directed graphs with small integer edge weights, APSP is in ? ?2.53time!
Previous Work via Fast Matrix Mult? Question: can we achieve subcubic preprocessing time? [Weimann-Yuster]: Yes! Preprocessing time ? ?1 ?+?, query time ? ?1+? Question: can we achieve sublinear query time? [Grandoni-Williams]: Yes! Preprocessing time ? ??+1/2+ ??+? 4 ?, query time ? ?1 ? Question: can we achieve near-constant query time? [Chechik-Cohen]: Yes! Preprocessing time ? ?2.8729, query time polylog ? ? 2.3729: matrix multiplication exponent ? 0,1 is a parameter
This Work Main result: preprocessing time ? ?2.7233, query time ? 1 ! Moreover, our algorithm is much simpler than [Chechik-Cohen]. Assumption in this talk: graph is unweighted; shortest paths are unique NOTE: the unique shortest path assumption is dangerous!
Our Algorithm in a Nutshell ?-truncated DSOs DSOs that return the correct answer when the answer is ?, and returns ? otherwise Case 1: ? is small Build an ?-truncated DSO via random sampling Case 2: ? is large Boost an ?-truncated DSO to a 3/2 ?-truncated DSO Putting it together Case 1 + log? iterations of Case 2 ? => 3/2 ? => 3/22? => => ?
Case 1: ?-truncated DSO for Small ? Recall: we only care about shortest paths with ? vertices Suppose we randomly remove 1/? fraction of vertices, then compute APSP in the rest graph Consider a query ?,?,? ( the shortest ? ? path that avoids ? ) Pr[the sample preserves the query] [ ] every vertex in the answer path are preserved Pr[? is removed] Pr 1 1/?? 1/? 1/4?. Repeat the above ? ? times. ? ? ?
Case 1: Time Complexity Recall: we took ? ? samples, and compute the APSP of each sample In APSP, we only care about distances ? Time: ? ???3 ?[Zwick 02, Grandoni-Williams 10] Preprocessing time: ? ? ???3 ? Query time: ? 1 For every failure ?, there are only ? 1 samples not containing ?
Case 2: Boost an ?-truncated DSO to a ?/? ?-truncated DSO Sample ? ?/? vertices, denoted as ? Hitting set (or bridging set) Query ?,?,? : For every ?, return minimum of ?????, ,? + ???? ,?,? ? ? ? ?
Case 2: Analysis Consider a query ?,?,? with answer in ?, 3/2 ? If ? hits the middle 1/3 portion of the answer path, then this query is answered correctly ? ? ? ? ? If you randomly sample ? ?/? vertices in ?, then w.h.p. it hits the middle 1/3 portion of every such ?,?,? .
Case 2: Wait, Whats Your Query Time? Query time: ? ?/? . But we want ? 1 query time. Lemma Given an ?-truncated DSO with preprocessing time ? and query time ? We can construct an ?-truncated DSO with preprocessing time ? + ? ?2 ? and query time ? 1 !
Case 2: From ?-truncated DSO to ?/? ?-truncated DSO DSO DSO Theorem 3/2 ?-truncated preprocessing time ? + ? ?3/? query time ? 1 3/2 ?-truncated preprocessing time ? query time ? ?/? We can boost an ?-truncated DSO to a 3/2 ?- truncated DSO, in ? ?3/? time! Lemma Bridging set Lemma Given an ?-truncated DSO with preprocessing time ? and query time ? We can construct an ?-truncated DSO with preprocessing time ? + ? ?2 ? and query time ? 1 ! DSO ?-truncated preprocessing time ? query time ? 1
Putting it Together Case 1: ?-truncated DSO in ???4 ?time Case 2: boost an ?-truncated DSO to a 3/2 ?-truncated DSO, in ?3/? time Case 2 Case 1 Case 2 Case 2 DSO DSO DSO DSO ???4 ? ?3/? ?3/ 3/2 ? ? 3/2 ? 9/4 ? ? 3 ? 5 ? ?=? Time complexity: ???4 ?+ ?3/? Improved to ?2.7233by rectangular matrix multiplication ?2.7613
The Lemma Lemma [Bernstein-Karger]: 1. Compute ? ?2DSO queries ??,??,?? 2. Compute the answers of these queries (somehow) in ? ?? time 3. Build a DSO from these results! Given an ?-truncated DSO with preprocessing time ? and query time ? We can construct an ?-truncated DSO with preprocessing time ? + ? ?2 ? and query time ? 1 ! ? ? ?2 by the slower DSO! Proof Strategy: Mimic the algorithm in [Bernstein-Karger]!
Bonus Slides: How to Break Ties? The shortest paths are not unique; ANNOYING! Assign a distinct index to every edge. Define the bottleneck of a path as the smallest index of any edge on the path. 6 4 8 3 9 ? ?,? = the largest possible bottleneck of any shortest path from ? to ?. [Duan-Pettie]: compute ? ?,? in ? ?3+? /2= ? ?2.687time! The All-Pairs Bottleneck Shortest Path problem
Bonus Slides: How to Break Ties? Recursively define the shortest path from ? to ?: Let ? ? be the edge with index ? ?,? (shortest path from ? to ? ) + ? ? + (shortest path from ? to ?) Shortest path trees can be computed in ? ?2.687time ? ? Two desirable properties: Let ? be a shortest path, Subpaths of ? are still shortest paths Let ? be any edge not in ?, then ? is still a shortest path in ? ? Proof see arXiv version! https://arxiv.org/abs/2007.11495 https://arxiv.org/abs/2007.11495
Open Questions? Preprocessing a DSO in ? ?2.53time, matching the best algorithm for APSP [Zwick]? For undirected graphs, can we preprocess a DSO in ? ??time? The size of our DSO is only ? ?2, but the preprocessing algorithm requires super-quadratic space. Improvement? Handling negative edge weights?
New Progress Ongoing work: DSO in ? ?3+? /2preprocessing time! New ingredient: symbolic computational methods from [van den Brand-Saranurak FOCS 19]
