Let @math be a directed graph. A in @math is a maximal vertex set @math with @math such that for each pair of distinct vertices @math , there exist two vertex-disjoint paths from @math to @math and two vertex-disjoint paths from @math to @math in @math . In contrast to the @math -vertex-connected components of @math , the subgraphs induced by the @math -directed blocks may consist of few or no edges. In this paper we present two algorithms for computing the @math -directed blocks of @math in @math time, where @math is the number of the strong articulation points of @math and @math is the number of the strong bridges of @math . Furthermore, we study two related concepts: the @math -strong blocks and the @math -edge blocks of @math . We give two algorithms for computing the @math -strong blocks of @math in @math time and we show that the @math -edge blocks of @math can be computed in @math time. In this paper we also study some optimization problems related to the strong articulation points and the @math -blocks of a directed graph. Given a strongly connected graph @math , find a minimum cardinality set @math such that @math is strongly connected and the strong articulation points of @math coincide with the strong articulation points of @math . This problem is called minimum strongly connected spanning subgraph with the same strong articulation points. We show that there is a linear time @math approximation algorithm for this NP-hard problem. We also consider the problem of finding a minimum strongly connected spanning subgraph with the same @math -blocks in a strongly connected graph @math . We present approximation algorithms for three versions of this problem, depending on the type of @math -blocks.
Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study @math -edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices @math and @math are @math -edge-connected if there are two edge-disjoint paths from @math to @math and two edge-disjoint paths from @math to @math . This relation partitions the vertices into blocks such that all vertices in the same block are @math -edge-connected. Differently from the undirected case, those blocks do not correspond to the @math -edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are @math -edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has @math edges and maintains the same @math -edge-connected blocks as the input graph.