Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems
Preprint
Abstract
A directed graph $G=(V,E)$ is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph $G$ are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex $v \in V$ is a twinless strong articulation point of $G$ if the deletion of $v$ increases the number of TSCCs of $G$. Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a $2$-vertex-connected (biconnected) undirected graph $H$, find all vertices $v$ that belong to a vertex-edge cut-pair, i.e., for which there exists an edge $e$ such that $H \setminus \{v,e\}$ is not connected. We develop a linear-time algorithm that not only finds all such vertices $v$, but also computes the number of edges $e$ such that $H \setminus \{v,e\}$ is not connected. This also implies that for each twinless strong articulation point $v$ which is not a strong articulation point in a strongly connected digraph $G$, we can compute the number of TSCCs in $G \setminus v$. We note that the problem of computing all vertices that belong to a vertex-edge cut-pair can be solved in linear-time by exploiting the structure of $3$-vertex-connected (triconnected) components of $H$, represented by an SPQR tree of $H$. Our approach, however, is conceptually simple, and thus likely to be more amenable to practical implementations.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- 2-edge-twinless blocksBulletin des Sciences Mathématiques, 2021
- 2-vertex connectivity in directed graphsInformation and Computation, 2018
- Strong Connectivity in Directed Graphs under Failures, with Applications2017
- Finding strong bridges and strong articulation points in linear timeTheoretical Computer Science, 2012
- Yet another optimal algorithm for 3-edge-connectivityJournal of Discrete Algorithms, 2009
- Twinless Strongly Connected Components2006
- Finding Triconnected Components by Local ReplacementSIAM Journal on Computing, 1993
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972