Computing the $2$-blocks of directed graphs

Jaberi, Raed¹

¹ Faculty of Computer Science and Automation, Teschnische Universität Ilmenau, 98693 Ilmenau, Germany

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 2, pp. 93-119

Résumé

Let $G$ be a directed graph. A $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 this paper we present two algorithms for computing the $2$-directed blocks of $G$ in $O\left(min\{m,(t_{sap}+t_{sb})n\}n\right)$ 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\left(min\{m,t_{sap}n\}n\right)$ time and we show that the $2$-edge blocks of $G$ can be computed in $O\left(min\{m,t_{sb}n\}n\right)$ 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)$, we want to find a minimum strongly connected spanning subgraph $G^{*}=(V,E^{*})$ of $G$ such that the strong articulation points of $G$ coincide with the strong articulation points of $G^{*}$. 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.

Détail

Reçu le : 2014-09-05
Accepté le : 2015-02-19
DOI : 10.1051/ita/2015001

Classification : 05C85, 05C20, 68W25
Keywords: Directed graphs, strong articulation points, strong bridges, 2-blocks, graph algorithms, approximation algorithms