Faster Algorithms for Distance Sensitivity Oracles

Hanlin Ren and Yong Gu from the University of Oxford presented faster algorithms for Distance Sensitivity Oracles (DSOs), a well-studied problem in graph algorithms. They discussed previous work, techniques like bootstrapping and hitting sets, and their innovative results with improved preprocessing and query times. Additionally, they explored the concept of unifying preprocessing and query times in data structure problems.

• Graph Algorithms
• Distance Sensitivity Oracles
• Faster Algorithms
• University of Oxford
• Graph Theory

hall_40 Follow

Uploaded on Sep 26, 2024 | 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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Faster Algorithms for Distance Sensitivity Oracles Hanlin Ren (University of Oxford) Joint work with Yong Gu Nov 14, Yaoclass Seminar * Work done in Tsinghua ? ? ? 1 / 16

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 / 16

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 / 16

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 / 16

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 5 / 16

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 / 16

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 / 16

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 / 16 *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 / 16

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 / 16

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 / 16

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 / 16

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 / 16 *Bootstrapping also works for ?-truncated DSOs!

14. 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? ? ? 14 / 16

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? 15 / 16

16. 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]. 16 / 16

17. Thank you! Questions are welcome!