Strong Bridges and Strong Articulation Points of Directed Graphs Giuseppe F. Italiano Univ. of Rome “Tor Vergata” Based on joint work with Donatella Firmani, Luigi Laura, Alessio Orlandi and Federico Santaron i Outline of the Talk 1.  Preliminary Definitions 2.  Algorithms for strong articulation points and strong bridges 3.  Preliminary Experiments on Large Scale Graphs 4.  Conclusions 2-Edge Connectivity Let G = (V,E) be an undirected connected graph, with m edges and n vertices. An edge e∈E is a bridge if its removal disconnects G (i.e., increases the number of connected components of G) Graph G is 2-edge-connected if it has no bridges. The 2-edge-connected components of G are its maximal 2-edge-connected subgraphs 1 2 3 4 5 6 7 2-Edge Connectivity Let G = (V,E) be an undirected connected graph, with m edges and n vertices. An edge e∈E is a bridge if its removal disconnects G (i.e., increases the number of connected components of G) Graph G is 2-edge-connected if it has no bridges. The 2-edge-connected components of G are its maximal 2-edge-connected subgraphs 1 2 3 4 5 6 7 2-Vertex Connectivity Let G = (V,E) be an undirected connected graph, with m edges and n vertices. A vertex v∈V is an articulation point if its removal disconnects G (i.e., increases the number of connected components of G) Graph G is 2-vertex-connected if it has no articulation points. The 2-vertex-connected components of G are its maximal 2- vertex-connected subgraphs 1 2 3 4 5 6 7 2-Vertex Connectivity Let G = (V,E) be an undirected connected graph, with m edges and n vertices. A vertex v∈V is an articulation point if its removal disconnects G (i.e., increases the number of connected components of G) Graph G is 2-vertex-connected if it has no articulation points. The 2-vertex-connected components of G are its maximal 2- vertex-connected subgraphs 1 2 2 3 4 4 5 6 6 7 Bounds for Undirected G Q1: Find whether G is 2-vertex- O(m+n) connected (2-edge-connected). I.e., find one connectivity cut (if any) Q2: Find all connectivity cuts O(m+n) (articulation points, bridges) in G Q3: Find the connectivity (2-vertex-, O(m+n) 2-edge-connected) components of G [Hopcroft & Tarjan 1973], [Tarjan 1974] Directed Graphs Let G = (V,E) be a directed graph, with m edges and n vertices. G is strongly connected if there is a directed path from each vertex to every other vertex in G. The strongly connected components (SCCs) of G are its maximal strongly connected subgraphs. 1 2 3 4 5 6 7 Directed: 2-Vertex Connectivity Let G = (V,E) be a directed strongly connected graph, with m edges and n vertices. A vertex v∈V is a strong articulation point if its removal increases the number of strongly connected components of G Graph G is 2-vertex-connected if it has no strong articulation points. The 2-vertex-connected components of G are its maximal 2-vertex-connected subgraphs Strong Articulation Points 1 2 3 4 5 6 7