Faster Algorithms for Distance Sensitivity Oracles

Given a directed graph, Distance Sensitivity Oracles help find the shortest path not passing through certain nodes. This presentation explores efficient algorithms and techniques to improve preprocessing and query times, along with advancements such as bootstrapping DSOs.

• Algorithms
• Graph Theory
• Optimization
• Distance Sensitivity
• Oracle

seabrooks_s Follow

Uploaded on Feb 16, 2025 | 0 Views

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.

Presentation Transcript

1. Faster Algorithms for Distance Sensitivity Oracles Hanlin Ren (Tsinghua Oxford) Joint work with Yong Gu ? ? ? 1 / 14

2. 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 / 14

3. Previous Work Na ve algorithm: Precompute the answer for every ?,?,? Space complexity ?3, query time ? 1 [DTCR 08]: space complexity ? ?2, query time ? 1 But requires ? ??2+ ?3log? preprocessing time! [BK 09]: ? ?? 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! [Z 01] We consider unweighted graphs in this talk, for simplicity. Our results extend to graphs with small positive integer weights. 3 / 14

4. Previous Work via Fast Matrix Mult? Question: can we achieve subcubic preprocessing time? [WY 10]: Yes! Preprocessing time ? ?1 ?+?, query time ? ?1+? Question: can we achieve sublinear query time? [GW 12]: Yes! Preprocessing time ? ??+1/2+ ??+? 4 ?, query time ? ?1 ? Question: can we achieve polylog query time? [CC 20]: Yes! Preprocessing time ? ?2.8729, query time polylog ? ? 2.3729: matrix multiplication exponent ? 0,1 is a parameter 4 / 14

5. Our Results [R 20]: Preprocessing time ? ?2.7233, query time ? 1 Technique 1: bootstrapping DSOs Technique 2: hitting sets [GR 21]: Preprocessing time ? ?2.5794, query time ? 1 Technique 3: adjoint of symbolic adjacency matrix Technique 4: unique & consistent shortest path trees This talk: first 3 techniques! 5 / 14

6. Bootstrapping DSOs A byproduct of [BK 09]! Proof of Bootstrapping Thm The [BK 09] prep. algorithm Bootstrapping Theorem Given a DSO with prep. time ? and query time ?, we can construct a DSO with prep. time ? + ? ?2 ? and query time ? 1 . 1. Compute ? ?2 (carefully-chosen) DSO queries ??,??,?? 2. Compute the answers of these queries (somehow) in ? ?? time Using the slower DSO ? + ? ?2 ? 3. Build a DSO from these answers! ? + ?2?measures the complexity of DSO! Question: any other data structure problem where we could unify preprocessing and query time? 6 / 14

7. ?-Truncated DSO & Hitting Sets An ?-truncated DSO is a DSO that returns the correct answer if the answer is ?, and returns + otherwise Hitting Set Theorem Given an ?-truncated DSO with prep. time ? and query time ? 1 , we can construct a 3/2 ?-truncated DSO with prep. time ? and query time ? ?/? . ?new?,?,? : if ?old?,?,? ?: return ?old?,?,? else: return min ??old?, ,? + ?old ,?,? 1/3 ? ? a random sample of ? ?/? vertices Whp ? hits the middle 1/3 parts of each query! ? ? ? ? ? 7 / 14

8. Putting It Together ?-truncated DSO in tradeoff Using rect. mat. mul. [R 20]: ?4 ??? preprocessing time ?4 ???+ ?3/? ?2.7613 ?2.7233 ?-truncated DSO [GR 21]: ??? preprocessing time ???+ ?3/? ?2.6865 ?2.5794 Hitting set Bootstrapping: (prep ?, query ?) (prep ? + ? ?2?, query ? 1 ) 3/2 ?-truncated DSO with ? ?/? query time 9/4 ?-truncated DSO with ? ?/? query time Hitting set Bootstrapping ?-truncated DSO with large query time Hitting set Bootstrapping Hitting set Bootstrapping 3/2 ?-truncated DSO with ? 1 query time 9/4 ?-truncated DSO with ? 1 query time ?-truncated DSO with ? 1 query time Hitting Set: (prep ?, query ? 1 ) (prep ?, query ? ?/? , 3/2 ?-truncated) 8 / 14 *Bootstrapping also works for ?-truncated DSOs!

9. The Starting ?-Truncated DSO Goal: ?-truncated DSO in ? ???preprocessing time Technical tool: symbolic adjacency matrix! 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 ??,?= 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 28? 70? 1 0 0 37? 0 0 60? 1 6 5 SA ? = 1 4 3 9 / 14

10. Adjoint of ?? ? Adjoint: adj ? = det ? ? 1 Theorem [Sankowski 05]. Whp over the choices 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 ??,?= 10 / 14

11. Handling a Vertex Failure 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 ??,?= 11 / 14

12. The ?-Truncated DSO Goal: an ?-truncated DSO with prep. time ? ??? and query time ? ? Preprocessing: compute SA ? 1mod ?? 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 ? ? Can be accelerated by fast rectangular mat. mult.! 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 choices of ??,?, the distance from ? to ? is the lowest degree of ? in adj SA ? ?,?. 12 / 14

13. Wrap Up ?-truncated DSO in tradeoff Using rect. mat. mul. [R 20]: ?4 ??? preprocessing time ?4 ???+ ?3/? ?2.7613 ?2.7233 ?-truncated DSO [GR 21]: ??? preprocessing time ???+ ?3/? ?2.6865 ?2.5794 Hitting set Bootstrapping: (prep ?, query ?) (prep ? + ? ?2?, query ? 1 ) 3/2 ?-truncated DSO with ? ?/? query time 9/4 ?-truncated DSO with ? ?/? query time Hitting set Bootstrapping ?-truncated DSO with large query time Hitting set Bootstrapping Hitting set Bootstrapping 3/2 ?-truncated DSO with ? 1 query time 9/4 ?-truncated DSO with ? 1 query time ?-truncated DSO with ? 1 query time Hitting Set: (prep ?, query ? 1 ) (prep ?, query ? ?/? , 3/2 ?-truncated) 13 / 14 *Bootstrapping also works for ?-truncated DSOs!

14. 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)? Direction 2: undirected DSO in ? ??time? Two drawbacks of our DSO: We don t support negative edge weights. A drawback of bootstrapping in [R 20]. We can only report distances, but don t support path queries. A drawback of the algebraic methods in [GR 21]. 14 / 14

15. Thank you! Questions are welcome!