## Computing the 2-blocks of directed graphs

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

raed.jaberi@tu-ilmenau.de

Received: 5 September 2014

Accepted: 19 February 2015

Let *G* be a directed graph. A 2*-directed block *in *G* is a maximal vertex set *C*^{2d} ⊆ *V* with | *C*^{2d} | ≥ 2 such that for each pair of distinct vertices *x*, *y* ∈ *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*(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*), 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.

Mathematics Subject Classification: 05C85 / 05C20 / 68W25

Key words: Directed graphs / strong articulation points / strong bridges / 2-blocks / graph algorithms / approximation algorithms

*© EDP Sciences 2015*