Advanced Techniques for Handling Network Failures in Graphs
Explore the challenges of dealing with failures in network graphs, with a focus on approximate distance oracles subject to multiple vertex failures. Learn about the complexity of the problem, existing literature, and novel solutions presented in this research.
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
?-Failure Model Failures are unavoidable in networks! Problem: given a graph, deal with failures. Example: Query ?,?,? = shortest path from ? to ? that avoids ? source vertex target vertex failed vertex optimal path
How Hard Is the Problem? Easiest case: 1 failure Query ?,?,? = shortest path from ? to ? that avoids ? ? is either a failed edge or a failed vertex A lot of literature [DTCR 08] [BK 08] [BK 09] [WY 10] [GW 12] [DZ 17] [CC 20] [R 20] Highly nontrivial solutions with ? 1 (optimal) query time
How Hard Is the Problem? 2 failures: considerably more complicated [DP 09] Query time: ? log?
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 ?
Oracles for ? Edge Failures Query ?,?,? , ? is a set of ? failed edges Partition the shortest path into ? ? 1segments Consider a segment ? with failures If optimal path avoids ?, (somehow) deal with it. If optimal path goes through ? ?? Pretend it also goes through ?! Query ?,?,? Query ?,?,? + Query ?,?,? , with error 2|?| ? ? ? ?
Oracles for ? Edge Failures Procedure Query(?,?,?): Select a segment ? that contains a failure Consider shortest paths that avoids ? Consider shortest paths that go through ? For every ?, ??? min ???,Query ?,?,? + Query ?,?,? Query time: poly in the number of ? poly ? Additive error: sum of 2 ? over recursion 1 + ? -approx ? is incident to some failed edge. Number of possible ? is 2? ? = ? ? Dist ?,?,? ? ? ? ?
The Art of Finding ? Our goal is to find a set of vertices ? to guard the failures 1. If ? is close to a failure, then ? is also close to ?* 2. |?| is small. Controls additive error. Query time = poly ? For edge failures, ? = {? incident to a failure} is good! ? *in the graph with failures removed
What about Vertex Failures? Natural attempt: ? is the set of vertices adjacent to failures ? is proportional to the degree of failed vertex. Query time is poly ? , could be poly ? . In general, low-degree failures are fine. The problem is high-degree failures! 1. If ? is close to a failure, then ? is also close to ? |?| is small. 2.
Spanners A log?-spanner of a graph ? is a sparse subgraph ? that preserves pairwise distances. For every ?,?, ?????,? ???? ?,? log? ?????,? Thm: We can construct a log?-spanner with ? ? edges Side note: we want 1 + ? - approximation, but we only need log?-spanners!
Attempt 2: High-Degree Hierarchy Used in [DP 10] for connectivity under vertex failures! In this hierarchy: There are only ? log? levels Every failure has small degree, w.r.t. the spanner inside each level
Attempt 2: Inside Each Spanner? in the spanner! ? is the set of vertices adjacent to a failure in the same level. ? How to keep track of inter-level paths? But false in general True if ? and the failure are in the same level! 1. If ? is close to a failure, then ? is also close to ? |?| is small. 2.
Tree Covers Another powerful tool for preserving distances! More powerful than spanners! 1. For every two vertices, exists a tree that covers them ??? ?,? ????????,? log? ??? ?,? 2. Every vertex is in ? log2? trees tree cover spanner
Attempt 2: Inside Each Tree Cover? Attempt 3: Grow Down the Trees! in the tree cover! ? is the set of vertices adjacent to a failure in the same level. It turns out that there is a natural way to grow the trees into lower levels! 1. If ? is close to a failure, then ? is also close to ? |?| is small. 2.
Attempt 3: Grow Down the Trees! In this hierarchy: There are only ? log? levels Every failure has small degree, w.r.t. the tree cover inside each level, before we grow the trees ? = {vertices incident to failures in the original tree cover} {parents of failures in the extended tree cover} ? += ? ?
If ? Is Close to a Failure, Then ? We want: if ? is close to a failure, then ? is also close to ? Assume ? is higher than the failure * Key Lemma. The green vertex is the parent of the failure. (So it is in ?.) ? Extended tree cover *also assume there is no other failure in the path from ? to the failure in the tree cover; the actual argument is a bit harder. ??? ?,? ????????,? log? ??? ?,?
Oracles for ? Vertex Failures Query ?,?,? , ? is a set of ? failed vertices Consider a segment ? that contains some failure ? largest level of any failure in ? If optimal path avoids ? Level ?, (somehow) deal with it. If optimal path goes through ? ? Level ?? level ? ? level failure , can find a guard ?! Query ?,?,? Query ?,?,? + Query ?,?,? , with error 2 ? log? ? max of their level The path may intersect ?, but if intersection point has level < ?, it is fine. ? ? ? ?
Oracles for ? Vertex Failures Query time: poly in the number of ? poly ?,log? Additive error: sum of 2 ? log? over recursion 1 + ? -approx Main Theorem Given an undirected graph, we can maintain ? + ? -approx. distance under ? vertex failures in ???? ?,???? query time. Our space complexity is ?2.01? 1log?? ?, nearly matching the 1 + ? - approximate edge-failure oracle [CCFK 17].
