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

Abstract

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_sapn} n) time and we show that the 2-edge blocks of G can be computed in O(min { m,t_sbn } 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.