Faster algorithms for maximal 2-connected subgraphs in directed graphs

24/11/2016 - 12:00

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsettled, especially for directed graphs. A strongly connected directed graph is 2-edge-connected (resp.,2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this talk we present improved algorithms for computing the maximal 2-edge- and 2-vertex-connected induced subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with O(mn) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. For the directed case, we showed 1) O(n^2) time algorithms in joint work with Monika Henzinger and Sebastian Krinninger (ICALP'15) and 2) O(m^1.5) time algorithms in joint work with Shiri Chechik, Thomas D. Hansen, Giuseppe F. Italiano, and Nikos Parotsidis (SODA'17).