Computing the $2$-blocks of directed graphs

Abstract

Let $G$ be a directed graph. A \textit{$2$-directed block} in $G$ is a maximal vertex set $C^{2d}\subseteq V$ with $|C^{2d}|\ge 2$ such that for each pair of distinct vertices $x,y\in C^{2d}$, there exist two vertex-disjoint paths from $x$ to $y$ and two vertex-disjoint paths from $y$ to $x$ in $G$. In contrast to the $2$-vertex-connected components of $G$, the subgraphs induced by the $2$-directed blocks may consist of few or no edges. In this paper we present two algorithms for computing the $2$-directed blocks of $G$ in $O(\min \{m,(t_{sap}+t_{sb})n\}n)$ time, where $t_{sap}$ is the number of the strong articulation points of $G$ and $t_{sb}$ is the number of the strong bridges of $G$. Furthermore, we study two related concepts: the $2$-strong blocks and the $2$-edge blocks of $G$. We give two algorithms for computing the $2$-strong blocks of $G$ in $O(\min \{m,t_{sap}n\}n)$ time and we show that the $2$-edge blocks of $G$ can be computed in $O(\min \{m,t_{sb}n\}n)$ time. In this paper we also study some optimization problems related to the strong articulation points and the $2$-blocks of a directed graph. Given a strongly connected graph $G=(V,E)$, find a minimum cardinality set $E^{\ast }\subseteq E$ such that $G^{\ast }=(V,E^{\ast })$ is strongly connected and the strong articulation points of $G$ coincide with the strong articulation points of $G^{\ast }$. This problem is called minimum strongly connected spanning subgraph with the same strong articulation points. We show that there is a linear time $17/3$ approximation algorithm for this NP-hard problem. We also consider the problem of finding a minimum strongly connected spanning subgraph with the same $2$-blocks in a strongly connected graph $G$. We present approximation algorithms for three versions of this problem, depending on the type of $2$-blocks.