Approximate Distance Oracles Under Multiple Vertex Failures Study
Explore the challenges of maintaining approximate shortest paths in a graph under vertex failures, presenting solutions and complexities. Delve into the difficulty of guarding failures and strategies for handling edge and high-degree vertex failures.
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
Approximate Distance Oracles Subject to Multiple Vertex Failures Hanlin Ren, IIIS, Tsinghua University Joint work with Ran Duan & Yong Gu
The Problem Problem: given a graph, maintain approx. shortest paths under vertex failures. Query ?,?,? shortest path from ? to ? that avoids ? source vertex target vertex failed vertex optimal path
How Hard Is the Problem? ? failures, undirected graph Desired query time: poly ?,log? approx. distance connectivity [PT 07] [DP 10] Fully dynamic connectivity [CLPR 10]: ? ? -approx [CCFK 17]: 1 + ? -approx ? edge failures ?? This work! ? vertex failures [DP 10] [DP 17]
Our Results We present two oracles:* Space Complexity ?2.01? 1log?? ? Query Time poly log?,?,? 1 Stretch 1 + ? Space Complexity ?2.01poly log?,? Query Time poly log?,? Stretch poly log?,? *assuming edge weights in 1,poly ?
Subroutine: Guarding the Failures Illustration of the difficulty of vertex failures Find a set of vertices ? to guard the failures a) If ? is close to a failure, then ? is also close to ?* b) |?| is small. Query time = poly ? 1 + ? -approx. ? *in the graph with failures removed
Guarding Edge Failures ? = set of vertices incident to edge failures ? ? ? ? 2? a) If ? is close to a failure, then ? is also close to ? b) |?| is small.
What about Vertex Failures? Natural attempt: ? is the set of vertices adjacent to failures ? is too large! In general, low-degree failures are fine. The problem is high-degree failures! a) If ? is close to a failure, then ? is also close to ? b) |?| is small.
Attempt 2: High-Degree Hierarchy [DP10] Partition vertices into ? log? levels Guarantee: Every failure has small degree inside each level, w.r.t. a (sparse) spanner ? = the set of vertices adjacent to a failure inside some level, in the spanner a) If ? is close to a failure, then ? is also close to ? b) |?| is small.
Attempt 2: High-Degree Hierarchy [DP10] Claim: a) is true if ? and failure are in the same level ? But false in general! a) If ? is close to a failure, then ? is also close to ? b) |?| is small.
Attempt 3: Tree Covers ? = {vertices incident to failures in the original tree cover} {parents of failures in the extended tree cover} LCA Claim: a) is true if level ? level failure ? a) If ? is close to a failure, then ? is also close to ? b) |?| is small.
Wrap Up Now, we can find a set ? that satisfies b) and half of a) We also show: half of a) is enough! See the longer talk a) If ? is close to a failure, then ? is also close to ? b) |?| is small.
