Connectivity oracles for graphs subject to vertex failures

DOI10.1137/1.9781611974782.31zbMATH Open1410.68096arXiv1607.06865OpenAlexW2484480607MaRDI QIDQ4575768FDOQ4575768

Authors: Ran Duan, Seth Pettie 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of $dleq{d}_{star}$ failed vertices in $ildeO(d^3)$ time and thereafter answers connectivity queries in $O(d)$ time. It occupies space $O(d_{star}mlogn)$. We develop a randomized Monte Carlo version of our data structure with update time $ildeO(d^2)$, query time $O(d)$, and space $ildeO(m)$ for any failure bound $dlen$. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carlo edge-failure connectivity oracle. Using space $O(nlo{g}^{2}n)$, $d$ edge failures are processed in $O(dlogdloglogn)$ time and thereafter, connectivity queries are answered in $O(loglogn)$ time, which are correct w.h.p. Our data structures are based on a new decomposition theorem for an undirected graph $G=(V,E)$, which is of independent interest. It states that for any terminal set $UsubseteqV$ we can remove a set $B$ of $|U|/(s-2)$ vertices such that the remaining graph contains a Steiner forest for $U-B$ with maximum degree $s$.

Full work available at URL: https://arxiv.org/abs/1607.06865

Recommendations

• Connectivity oracles for graphs subject to vertex failures
• Connectivity oracles for failure prone graphs
• Strong connectivity in directed graphs under failures, with applications
• Fully dynamic connectivity oracles under general vertex updates
• Connectivity Oracles for Planar Graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Connectivity (05C40)

Cited In (12)

• A nearly optimal oracle for avoiding failed vertices and edges
• Connectivity Oracles for Planar Graphs
• Near-optimal distributed computation of small vertex cuts
• Network failure detection and graph connectivity
• Connectivity oracles for failure prone graphs
• Fully dynamic connectivity oracles under general vertex updates
• Mincut sensitivity data structures for the insertion of an edge
• Conditional hardness for sensitivity problems
• Network Failure Detection and Graph Connectivity
• An efficient strongly connected components algorithm in the fault tolerant model
• Connectivity oracles for graphs subject to vertex failures
• 2-fault-tolerant strong connectivity oracles

This page was built for publication: Connectivity oracles for graphs subject to vertex failures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575768)