Efficient Contractions of Dynamic Graphs – With Applications

In this paper, we present the first data structure for providing an NMC sparsifier of a fully dynamic graph that supports sublinear worst-case update and query time and works against an adaptive adversary. As a first application, we give an improved fully dynamic algorithm that outputs a cactus representation of all minimum cuts of the current graph upon request. Additionally, we use our data structure to compute the maximal $k$-edge connected subgraphs of an undirected simple graph with an improvement in running time for large values of $k$.

In more detail, we provide a data structure for a fully dynamic graph that can be updated in worst-case time $\widehat{O}(1)$ and that allows (at any point during the sequence of edge updates) to construct an NMC sparsifier in worst-case time $\widehat{O}(n)$. The probabilistic guarantees work against an adaptive adversary. If the update time is relaxed to be amortized or if the adversary is oblivious, the update time can be improved to $\tilde{O}(1)$ and the query time to $\tilde{O}(n)$.

Our basic approach is to maintain suitable data structures in a dynamically changing graph that allow the execution of the static NMC sparsifier algorithm based on random 2-out contractions proposed by Ghaffari, Nowicki, and Thorup [10] in time $\widehat{O}(n)$ instead of $\tilde{O}(m)$. Our main insight is that this speedup can be achieved by maintaining

1. 1.

   a dynamic spanning forest data structure (DSF) of the input graph $G$ and

2. 2.

   a dynamic cut set data structure (DCS), where the user determines which edges belong to a (not necessarily spanning) forest $F$ of $G$, and, given a vertex $v$, the data structure returns an edge that leaves the tree of $F$ that contains $v$ (if it exists).

We show that these two data structures suffice to construct an NMC sparsifier of the current graph in the desired time bound. Put differently, we can avoid processing all edges of $G$ in order to build the NMC sparsifier, and only spend time that is roughly proportional to the size of the sparsifier.

Note that the NMC sparsifier is computed from scratch every time it is requested and no information of a previously computed sparsifier is maintained throughout the dynamic updates of the underlying graph. This ensures the probabilistic guarantees hold against an adaptive adversary if the guarantees of the chosen DSF and DCS data structures do.

Our main result is the following theorem.

Recall that $\tilde{O}$ hides polylogarithmic factors and $\widehat{O}$ hides subpolynomial (i.e., $n^{o(1)}$) factors. The three cases of Theorem 1 result from using different data structures to realize our required DSF and DCS data structures. We show that with minimal overhead both data structures can be reduced to a dynamic minimum spanning forest data structure, for which many constructions have been proposed in the literature. For Case 1, we make use of the fully dynamic minimum spanning forest algorithm of Chuzhoy, Gao, Li, Nanongkai, Peng, and Saranurak [6] – the only spanning forest data structure known so far that can provide worst-case time guarantees against an adaptive adversary. Case 2 is the result of substituting the deterministic data structure of Holm, de Lichtenberg, and Thorup [15] and case 3 results from using the randomized data structure of Kapron, King, and Mountjoy [16] instead.

As a first application we can efficiently provide a cactus representation of the minimum cuts of a simple graph upon request in the fully dynamic setting. The cactus representation of all minimum cuts of a static graph is known to be computable in near linear time $\tilde{O}(m)$ using randomized algorithms [12, 18, 21]. With deterministic algorithms, the best known time bound is $m^{1+o(1)}$ [12]. We are not aware of any previous work on providing the cactus for fully dynamic graphs in sublinear time per query. Specifically, we show the following:

Theorem 2 provides an improvement over one of the main technical components in [11]. Specifically, Goranci et al. [11], provide a method to efficiently maintain an NMC sparsifier of a dynamic simple graph, based on the $2$-out contractions of Ghaffari et al. [10]. However, their main technical result (Theorem 3.7 in [11]) has several drawbacks. First, it needs to know an estimated upper bound $\widehat{\delta }$ on the minimum degree of any graph that occurs during the sequence of updates of $G$. Second, they try to maintain the sparsifier during the updates. This results in an update time $\tilde{O}(\widehat{\delta })$, and forces them to “hide” their sparsifier from an adversary, i.e., they can expose their sparsifier only if they work against an oblivious adversary. Thus, to make their minimum cut algorithm work against an adaptive adversary, they return only the value of the minimum cut. In contrast, our algorithm computes a sparsifier from scratch upon request, and can therefore provide a cactus representation of all minimum cuts, even against an adaptive adversary.

Notice that we provide a different trade-off in reporting the minimum cut: We have an update time of $\widehat{O}(1)$ and a query time of $\widehat{O}(n)$, whereas Theorem 1.1 of Goranci et al. [11] has an update time of $\tilde{O}(n)$ and query time $O(1)$. This trade-off is never worse (modulo the subpolynomial factors) if one caches the result of a query and answers queries from the cache if the graph did not change. Furthermore, upon request, we can provide a minimum cut explicitly, and not just its value.

As a second application of our main result, we improve the time bounds for computing the (vertex sets of the) maximal $k$-edge-connected subgraphs in a simple undirected graph. Specifically, we have the following:

For comparison, Table 1 gives an overview of the best known algorithms for computing the maximal $k$-edge-connected subgraphs in undirected graphs. Thorup [28] does not deal with the computation of the maximal $k$-edge-connected subgraphs, but the result is a consequence of his fully dynamic minimum cut algorithm as observed in [9]. The algorithm in [24] is the only one that holds for weighted graphs (with integer weights), and it has no dependency on $k$ in the time bound. Notice that our algorithm improves over all prior results for $k=\mathrm{\Omega }(n^{1/8})$ and $m=\mathrm{\Omega }(n^{8/7})$.

With a reduction to simple graphs, this implies the following bounds for computing the maximal $k$-edge-connected subgraphs of multigraphs.

Notice that Corollary 4 provides an improvement compared to the other algorithms in Table 1, depending on $k$ and the density of the graph. For example, if $\delta$ and $ϵ$ are two parameters satisfying $1/4\le \delta \le 1$, $16/15\le ϵ\le 2$ and $\delta \le ϵ-6/5$, then we have an improvement in the regime where $m=\mathrm{\Theta }(n^{ϵ})$ and $k=\mathrm{\Theta }(n^{\delta })$ against all previous algorithms in Table 1 that work for multigraphs (i.e., except for Henzinger et al. [13], which works only for simple graphs).

Finally, the method that we use in Theorem 3 for computing the maximal $k$-edge-connected subgraphs in static graphs extends to the case of dynamic graphs.

The results by Aamand et al. [1] and Saranurak and Yuan [25] provide algorithms for maintaining the maximal $k$-edge-connected subgraphs in decremental graphs. Georgiadis et al. [9] provide a fully dynamic algorithm that given two vertices determines whether they belong to the same $k$-edge connected subgraph in time $O(1)$. Their worst-case update time is $\tilde{O}(T(n,k))$, where $T(n,k)$ is the running time of any algorithm for static graphs that is used internally by the algorithm (see values in the time column of Table 1 with the additive term $m$ removed). Thus, as in the case for dynamic minimum cut, our algorithm provides a different trade-off, with fast updates and slower query time. Notice that Theorem 5 provides an improvement over [9] (for any function $T(n,k)$ corresponding to an algorithm from Table 1) when $k$ is sufficiently large (i.e., when $k=\mathrm{\Omega }(n^{1/8})$).

Due to the space constraints, more details on related work, all omitted proofs, and some further details can be found in the full version of this paper.

As our fully dynamic graph $G$ changes, we rely on efficient data structures for the following two problems, which we call the “dynamic spanning forest“ problem (DSF) and the “dynamic cutset” problem (DCS). In DSF, the goal is to maintain a spanning forest $F$ of a dynamic graph $G$. Specifically, the DSF data structure supports the following operations.

• $\mathrm{■}$

  $\mathrm{𝚒𝚗𝚜𝚎𝚛𝚝}(e)$. Inserts a new edge $e$ to $G$. If $e$ has endpoints in different trees of $F$, then it is automatically included in $F$, and this event is reported to the user.

• $\mathrm{■}$

  $\mathrm{𝚍𝚎𝚕𝚎𝚝𝚎}(e)$. Deletes the edge $e$ from $G$. If $e$ was a tree edge in $F$, then it is also removed from $F$, and a new replacement edge is selected among the remaining edges of $G$ in order to reconnect the trees of $F$ that got disconnected. If a replacement edge is found, it automatically becomes a tree edge in $F$, and it is output to the user.

The DCS problem is a more demanding variant of DSF. Here the goal is to maintain a (not necessarily spanning) forest $F$ of the graph, but we must also be able to provide an edge that connects two different trees if needed. Specifically, the DCS data structure supports the following operations.

• $\mathrm{■}$

  ${\mathrm{𝚒𝚗𝚜𝚎𝚛𝚝}}_G(e)$. Inserts a new edge $e$ to $G$.

• $\mathrm{■}$

  ${\mathrm{𝚒𝚗𝚜𝚎𝚛𝚝}}_F(e)$. Inserts an edge $e$ to $F$, if $e$ is an edge of $G$ that has endpoints in different trees of $F$. Otherwise, $F$ stays the same.

• $\mathrm{■}$

  ${\mathrm{𝚍𝚎𝚕𝚎𝚝𝚎}}_G(e)$. Deletes the edge $e$ from $G$. If $e$ is a tree edge in $F$, it is also deleted from $F$.

• $\mathrm{■}$

  ${\mathrm{𝚍𝚎𝚕𝚎𝚝𝚎}}_F(e)$. Deletes the edge $e$ from $F$ (or reports that $e$ is not an edge of $F$).

• $\mathrm{■}$

  $\mathrm{𝚏𝚒𝚗𝚍}\mathrm{\_}\mathrm{𝚌𝚞𝚝𝚎𝚍𝚐𝚎}(v)$. Returns an edge of $G$ (if it exists) that has one endpoint in the tree of $F$ that contains $v$, and the other endpoint outside of that tree.

The main difference between DSF and DCS is that in DCS the user has absolute control over the edges of the forest $F$. In both problems, the most challenging part is finding an edge that connects two distinct trees of $F$. In DCS this becomes more difficult because the data structure must work with the forest that the user has created, whereas in DSF the spanning forest is managed internally by the data structure. Both of these problems can be solved by reducing them to the dynamic minimum spanning forest (MSF) problem, as shown in the following Lemma 7.

To realize these two data structures deterministically with worst-case time guarantees, the only available solution at the moment is to make use of the reduction to the dynamic MSF problem given in Lemma 7 and then employ the dynamic MSF data structure of Chuzhoy et. al. [6], which supports every update operation in worst-case $\widehat{O}(1)$ time. Alternatively, one can solve both DSF and DCS deterministically with amortized time guarantees using the data structures of Holm et. al. [15]. In that case, every update for DSF can be performed in amortized $O({\log }^{2}n)$ time, and every operation for DCS can be performed in amortized $O({\log }^{4}n)$ time, by reduction to dynamic MSF. If one is willing to allow randomness, one can solve both DSF and DCS in worst-case polylogarithmic time per operation, under the assumption of an oblivious adversary with the data structure by Kapron et al. [16].

These different choices for realizing the dynamic MSF data structure give the following lemma.

To handle the updates on $G$, any insertion or deletion of an edge is also applied in both the DSF and the DCS data structure. In particular, for DCS we only use the ${\mathrm{𝚒𝚗𝚜𝚎𝚛𝚝}}_G$ and ${\mathrm{𝚍𝚎𝚕𝚎𝚝𝚎}}_G$ operations and keep its forest empty. At query time, we will build the DCS forest from scratch and then fully delete it again. In order for this to be efficient, DCS needs to have already processed all edges of $G$.

The NMC sparsifier that we output for each query is a random 2-out contraction of the graph at the current time. For this construction, we use our maintained forest data structures and build upon the algorithm of Ghaffari et al. [10], who prove the following.

Note that in particular, the contracted graph $\widehat{G}$ created by the above theorem is an NMC sparsifier, as desired. We first sketch the algorithm that yields Theorem 9 as described by Ghaffari et al. [10]. Then we outline how we can adapt and improve this construction for dynamic graphs, making use of the DSF and DCS data structures. Specifically, to answer a query we show that we can build $\widehat{G}$ in time proportional to the size of $\widehat{G}$, which may be much lower than $O(m\log n)$. The details and a formal analysis can be found in Section 4.

Given a set of edges to contract, the following proposition shows how to compute a $k$ forest decomposition of the induced contracted graph. Crucially, the contracted graph $H$ does not have to be given explicitly, but it is sufficient to know only a set of edges whose contraction yields $H$. Thus, the running time of the construction is independent of the number of edges of $H$. The whole procedure is shown in Algorithm 2.

Note that the number of DCS operations depends only on (1) the number $n$ of vertices of $G$, (2) the number $n_H$ of vertices of $H$, and (3) the number $k$ of forests that we want to build.

A contracted graph can naturally be computed from its defining set of contraction edges $E_{\text{con}}$ in time proportional to the size of this set $|E_{\text{con}}|$. Recall that in our case $E_{\text{con}}$ is the result of the “voting” procedure across all generated $\delta$-forest decompositions (cf. Section 3.2), which is rather expensive to compute. We hence use a different construction that does not need to know $E_{\text{con}}$ explicitly. Instead, it relies on an efficient oracle to certify that a given edge is not contained in $E_{\text{con}}$.

Note that the number of DSF operations is proportional to the number of edges in $E_{\text{check}}$ (the set $E_{\text{con}}$ is not required as input to the algorithm). Thus, this algorithm becomes more efficient if only few edges are contained in $E(G)\setminus E_{\text{con}}$ (since $E_{\text{check}}\subseteq E(G)\setminus E_{\text{con}}$). In our application, we will have $\mu =O(\log n)$.

We can now state our result for computing an NMC sparsifier of a simple graph using Propositions 10 and 11. Compare this to Theorem 9 and note how Theorem 12 requires initialized DSF and DCS data structures but has a running time that is independent of the number of edges in $G$. An outline of this procedure is given in Section 3.2.

The result of Theorem 12 can easily be extended to fully dynamic simple graphs by maintaining the DSF and DCS data structures throughout the updates of the graph. These forest data structures can be realized in different ways, as described in Section 3.1. Depending on this choice we get a different result, and this is how we derive Theorem 1.

If $G$ is disconnected, all minimum cuts have value $0$ and an NMC sparsifier $H$ is by definition only required to have no edges between different connected components of $G$. Crucially, this implies that there is no guarantee that any information of the minimum cuts within each connected component of $G$ is preserved in $H$. In this case, however, we can easily strengthen the result by applying Theorem 12 to each connected component of $G$ individually.

It is well-known that a graph with $n$ vertices has $O(n^2)$ minimum cuts, all of which can be represented compactly with a data structure of $O(n)$ size that has the form of a cactus graph (for more details, see [23]). As a first immediate application of our main Theorem 1, we show how the NMC sparsifier $\widehat{G}$ of any fully dynamic simple graph $G$ can be used to quickly compute this cactus representation. This result is summarized in Theorem 2; see the full version of this paper for a detailed construction.

To obtain just a single minimum cut of $G$, one can apply the deterministic minimum cut algorithms of [14, 19] on $\widehat{G}$, which yields a minimum cut $C$ of $\widehat{G}$ in time $\tilde{O}(|\widehat{G}|)=\tilde{O}(n)$. To transform $C$ into a minimum cut of $G$, we compare its size with the minimum degree $\delta$ of any node in $G$: If $|C|\le \delta$, then we get a minimum cut of $G$ by simply mapping the edges from $C$ back to the corresponding edges of $G$. Otherwise, a minimum cut of $G$ is given by any vertex of $G$ that has degree $\delta$ (which is easy to maintain throughout the updates).

The data structure of Theorem 1 can also be used to improve the time bounds for computing the maximal $k$-edge-connected subgraphs of a simple graph, in for cases where $k$ is a sufficiently large polynomial of $n$. Specifically, we get an improvement for $k=\mathrm{\Omega }(n^{1/8})$, c.f. Section 1.

A general strategy for computing these subgraphs is the following. Let $G$ be a simple graph with $n$ vertices and $m$ edges, and let $k$ be a positive integer. The basic idea is to repeatedly find and remove cuts with value less than $k$ from $G$. First, as long as there are vertices with degree less than $k$, we repeatedly remove them from the graph. Now we are left with a (possibly disconnected) graph where every non-trivial connected component has minimum degree at least $k$. If we perform a minimum cut computation on a non-trivial connected component $S$ of $G$, there are two possibilities: either the minimum cut is at least $k$, or we will have a minimum cut $C$ with value less than $k$. In the first case, $S$ is confirmed to be a maximal $k$-edge-connected subgraph of $G$. In the second case, we remove $C$ from $S$, and thereby split it into two connected components $S_1$ and $S_2$. Then we recurse on both $S_1$ and $S_2$. Since the graph is simple and $S$ has minimum degree at least $k$, it is a crucial observation that both $S_1$ and $S_2$ contain at least $k$ vertices (see e.g. [19]). Therefore the number of nodes decreases by at least $k$ with every iteration and hence the total recursion depth is $O(n/k)$.

The minimum cut computation takes time $T_{\text{mc}}=\tilde{O}(m)$ [17], hence the worst-case running time of this approach is $\mathrm{\Theta }(n/k\cdot T_{\text{mc}})=\tilde{O}(mn/k)$. We can use Theorem 1 to bring the time down to $\tilde{O}(m+n^2/k)$ w.h.p.

Through a reduction to simple graphs, Theorem 3 implies Corollary 4, which is a similar result with slightly worse time bounds for undirected multigraphs. Finally, the method that establishes Theorem 3 naturally extends to the case of fully dynamic simple graphs, which yields Theorem 5.