Fully Dynamic Algorithms for Transitive Reduction

In acyclic graphs, a reduction resembling that of [4] (see Lemma 4.1) carries quite well to the fully dynamic setting. Roughly speaking, one can set up a graph $G^{\prime }$ with two additional copies of every vertex and edge, so that for all $u,v\in V$, paths $u^{\prime \prime }\to v^{\prime \prime }$ between the respective second-copy vertices $u^{\prime \prime },v^{\prime \prime }$ in $G^{\prime }$ correspond precisely to indirect paths $u\to v$ in $G$, i.e., $u\to v$ paths avoiding the edge $uv$. Clearly, an edge $xy$ is redundant if indirect $x\to y$ paths exist. As a result, one can obtain a dynamic transitive reduction data structure by setting up a dynamic transitive closure data structure on $G$ and issuing $m$ reachability queries after each update. The reduction immediately implies an $O(n^2)$ worst-case update bound (Monte Carlo randomized) and $O(n^2)$ amortized update bound (deterministic) for the problem in the acyclic case via [42, 47], even in the case of vertex updates. This is optimal for dense acyclic graphs, at least if one is interested in maintaining the reduction explicitly.⁵⁵5Indeed, consider a graph $G=(V_1\cup V_2\cup \{s,t\},E)$ with $E=(V_1\times V_2)\cup \{vs:v\in V_1\}\cup \{tv:v\in V_2\}$, where $n=|V_1|=|V_2|$. No edges in this acyclic graph are redundant. However, adding the edge $st$ makes all $n^2$ edges $V_1\times V_2$ redundant. Adding and removing $st$ back and forth causes $\mathrm{\Theta }(n^2)$ amortized change in the transitive reduction.

The reduction works best if the transitive closure data structure can maintain some (mostly fixed) $m$ reachability pairs $Y\subseteq V\times V$ of interest more efficiently than via issuing $m$ reachability queries. In our use case, the reachability pairs $Y$ correspond to the edges of the graph, so an update of $G$ can only change $Y$ by one pair in the case of single-edge updates, and by $n$ pairs sharing a single vertex in the case of vertex updates to $G$. Some algebraic dynamic reachability data structures based on dynamic matrix inverse [47, 48] come with such a functionality out of the box. By applying these data structures on top of the reduction, one can obtain an $O(n^{1.528}+m)$ worst-case bound for updating the transitive reduction of an acyclic digraph (see Theorem 6.4 for details). Interestingly, the $n^{1.528}$ term (where the exponent depends on the current matrix multiplication exponent [55] and simplifies to $n^{1.5}$ if $\omega =2$) typically emerges in connection with single-source reachability problems, and $O(n^{1.528})$ is indeed conjectured optimal for fully dynamic single-source reachability [53]. One could say that our algebraic transitive reduction data structure for DAGs meets a fairly natural barrier.

The algebraic reachability data structures provide worst-case guarantees but are more suitable for denser graphs. In particular, they never achieve near-linear in $n$ update bounds, even when applied to sparse graphs. On the other hand, some combinatorial fully dynamic reachability data structures, such as [44], do achieve near-linear in $n$ update bound. However, these update bound guarantees (1) are only amortized, and (2) come with a non-trivial polynomial query procedure that does not inherently support maintaining a set $Y$ of reachability pairs of interest. This is why relying on the reduction (Lemma 4.1) does not immediately improve the update bound for sparse graphs. Instead, we design a data structure tailored specifically to maintain the transitive reduction of a DAG (Theorem 1.1). We later extend it to general graphs, ultimately obtaining Theorem 1.2.

First of all, we prove that given a source vertex $s$ of a DAG $G$, one can efficiently maintain, subject to edge deletions, whether an indirect $s\to t$ path exists in $G$ for every outgoing edge $st\in E$ (Lemma 5.1). This “indirect paths” data structure is based on extending the decremental single-source reachability data structure of [30], which is a classical combinatorial data structure with an optimal $O(m)$ total update time.

Equipped with the above, we apply the strategy used in the reachability data structures of [44, 45]: every time an insertion of edges centered at a vertex $z$ issued, we build a new decremental single-source indirect paths data structure $D_z$ “rooted” at $z$ and initialized with the current snapshot of $G$. Such a data structure will not accept any further insertions, so the future insertions to $G$ are effectively ignored by $D_z$. Intuitively, the responsibility of $D_z$ is to handle (i.e., test the indirectness of) paths in the current graph $G$ whose most recently updated vertex is $z$.⁶⁶6In the transitive closure data structures [44, 45], the concrete goal of an analogous data structure rooted at $z$ is to efficiently query for the existence of a path $x\to y$, where $z$ is the most recent updated vertex along the path. This way, handling each path in $G$ is delegated to precisely one maintained decremental indirect paths data structure rooted at a single vertex.

Compared to the data structures of [44, 45], an additional layer of global bookkeeping is used to aggregate the counts of alternative paths from the individual data structures $D_z$. That is, for an arbitrary $z\in V$, $D_z$ contributes to the counter iff it contains an alternative path. Using this technique, if the count is zero for some edge $uv$, then $uv$ is not redundant. This allows constant-time redundancy queries, or, more generally, explicitly maintaining the set of edges in the transitive reduction.

We prove that all actions we perform can be charged to the $O(m)$ initialization time of the decremental data structures $D_z$. Since, upon each insert update (incident to the same vertex), we (re)initialize only one data structure $D_z$, the amortized update time of the data structure is $O(m)$.

Extending the data structure for DAGs to support SCCs involves addressing some technical challenges. The decremental indirect path data structures need to be generalized to support detecting indirect paths in the condensation. The approach of [30] breaks for general graphs, though. One solution here would be to adapt the near-linear decremental single-source reachability for general graphs [11]. However, that data structure is randomized, slower by a few log factors, and much more complex. Instead, as in [44, 45], we take advantage of the fact that we always maintain $n$ decremental indirect paths data structures on a nested family of snapshots of $G$. This allows us to apply an algorithm from [45] to compute how the SCCs decompose as a result of deleting some edges in all the snapshots at once, in $O(m+n\log n)$ time. Since the SCCs in snapshots decompose due to deletions, the condensations are not completely decremental in the usual sense: some intra-SCC edges may turn into inter-SCC edges and thus are added to the condensation. Similarly, the groups of parallel inter-SCC edges may split, and some edges that have previously been parallel may lose this status. Nevertheless, we show that all these problems can be efficiently addressed within the amortized bound of $O(m+n\log n)$ which matches that of the fully dynamic reachability data structure of [45]. Similarly as in DAGs, one needs to check $O(1)$ counters and flags to test whether some edge of $G$ is redundant or not; this takes $O(1)$ time. The details can be found in the full version of the paper.

As indicated previously, operating on the condensation turns out to be very hard when using the dynamic matrix inverse machinery [53, 47]. Intuitively, this is because these data structures model edge updates as entry changes in the adjacency matrix, and this is all the dynamic matrix inverse can accept. It seems that if we wanted an algebraic data structure to maintain the condensation, we would need to update it explicitly by issuing edge updates. Recall that there could be $\mathrm{\Theta }(n)$ such edge updates to the condensation per single-edge update issued to $G$, even if $G$ is sparse. This is prohibitive, especially since any updates to a dynamic matrix inverse data structure take time superlinear in $n$.

To deal with these problems, we refrain from maintaining the condensation. Instead, we prove an algebraic characterization of the redundancy of a group of parallel inter-SCC edges $F=\{u_1{v}_1,\mathrm{\dots },u_k{v}_k\}$ connecting two distinct SCCs $R,T$ of $G$. Specifically, we prove that if $\tilde{A}(G)$ is the symbolic adjacency matrix [47] (i.e., a variant of the adjacency matrix with each $1$ corresponding to an edge $uv$ is replaced with an independent indeterminate $x_{u,v}$), then in order to test whether $F$ is redundant it is enough to verify a certain polynomial identity (see the full version of the paper) on some $k+1$ elements of the inverse ${(\tilde{A}(G))}^{-1}$ whose elements are degree $\le n$ multivariate polynomials. Consequently, through all groups $F$ of parallel inter-SCC edges in $G$, we obtain that $O(n+m)$ elements of the inverse have to be inspected to deduce which inter-SCC edges are redundant.

By a standard argument involving the Schwartz-Zippel lemma, in the implementation, we do not actually need to operate on polynomials (which may contain an exponential number of terms of degree $\le n$). Instead, for high-probability correctness it is enough to test which of the aforementioned identities hold for some random variable substitution from a sufficiently large prime field $\mathbb{Z}/p\mathbb{Z}$ where $p=\mathrm{\Theta }(\mathrm{poly}\left(n\right))$. Since the inverse of a matrix can be maintained explicitly in $O(n^2)$ worst-case time subject to row or column updates, this yields a transitive reduction data structure with $O(n^2)$ worst-case bound per vertex update (see the full version of the paper).

Obtaining a better worst-case bound for sparser graphs in the single-edge update setting is more challenging. Unfortunately, the elements of the inverse used for testing the redundancy of a group $F$ of parallel intra-SCC edges do not quite correspond to the individual edges of $F$; they also depend, to some extent, on the global structure of $G$. Specifically, the aforementioned identity associated with $F$ involves elements $(r,u_1),\mathrm{\dots },(r,u_k)$, $(v_1,t),\mathrm{\dots },(v_k,t)$, and $(r,t)$ of the inverse, where $r,t$ are arbitrarily chosen roots of the SCCs $R$ and $T$, respectively.

Dynamic inverse data structures with subquadratic update time [53, 47] (handling single-element matrix updates) generally do not allow accessing arbitrary query elements of the maintained inverse in constant time; this costs at least $\mathrm{\Theta }(n^{0.5})$ time. They can, however, provide constant-time access to a specified subset of interest $Y\subseteq V\times V$ of its entries, at the additive cost $O(|Y|)$ in the update bound. Ideally, we would like $Y$ to contain all the $O(m+n)$ elements involved in identities to be checked. However, the mapping of vertices $V$ to the roots of their respective SCCs may quickly become invalid due to adversarial edge updates causing SCC splits and merges. Adding new entries to $Y$ is costly, though: e.g., inserting $n$ new elements takes $\mathrm{\Omega }(n^{1.5})$ time.

We nevertheless deal with the outlined problem by applying the hitting set argument [52] along with a heavy-light SCC distinction. For a parameter $\delta \in (0,1)$, we call an SCC heavy if it has $\mathrm{\Theta }(n^{\delta })$ vertices, and light otherwise. We make sure that at all times our set of interest $Y$ in the dynamic inverse data structure contains

1. 1.

   the edges $E$,

2. 2.

   a sample $(S\times V)\cup (V\times S)$ of rows and columns for a random subset $S$ (sampled once) of size $\mathrm{\Theta }(n^{1-\delta }\log n)$, and

3. 3.

   all $O(n^{1+\delta })$ pairs $(u,v)$ such that $u$ and $v$ are both in the same light SCC.

This guarantees that the set $Y$ allows for testing all the required identities in $O(n+m)$ time, has size $\tilde{O}(n^{1+\delta }+n^{2-\delta }+m)$ and evolves by $O(n^{1+\delta })$ elements per single-edge update, all aligned in $O(n)$ small square submatrices. For an optimized choice of $\delta$, the worst-case update time of the data structure is $O(n^{1.585}+m)$, i.e., slightly worse than we have achieved for DAGs.

It is an interesting problem whether the transitive reduction of a general directed graph can be maintained within the natural $O(n^{1.528}+m)$ worst-case bound per update. The details can be found in the full version of the paper.