Computing the $2$-blocks of directed graphs

Jaberi, Raed

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

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.

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

S. Alstrup, D. Harel, P.W. Lauridsen and M. Thorup, Dominators in linear time. SIAM J. Comput. 28 (1999) 2117–2132. | DOI | MR | Zbl

R. Balakrishnan and K. Ranganathan, A Textbook of graph theory, 2nd edn. Springer (2012) 66. | MR | Zbl

A.L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R.E. Tarjan and J.R. Westbrook, Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput. 38 (2008) 1533–1573. | DOI | MR | Zbl

J. Carmesin, R. Diestel, M. Hamann and F. Hundertmark, k-Blocks, a connectivity invariant for graphs (2013). Preprint ArXiv:1305.4557. | MR

J. Cheriyan and R. Thurimella, Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30 (2000) 528–560. | DOI | MR | Zbl

Y.M. Erusalimskii and G.G. Svetlov, Bijoin points, bibridges, and biblocks of directed graphs. Cybernet. Systems Anal. 16 (1980) 41–44. | DOI | MR | Zbl

D. Firmani, G.F. Italiano, L. Laura, A. Orlandi and F. Santaroni, Computing strong articulation points and strong bridges in large scale graphs, SEA. Lect. Notes Comput. Sci. 7276 (2012) 195–207. | DOI

S. Fortune, J.E. Hopcroft and J. Wyllie, The Directed Subgraph Homeomorphism Problem. Theoret. Comput. Sci. 10 (1980) 111–121. | DOI | MR | Zbl

G.N. Frederickson, J. Jájá, Approximation Algorithms for Several Graph Augmentation Problems. SIAM J. Comput. 10 (1981) 270–283. | DOI | MR | Zbl

M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco (1979). | MR | Zbl

F. Gavril, Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM J. Comput. 1 (1972) 180–187. | DOI | MR | Zbl

L. Georgiadis, Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, In vol. 6189 of Proc. of 37th ICALP, Part I. Lect. Notes Comput. Sci. (2010) 738–749. | MR | Zbl

L. Georgiadis, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph, In Proc. of 19th European Symposium on Algorithms (2011) 13–24. | MR

L. Georgiadis and R.E. Tarjan, Dominator tree verification and vertex- disjoint paths, In Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (2005) 433–442. | MR | Zbl

L. Georgiadis and R.E. Tarjan, Dominators, Directed Bipolar Orders, and Independent Spanning Trees. ICALP (2012) 375–386. | MR | Zbl

L. Georgiadis, G.F. Italiano, L. Laura and N. Parotsidis, 2-Edge Connectivity in Directed Graphs, CoRR abs/1407.3041 (2014). | MR

L. Georgiadis, G.F. Italiano, L. Laura and N. Parotsidis, 2-Vertex Connectivity in Directed Graphs, CoRR abs/1409.6277 (2014). | MR

L. Georgiadis, G.F. Italiano, L. Laura and N. Parotsidis, 2-Edge Connectivity in Directed Graphs, SODA (2015) 1988–2005. | MR

A.V. Goldberg and R.E. Tarjan, Efficient maximum flow algorithms. Commun. ACM 57 (2014) 82–89. | DOI

G.F. Italiano, L. Laura and F. Santaroni, Finding strong bridges and strong articulation points in linear time. Theoret. Comput. Sci. 447 (2012) 74–84. | DOI | MR | Zbl

R. Jaberi, On Computing the 2-vertex-connected components of directed graphs, CoRR abs/1401.6000 (2014). | MR

S. Khuller, B. Raghavachari and N.E. Young, Approximating the Minimum Equivalent Diagraph. SODA (1994) 177–186. | MR | Zbl

T. Lengauer and R.E. Tarjan, A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1 (1979) 121–141. | DOI | Zbl

Chung-Lun Li, S. Thomas Mccormick and D. Simchi-Levi, The complexity of finding two disjoint paths with min-max objective function. Discrete. Appl. Math. 26 (1990) 105–115. | DOI | MR | Zbl

E.S. Lowry and C.W. Medlock, Object code optimization. Commun. ACM 12 (1969) 13–22. | DOI

J.B. Orlin, Max Flows in O(nm) time, or better. In Proc. of the Annual ACM Symposium on Theory of Computing. ACM Press, New York (2011) 765–774. | MR | Zbl

D.J. Rose and R.E. Tarjan, Algorithmic Aspects of Vertex Elimination. Proc. of 7e Annual ACM Symposium on Theory of Computing. ACM Press, New York (1975) 245–254. | MR | Zbl

R.E. Tarjan, Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972). 146–160 | DOI | MR | Zbl

R.E. Tarjan, Edge-disjoint spanning trees and depth-first search. Acta Inf. 6 (1976) 171–185. | DOI | MR | Zbl

S. Vempala and A. Vetta, Factor 4/3 approximations for minimum 2-connected subgraphs. Proc. of APPROX (2000) 262–273. | MR | Zbl

L. Zhao, H. Nagamochi and T. Ibaraki, A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem. Inf. Process. Lett. 86 (2003) 63–70. | DOI | MR | Zbl