Approximate Distance Oracles for Handling Multiple Vertex Failures in Networks

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: ? + ? -approx! ?? ? vertex failures [DP 10] [DP 17]

Rest of This Talk Review the ?-edge-failure oracle A few attempts on how to handle vertex failures And finally, our solution

Oracles for ? Edge Failures Dist ?,?,? , ? is a set of ? failed edges Partition the shortest path into segments Consider a segment ? with failures If optimal path avoids ?, it s fine. If optimal path goes through ? ?? Pretend it also goes through ?! Dist ?,?,? Dist ?,?,? + Dist ?,?,? , with error 2|?| ? ? ? ?

Oracles for ? Edge Failures Procedure Dist(?,?,?): Select a segment ? that contains a failure Consider ( recursively ) shortest paths that avoids ? Consider shortest paths that go through ? For every ?, ??? min ???,Dist ?,?,? + Dist ?,?,? 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! ?

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 Two caveats: spanners, 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 is 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 THREE caveats: tree covers, 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 ??? ?,? ????????,? log? ??? ?,?

Oracles for ? Vertex Failures Dist ?,?,? , ? is a set of ? failed vertices Consider a segment ? that contains some failure ? largest level of any failure in ? If optimal path avoids ? ????? ?, deal with it recursively. If optimal path goes through ? ? ????? ?? ????? ? ? ????? failure , can find a guard ?! Dist ?,?,? Dist ?,?,? + Dist ?,?,? , 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.

Open Problems Exact distance oracle subject to multiple failures? May consider easiest case here: undirected graph, edge failures Approximate distance oracle for directed graphs? Subject to multiple failures. (Edge and vertex failures are equivalent) [van den Brand & Saranurak 2019]: exact distance, but requires ? query time; reachability in poly ? query time Shave logs?

Thank you!