Connectivity in directed graphs: static and dynamic

Some of the most basic connectivity concepts in directed graphs are reachability and strong connectivity. The concept of strong connectivity naturally extends to the 2-connectivity in directed graphs. There exist two main concepts in 2-connectivity in directed graphs, namely the maximal 2-connected subgraphs, and the 2-connected components. A maximal 2-edge-connected subgraph is a maximal subgraph that remains strongly connected after the removal of any of its edge. The pairwise version of 2-connectivity is defined as follows. We say that two vertices are 2-edge-connected if the removal of any edge leaves them in the same strongly connected component. A 2-edge-connected component of a directed graph is a maximal set of vertices such that all pairs of vertices are 2-edge-connected. Similar definitions can be given for 2-vertex-connectivity. In this thesis we presented algorithms for basic connectivity concepts in directed graphs. In particular, we presented algorithms for reachability, strong connectivity, and 2-connectivity in different settings. We begin by presenting new algorithms for computing the maximal 2-edge- and 2-vertex-connected subgraphs in directed graphs in O(m3/2 ) time, where m and n are respectively the number of edges and vertices of the graph. That improves the previously best-known O(n 2 ) bound for sparse graphs. We presented an optimal data structure that can answer strong connectivity queries under edge or vertex failures. More specifically, after O(m + n) time preprocessing, we build a O(n)-size data structure such that, given a failing edge e, it can answer various strong connectivity queries in G \ e, such as reporting the strongly connected components, or their number, or the size of largest strongly connected component, and more. All of the queries are answered in asymptotically optimal time. The same bounds apply with respect to vertex failures. We further study connectivity problems in the dynamic setting, where the goal is to maintain a solution to the problems at hand while the graph undergoes edges updates. First, we presented an algorithm that can maintain the strongly connected components and single-source reachability information under any sequence of edge deletions in a total of O(m √ n log n) time. Our algorithm achieves a sharp improvement over the previously best known algorithm for both of these problems that runs in a total of O(mn0.9+o(1)) time. The second problem that we study in the dynamic setting is the maintenance of a dominator tree under any sequence of edge deletions. We presented an algorithm that runs in a total of O(mn log n) time. This is the first dynamic algorithm for these problems that beats the naive algorithms that simply recompute from scratch the solution after each update. Our algorithm also maintains various 2-connectivity notions.We further give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors. Finally, we presented algorithms for maintaining the 2-edge-connected components under any sequence of edge insertions in a total of O(mn) time. Again, this is the first algorithm to beat the trivial algorithm that recomputes from scratch the solution after everyupdate. Also here, we give a conditional lower bound showing that shaving polynomial factors from our bound has interesting consequences.