Faster Dynamic $2$-Edge Connectivity in Directed Graphs

A flow graph is a directed graph with a distinguished start vertex $s$ such that every vertex is reachable from $s$. Let $G=(V,E)$ be a strongly connected graph. Since $G$ is strongly connected, all vertices are reachable from $s$ and reach $s$, so we can view both $G$ and $G^R$ as flow graphs with start vertex $s$. To avoid ambiguities, throughout the paper, we will denote those flow graphs respectively by $G_s$ and $G_s^R$. Let $G_s$ be a flow graph with start vertex $s$. An edge $(u,v)$ is a bridge of $G_s$ if all paths from $s$ to $v$ include $(u,v)$.¹¹1Throughout the paper, to avoid confusion, we use consistently the term bridge to refer to a bridge of a flow graph and the term strong bridge to refer to a strong bridge in the original graph. A vertex $u$ is a dominator of a vertex $v$ ($u$ dominates $v$) if every path from $s$ to $v$ in $G_s$ contains $u$. The dominator relation is reflexive and transitive. Its transitive reduction is a rooted tree, the dominator tree $D$: $u$ dominates $v$ if and only if $u$ is an ancestor of $v$ in $D$. The dominator tree and the bridges of a flow graph can be computed in linear time [2, 5].

A cut is a partition of the vertices of a graph into two disjoint subsets $S,T$. A cut determines a cut-set $E(S,T)$, since the removal of these edges makes all vertices in $T$ unreachable from vertices in $S$. We may use the term “cut” interchangeably to denote either the partition $(S,T)$ or the set of edges $E(S,T)$. (The meaning will always be clear from the context.) We say that a cut $(S,T)$ is a $k$-sized cut if $out(S)=in(T)=k$; then we say $S$ is a $k$-out set and $T$ is a $k$-in set. A cut $(S,T)$ is trivial if $|S|=1$ or $|T|=1$. A cut $C$ separates vertex $s$ from vertex $t$ if all paths from $s$ to $t$ contain an edge in $C$. We refer to such a cut $C$ as an $s$-$t$ cut. Any partition of the vertices into two sets $S$ and $T=V\setminus S$, such that $s\in S$ and $t\in T$ naturally defines an $s$-$t$ cut. We also refer to the partition $(S,T)$ as an $s$-$t$ cut of $G$. The size of this cut is equal to $|E(S,T)|$, i.e., the number of edges directed from $S$ to $T$. An $s$-$t$ mincut is a cut $(S,T)$ of minimum size such that $s\in S$ and $t\in T$. Consider a flow graph $G_s$ and a $k$-in set $T$ such that $s\notin T$. We call $T$ a $k$-sized $s$-cut of $G$. Then, all paths from $s$ to $T$ contain an edge in $\rho (T)$. Clearly, any cut of $G$ is an $s$-cut of $G_s$ or an $s$-cut of $G_s^R$, which allows us to focus only on the $s$-cuts of $G$.

Let $T$ be a rooted tree. Throughout, we assume that the edges of $T$ are directed away from the root. For each directed edge $(u,v)$ in $T$, we say that $u$ is a parent of $v$ (and we denote it by $t(v)$) and that $v$ is a child of $u$. Every vertex except the root has a unique parent. If there is a (directed) path from vertex $v$ to vertex $w$ in $T$, we say that $v$ is an ancestor of $w$ and that $w$ is a descendant of $v$, and we denote this path by $T[v,w]$. If $v\ne w$, we say that $v$ is a proper ancestor of $w$ and that $w$ is a proper descendant of $v$, and denote by $T(v,w]$ the path in $T$ to $w$ from the child of $v$ that is an ancestor of $w$.

A spanning tree $T$ of a flow graph $G_s$ with start vertex $s$ is rooted at $s$ and contains a unique path from $s$ to any other vertex. For an edge $e\notin T$, we let $T(e)$ denote the fundamental cycle of $e$ in $T$, i.e., the cycle that is formed in $T$ when we add edge $e$, ignoring edge directions. Let $e=(u,v)\notin T$, and let $z$ be the nearest common ancestor of $u$ and $v$ in $T$. Then $T(e)\setminus e$ consists of two directed paths, one from $z$ to $u$, and another from $z$ to $v$. (One of these paths may consist of a single vertex.) For a set $S\subseteq V(S)$, we let $\mathrm{𝐿𝐶𝐴}(S)$ denote the lowest common ancestor in $T$ of all vertices in $S$.

Let $G_s$ be a flow graph and let $T$ be a spanning tree of $G_s$ rooted at $s$. We let $𝒩$ denote the set of non-tree edges of $G_s$, i.e., $𝒩=E(G_s)\setminus T$. For any vertex $v\in G_s$, we let ${\rho }_{𝒩}(v)$ denote the set of non-tree edges that are incoming to $v$.

Let $G_s$ be a strongly connected digraph with a fixed start vertex $s$. A set of vertices $S$ is called a $1$-in set if $s\notin S$ and $\mathrm{𝑖𝑛}(S)=|E(V\setminus S,S)|=1$. For every vertex $v\ne s$ that is contained in a $1$-in set, we let $M(v)$ denote the (inclusion-wise) minimum $1$-in set that contains $v$. We call this the $M$-set of $v$. Note that $M(v)$ is well-defined due to the submodularity of cuts. Specifically, we have the following.

Gabow [8] defines a labeling graph $\mathrm{𝐿𝐺}$ with the property that the strongly connected components of $\mathrm{𝐿𝐺}$ correspond to the edges of $G_s$ that have the same $M$-set. For any vertex $v\ne s$, there is at most one incoming edge to $v$ that can be the incoming edge to $M(v)$, and the rest have the property that both of their endpoints also belong to $M(v)$. Thus, the idea is to assign a label to every edge $e$, which is essentially a set of pointers to edges that participate in the same $M$-set as $e$. Thus, the $M$-sets are given as the reachability sets of various edges with respect to this labeling. However, we cannot afford to explicitly compute the $M$-sets of all vertices, as their total size can be quadratic to $|V(G_s)|$.

In [8], the vertex set $V(\mathrm{𝐿𝐺})$ of $\mathrm{𝐿𝐺}$ consists of the edges of $G$, and the edges $(f,g)\in E(\mathrm{𝐿𝐺})$ are defined by a labeling function ${ℒ}_c:E\mapsto 2^E$. In our case, this labeling function becomes

This function implies a labeling graph $\mathrm{𝐿𝐺}$ that has vertex set $E$ (i.e., one vertex for each edge of $G$), and edges $(e,f)$ where $e\in E$ and $f\in L(e)$. For $e,f\in E$, we say that $f$ is a successor of $e$ if there is a path from $e$ to $f$ in $\mathrm{𝐿𝐺}$. The important property of the labeling graph $\mathrm{𝐿𝐺}$ is that the minimum set $M(e)$ of each edge $e$ is equal to the set of all successors of $e$ in $\mathrm{𝐿𝐺}$ [8]. This implies the following key proposition. (See Figure 2.)

By Proposition 6, we have that any two vertices $v$ and $w$ are $2$-edge-connected if and only if $(v,v^{\prime })$ and $(w,w^{\prime })$ are strongly connected both in the labeling graph ${\mathrm{𝐿𝐺}}^{+}$ of $G_s^{+}$ and in the labeling graph ${\mathrm{𝐿𝐺}}_R^{+}$ of ${(G_s^{+})}^R$.

Note that each tree edge $e=(v,w)$ has out-degree equal to $|{\rho }_{𝒩}(v)|+|{\rho }_{𝒩}(w)|$ in $\mathrm{𝐿𝐺}$, while each non-tree edge $f$ has out-degree equal to the number of tree edges in $T(f)$. Hence, $\mathrm{𝐿𝐺}$ has $m$ vertices and $O(mn)$ edges. Nevertheless, Gabow [8] showed that the nodes $[e]$ of the corresponding poset $(\{[e]\},\succ )$, which form a compact representation of these $M$-sets sufficient for our purposes, can be computed in $O(m)$ time by a clever implementation of an algorithm for computing the SCCs [7] of $\mathrm{𝐿𝐺}$. (We remark that the node-finding algorithm of [8] does not compute the complete poset, which has $O(n)$ vertices and $O(n^2)$ edges.) The key idea is to use appropriate data structures, based on set merging [9], to avoid generating all edges of $\mathrm{𝐿𝐺}$. This algorithm critically depends on a specific ordering of operations within the SCC algorithm, which makes it unsuitable for use in incremental or decremental settings.

The modified labeling graph $\widehat{\mathrm{𝐿𝐺}}$ is defined as follows. The vertex set of $\widehat{\mathrm{𝐿𝐺}}$  consists of the tree edges of $T$ and the vertices of $G$, i.e., $V(\widehat{\mathrm{𝐿𝐺}})=T\cup V(G)$. The edge set is defined by the following modified labeling function ${\widehat{ℒ}}_c:T\cup V(G)\mapsto 2^{T\cup V(G)}$:

Hence, $(x,y)\in E(\widehat{\mathrm{𝐿𝐺}})$ if and only if $y\in {\widehat{ℒ}}_c(x)$. Note that both $\mathrm{𝐿𝐺}$ and $\widehat{\mathrm{𝐿𝐺}}$ are bipartite graphs, since any edge connects a tree edge $e\in T$ with a non-tree edge $f\in 𝒩$ in the former, and a tree edge $e\in T$ with a vertex $v\in V(G)$ in the latter. While $\mathrm{𝐿𝐺}$ has $m$ vertices and $O(mn)$ edges, $\widehat{\mathrm{𝐿𝐺}}$ has $2n-1$ vertices and $O(n^2)$ edges.

Here we describe how to construct $\widehat{\mathrm{𝐿𝐺}}$ incrementally as edges are added to a strongly connected graph $G$ with a designated start vertex $s$. The labeling graph is defined with respect to a fixed spanning tree $T$ of the flow graph $G_s$, rooted at $s$. (Similarly, we have a fixed spanning tree $T_R$ of $G_s^R$, rooted at $s$, that defines the labeling graph of $G_s^R$.)

We initialize $\widehat{\mathrm{𝐿𝐺}}$ by inserting a vertex for each $v\in V(G)$ and for each tree edge $e\in T$. Also, for each tree edge $e=(u,v)$, we add to $\widehat{\mathrm{𝐿𝐺}}$ the edges $(e,u)$ and $(e,v)$.

Let $v$ be a vertex of $G$, and let $e$ be a tree edge of $T$. We say that $e$ is covered by $v$ if there is an edge $f\in {\rho }_{𝒩}(v)$ such that $e\in T(f)$, i.e., if $e\in {\widehat{ℒ}}_c(v)$. For each vertex $v\in V(G)$, we maintain the set of tree edges that are covered by $v$, using the following simple fact.

Let $G$ be a strongly connected graph that undergoes edge insertions. We chose an arbitrary start vertex $s$, and compute a spanning trees $T$ of $G$ and a spanning $T_R$ of $G^R$, rooted at $s$. We maintain two instances of the modified labeling graph of Section 4.1, $\widehat{\mathrm{𝐿𝐺}}$ that represents the minimum $1$-in sets of $G$, and ${\widehat{\mathrm{𝐿𝐺}}}_R$ that represents the minimum $1$-in sets of $G^R$, using the two fixed spanning trees $T$ and $T_R$. When an edge $(u,v)$ is inserted into $G$, we execute the update operation of Section 4.2 for $\widehat{\mathrm{𝐿𝐺}}$ and for ${\widehat{\mathrm{𝐿𝐺}}}_R$. Note that for ${\widehat{\mathrm{𝐿𝐺}}}_R$, we search for tree edges of $T_R$ that are covered by $u$.

We maintain the SCCs of $\widehat{\mathrm{𝐿𝐺}}$ and ${\widehat{\mathrm{𝐿𝐺}}}_R$ incrementally, by running on each labeling graph the incremental SCCs algorithm of Bender et al. [3] for dense graphs. For a digraph with $n$ vertices, the algorithm of [3] runs in $O(n^2\log n)$ total time. The modified labeling graphs $\widehat{\mathrm{𝐿𝐺}}$ and ${\widehat{\mathrm{𝐿𝐺}}}_R$ have $O(n)$ vertices and $O(n^2)$ edges, since during their construction we never add duplicate edges. By Lemma 12, we can construct them incrementally in $O(n^2)$ time, and the total time for maintaining their SCCs is also $O(n^2\log n)$.

We turn now to the query operations $\mathrm{𝑞𝑢𝑒𝑟𝑦}(v,w)$ and $\mathrm{𝑟𝑒𝑝𝑜𝑟𝑡}()$. Each SCC of $\widehat{\mathrm{𝐿𝐺}}$ (and similarly of ${\widehat{\mathrm{𝐿𝐺}}}_R$) is represented by a canonical vertex, and the partition of the vertices into SCCs is maintained through a disjoint set union data (DSU) structure [36, 35]. The DSU data structure supports the operation $\mathrm{𝑢𝑛𝑖𝑡𝑒}(p,q)$, which, given canonical vertices $p$ and $q$, merges the SCCs containing $p$ and $q$ into one new SCC and makes $p$ the canonical vertex of the new SCC. It also supports the query $\mathrm{𝑓𝑖𝑛𝑑}(v)$, which returns the canonical vertex of the SCC containing $v$. Since we aim at constant time queries, we use such a data structure that can support each $\mathrm{𝑓𝑖𝑛𝑑}$ operation in worst-case $O(1)$ time and any sequence of $\mathrm{𝑢𝑛𝑖𝑡𝑒}$ operations in total time $O(n\log n)$ [36]. This way, we can identify the canonical vertex of the auxiliary component containing a query vertex in constant time. Hence, by Corollary 10, we can answer $\mathrm{𝑞𝑢𝑒𝑟𝑦}(v,w)$ in $G$ also in constant time, by testing if $u$ and $v$ are strongly connected in both $\widehat{\mathrm{𝐿𝐺}}$ and ${\widehat{\mathrm{𝐿𝐺}}}_R$.

To answer a $\mathrm{𝑟𝑒𝑝𝑜𝑟𝑡}()$ query, we create, for each vertex $v\in V(G)$, a label $\mathrm{𝑙𝑎𝑏𝑒𝑙}(v)=⟨c_v,c_v^R,v⟩$, where $c_v$ and $c_v^R$ are the canonical vertices in the SCCs of $\widehat{\mathrm{𝐿𝐺}}$ and ${\widehat{\mathrm{𝐿𝐺}}}_R$, respectively, that contain $v$. As above, each of these canonical vertices is available in $O(1)$ time. We form a list $L$ consisting of $\mathrm{𝑙𝑎𝑏𝑒𝑙}(v)$ for all $v\in V(G)$, and sort them lexicographically in $O(n)$ time using bucket sorting. Then, in the sorted list $L$, the vertices of the same $2$-edge-connected component appear consecutively, since they have the same canonical vertices in their labels. Therefore, we can report the $2$-edge-connected components of $G$ in $O(n)$ time.

Now we extend our incremental algorithm to general (not strongly connected) digraphs. We note that Proposition 6 requires us to use labeling graphs that correspond to strongly connected flow graphs. To that end, we construct a two-level data structure, that uses various instances of the incremental SCCs algorithm of Bender et al. [3], as mentioned in Section 4.3.

Let $G$ be the input digraph subject to edge insertions. The top level of our data structure, that we refer to as $\mathrm{ISC}(G)$, maintains the strongly connected components of $G$ with the use of the incremental SCCs algorithm of [3]. More precisely, $\mathrm{ISC}(G)$ maintains the SCCs of $G$, represented with a DSU data structure, and the condensation of $G$, denoted by $\overline{G}$, which is the directed acyclic graph that results from $G$ after we contract each SCC into its canonical vertex. We note that [3] also maintains a topological ordering of $\overline{G}$, and when a new SCC is formed, it removes loops and duplicate edges. The bottom level of our data structure maintains the information about the $1$-in sets and $1$-out sets within each SCC $C$ of $G$, in a structure $\mathrm{I2EC}(C)$. Specifically, for each strongly connected component $C$ of $G$, with a designated start vertex $s$, we store a spanning tree $T$ of $G[C]$ and a spanning tree $T_R$ of $G^R[C]$, rooted at $s$. Also, we maintain the data structures of Sections 4.2 and 4.3.

Now we describe how to handle an edge insertion. Suppose a new edge $(x,y)$ is inserted into $G$. If $x$ and $y$ are located the same SCC $C$ of $G$, then we execute the insertion procedure for $\mathrm{I2EC}(C)$, described in Sections 4.2 and 4.3. Otherwise, we execute the insertion in the $\mathrm{ISC}(G)$ data structure. Note that this operation inserts the edge $(\mathrm{𝑓𝑖𝑛𝑑}(x),\mathrm{𝑓𝑖𝑛𝑑}(y))$ into the condensation $\overline{G}$ of $G$. If this insertion does not create a cycle in $\overline{G}$ then we are done. Otherwise, $\mathrm{ISC}(G)$ finds a new SCC of $\overline{G}$, corresponding to a new SCC of $G$, that is contracted into some canonical vertex. As a result, we need to update the bottom-level structure for the involved components of $G$.

Let $C$ be the new SCC of $G$. The data structure $\mathrm{ISC}(G)$ identifies all components $C_1,C_2,\mathrm{\dots },C_k$ of $G$ that are merged into $C$ after the insertion of $(x,y)$, along with the edges $E(C_i,C_j)$ that connect distinct components. (Each such edge $(u,v)$ satisfies $u\in C_i$, $v\in C_j$, where $C_i$ precedes $C_j$ in a topological ordering of the components.) Without loss of generality, assume that $C_1$ is the largest of these components. We choose the canonical (start) vertex $s$ of $C$ to be the start vertex of $C_1$. We refer to this component $C_1$ as the principal component of $C$. Also, we refer to the vertices of $C_1$ as the principal vertices of $C$. The remaining vertices in $C_2,\mathrm{\dots },C_k$ are the secondary vertices of $C$.

Now we describe how to construct the data structure $\mathrm{I2EC}(C)$ for the new component $C$. We describe only the construction of the structures for $G[C]$. The structures for the reverse graph $G^R[C]$ are updated similarly. First, we extend the spanning tree $T_1$ of $G[C_1]$, which is rooted at $s$, to a spanning tree $T$ of $G[C]$ rooted at $s$, so that $T_1\subseteq T$. To achieve this, it suffices to traverse the edges $E(C_i,C_j)$ and the edges of the two spanning trees that we maintain for each component $C_2,\mathrm{\dots },C_k$. This is enough to construct $T$, since the two spanning trees of each $C_i$ form a sparse strongly connected subgraph of $G[C_i]$. (Note that we cannot afford to traverse all edges of $G[C_i]$.) Once $T$ is constructed, we traverse it to recompute $\mathrm{𝑝𝑟𝑒}(v)$ and $\mathrm{𝑠𝑖𝑧𝑒}(v)$ for all $v\in T$. This enables testing the ancestor-descendant relation in $T$ in $O(1)$ time.

Next, we need to update the structures that keep track of the covered edges of $T$ for each vertex $v\in C$. To initialize these structures for the new component $C$, we maintain the structures $b_v$ and ${\mathrm{𝑟𝑜𝑜𝑡}}_v$, for all principal vertices $v$ as they are. Then, we insert the nontree edges $e=(u,v)$ such that $u$ is a secondary vertex in $C$. For each secondary vertex $u$, we compute $b_u$ and ${\mathrm{𝑟𝑜𝑜𝑡}}_u$ from scratch. Hence, in effect we construct $\mathrm{I2EC}(C)$ by inserting the secondary vertices and their adjacent edges in the data structure $\mathrm{I2EC}(C_1)$ of the principal component.