Strong connectivity in directed graphs under failures, with applications

DOI10.1137/1.9781611974782.123zbMATH Open1410.68296arXiv1511.02913OpenAlexW4234397737MaRDI QIDQ4575869FDOQ4575869

Authors: Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis 

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: In this paper, we investigate some basic connectivity problems in directed graphs (digraphs). Let $G$ be a digraph with $m$ edges and $n$ vertices, and let $Gsetminuse$ be the digraph obtained after deleting edge $e$ from $G$. As a first result, we show how to compute in $O(m+n)$ worst-case time: $(i)$ The total number of strongly connected components in $Gsetminuse$, for all edges $e$ in $G$. $(ii)$ The size of the largest and of the smallest strongly connected components in $Gsetminuse$, for all edges $e$ in $G$. Let $G$ be strongly connected. We say that edge $e$ separates two vertices $x$ and $y$, if $x$ and $y$ are no longer strongly connected in $Gsetminuse$. As a second set of results, we show how to build in $O(m+n)$ time $O(n)$-space data structures that can answer in optimal time the following basic connectivity queries on digraphs: $(i)$ Report in $O(n)$ worst-case time all the strongly connected components of $Gsetminuse$, for a query edge $e$. $(ii)$ Test whether an edge separates two query vertices in $O(1)$ worst-case time. $(iii)$ Report all edges that separate two query vertices in optimal worst-case time, i.e., in time $O(k)$, where $k$ is the number of separating edges. (For $k=0$, the time is $O(1)$). All of the above results extend to vertex failures. All our bounds are tight and are obtained with a common algorithmic framework, based on a novel compact representation of the decompositions induced by the $1$-connectivity (i.e., $1$-edge and $1$-vertex) cuts in digraphs, which might be of independent interest. With the help of our data structures we can design efficient algorithms for several other connectivity problems on digraphs and we can also obtain in linear time a strongly connected spanning subgraph of $G$ with $O(n)$ edges that maintains the $1$-connectivity cuts of $G$ and the decompositions induced by those cuts.

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

Recommendations

• Strong connectivity in directed graphs under failures, with applications
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Incremental strong connectivity and 2-connectivity in directed graphs
• 2-Connectivity in Directed Graphs (Invited Talk)
• Decremental data structures for connectivity and dominators in directed graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cited In (12)

• Strong articulation points and strong bridges in large scale graphs
• Connectivity oracles for graphs subject to vertex failures
• An efficient strongly connected components algorithm in the fault tolerant model
• Decremental data structures for connectivity and dominators in directed graphs
• Fault-tolerant subgraph for single-source reachability: general and optimal
• Sparse certificates for 2-connectivity in directed graphs
• Strong connectivity in directed graphs under failures, with applications
• Incremental strong connectivity and 2-connectivity in directed graphs
• Computing Critical Nodes in Directed Graphs
• An efficient strongly connected components algorithm in the fault tolerant model
• 2-fault-tolerant strong connectivity oracles
• Title not available (Why is that?)

This page was built for publication: Strong connectivity in directed graphs under failures, with applications

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