Smoothed Analysis of Dynamic Graph Algorithms

We consider fully dynamic graphs with a fixed set of nodes $V=[n]$ and changing edges. The input consists of the edges of an initial graph, followed by a sequence of edges to be flipped. The complexity of a dynamic graph algorithm is measured by the time $t_{\text{pre}}$ it needs for processing the initial graph, the time $t_{\text{u}}$ for processing an edge change, and the time $t_{\text{q}}$ for answering a query.

We next define a $p$-smoothed input, for a parameter $0\le p\le 1$, which we name the oblivious flip adversary model of smoothing. First, the adversary fixes an initial graph and a sequence of edge flips. The initial graph is smoothed as follows: each node pair remains consistent with the adversarial choice with probability $p$, and otherwise re-sampled (uniformly from $\{0,1\}$). Then, each edge flip remains unchanged with probability $p$, and otherwise re-sampled uniformly from $(\genfrac{}{}{0pt}{}{[n]}{2})$. Clearly, when $p=0$ the process coincides with an average-case (uniformly random) input, while for $p=1$ it results in the standard adversarial (worst case) input.

Smoothed analysis was originally introduced for studying the simplex algorithm, where the inputs are continuous and the added noise is Gaussian. The field has greatly evolved since: first, it is now typical to analyze the complexity of a computational problem, rather than that of a specific solution (algorithm), leading to more robust results. Second, the model of random noise was adjusted to discrete inputs, which are common throughout computer science. Lastly, the framework has also been applied to several different computational models, each posing its own unique challenges.

In our case, the inputs are discrete and arrive in an online manner. This gives rise to several natural models of smoothing, differing in the adaptivity of the adversary to the noise and in the way changes are encoded. In the following we present three variants of $p$-smoothed inputs: oblivious flip adversary, oblivious add/remove adversary, and an adaptive adversary. Each model constitutes a different intermediate model between worst-case and average-case, and the relations between them is depicted in Figure 3. In Figure 5 we exemplify how the complexities of concrete problems increase differently as we transition from easier to harder models of input.

Table 4 compares our results to known results in average-case and worst-case models, focusing on update times of algorithms with constant query times. We discuss these results below.

Dynamic graph algorithms constitute a deep and well-studied research topic, as was recently presented in the thorough survey of Hanauer, Henzinger and Schulz [15]. The most recent dynamic algorithm for connectivity is by Huang, Huang, Kopelowitz, Pettie and Thorup [18], and has $t_{\text{u}}=O(\log n{\log }^2\log n)$ amortized update time and $t_{\text{q}}=O(\log n/\log \log \log n)$ time per query. Small subgraph counting was recently studied by Hanauer, Henzinger and Hua [14], who showed, e.g., that counting $s$-$t$ $3$-paths and $s$-triangles (triangles through a given node $s$) can be done with $t_{\text{u}}=O(n)$ and constant query time. Kara, Nikolic, Ngo, Olteanu and Zhang [19] studied databases that support enumeration of triangles in trinary relations, and their work implies triangle counting in dynamic graphs with $t_{\text{pre}}=O(m_0^{3/2}),t_{\text{u}}=O(m^{1/2})$, and $t_{\text{q}}=O(1)$.

Pătraşcu and Demaine [29] proved the first unconditional lower bound for dynamic graph algorithms, focusing on connectivity problems in undirected graphs. One of their results asserts that there is no dynamic algorithm for deciding whether the graph is connected with a constant query time and $t_{\text{u}}=o(\log n)$ amortized time, a result that remains the best known to date. Some follow-up works [31, 4, 24] considered, e.g., the case of parameterized queries (querying whether two given nodes are in the same connected component) and directed graphs.

Following a line of work on conditional lower bounds in dynamic graphs [1, 30, 9, 32, 21], which used several different conjectures, Henzinger, Krinninger, Nanongkai and Saranurak [16] introduced the OMv conjecture as a unified conjecture. They showed, e.g., that $s$-triangle detection, bipartite matchings and bipartite vertex cover cannot be done with polynomial preprocessing time, $t_{\text{u}}=O(n^{1-ϵ})$ and $t_{\text{q}}=O(n^{2-ϵ})$, for any $ϵ>0$ and even amortized and randomized, unless the OMv conjecture is false. The main focus of the works until this point was on worst-case analysis, and average-case analysis was rarely applied, as described next.

The first to study average-case complexity of dynamic graph algorithms were Nikoletseas, Reif, Spirakis and Yung [28]. They consider an initial empty graph, a phase of addition of random edges, and then a phase where random edges are added or remove with equal probabilities. In this setting, they present an algorithm for $(u,v)$-connectivity, i.e., where a query includes a pair $(u,v)$ of nodes and has to determine if they are in the same connected component.

Following this, Alberts and Henzinger [2] defined the “restricted randomness” model. To this end, they note that each change consists of a type (add or remove) and a parameter (which edge to add or to remove). In their model, an adversary chooses a sequence of types (add or remove) for the changes, and then the parameter (edge) of each change is chosen uniformly at random from the relevant set (existing edges for a remove operation, node-pairs without edges for an add operation). They show that several problems have better amortized time complexities in the restricted randomness model compared to the best worst-case bounds known at the time (almost no lower bounds where known at the time). The problems considered include connectivity and its variants (edge and node connectivity), maximum cardinality matching, minimum spanning forest, and bipartiteness.

Indeed, one could see this model as an average-case model, but we prefer to use this term only for uniformly random inputs (as in [28, 17]). It can also be seen as a smoothed analysis model, though without the ability to parameterize the amount of randomness.

As this model consists in an adversary and a random process, it should not come as a surprise that both an oblivious adversary and an adaptive one can be considered in this setting. Here, an adversary that chooses the sequence of types in advance is called an oblivious one, and an adversary that can choose each type according to the outcome of the random process so far is an adaptive one. These variants are not equivalent: for example, an adaptive adversary can make sure that all the $n$-edge graphs in the sequence are connected (by adding an $n$-th edge to an $(n-1)$-edge graph only if it is connected), while with an oblivious adversary every $n$-edge graph has equal probability, and most of them are not connected. The distinction between adversaries is not made in [2], but the proofs use the fact that each graph has equal probability (conditioned on the number of edges), thus the model there is oblivious.

The average-case complexity of dynamic graph algorithms was disregarded for decades, until recently Henzinger, Lincoln and Saha [17] approached it again with new tools. They studied subgraph counting problems, presented some simple algorithms inspired by [2], and focused mainly on proving conditional lower bounds. Their proofs use ideas from fine-grained complexity [16], and specifically lower bounds for average-case complexity in this setting [5, 3]. For some problems, such as counting $s$-$t$ $5$-paths, they show that the average-case complexity cannot be better than the worst-case one (up to an $n^{ϵ}$ factor), while for others, such as $s$-$t$ $3$-paths, they prove a big gap exists. As smoothed analysis lie between the worst case and the average one, we focus the current work only on problems of the last type, where a gap exists. Some of our lower bound proofs use techniques from [17]; for example, while they do not give a lower bound for $s$-$t$ $3$-paths (since it is easy in the average case) we give a lower bound for this problem in the smoothed case by extending the technique they used for proving a lower bound for $s$-$t$ $5$-paths.

Smoothed analysis was introduced by Spielman and Teng [35] in relation to using pivoting rules in the simplex algorithm. Since then, it have received much attention in sequential algorithm design. In particular interest to us are smoothed analysis results for static graphs [23, 10, 22] and dynamic networks [8, 26, 11, 7], which we use as inspiration for our model of noise.

In recent years, smoothed analysis was also applied in settings of a repeated game, where inputs are chosen successively. These include dynamic networks, population protocols [34] and online learning [12, 13]. The effect of the adversary’s adaptivity was first studied with regard to information spreading in dynamic networks [26], which is shown to be polynomially slower when the adversary is adaptive compared to an oblivious adversary. The adaptivity question was also studied in the context of online learning [13], and a handful of problems were shown to have the same smoothed complexity whether the adversary is adaptive or oblivious. From these, the dynamic networks works are the most relevant to ours, as they defined similar smoothing models. Their results, however, focus on round complexity and not computation time, and thus are incomparable with ours.

We extend the definition of a dynamic graph to the case where some updates are chosen at random while others are adversarial. While we explore variants on this model, the basic definition is for the adaptive flip adversary:

We also consider oblivious adversaries, that fix all their choices ahead of time, but then in execution each choice is replaced by a random choice with probability $1-p$. In this model we allow for either a flip adversary or an add/remove adversary:

Note that a graph created by this process can also be thought of as a graph created step by step as in the adaptive adversary case, but by an adversary (flip or add/remove) that does not see any of the random choices in the initial graph and previous steps.

Our proofs use probabilistic tools extensively. For the distance between two distribution $P,Q$ over the same domain we use the well-known statistical distance (sometimes called total-variation distance). We make an extensive use of the Poisson distribution and more importantly the Poissonization technique (see, e.g., [27, Section 8.4]). We use $\mathrm{Pois}(t)$ for the Poisson distribution with parameter $t$ and sometimes for a random variable drawn from this distribution. Some helpful properties of the Poisson distribution are summarized in the following fact.

The first step reduces between online algebraic matrix-vector multiplication problems. It consists of an algebraic reduction that was presented in [16] and is standard by now, and two reductions that were presented in [17].

After a standard reduction from the OMv problem to the OuMv problem, two other reductions are made. The first reduces to OuMv with operations modulo $2$ (that is, over ${𝔽}_2$ instead of $ℝ$), as defined below. The second reduction is a typical worst-case to average-case reduction over ${𝔽}_2$, showing the problem is as hard on random inputs. We define the OuMv problem and state the reduction to conclude this step.

The sequence of reductions concludes in the following lemma.

We next show that average-case parity OuMv can be solved using an algorithm that counts $s$-$t$ $3$-paths in $P_3$-partite $p$-smoothed dynamic graphs with an oblivious flip adversary.

A $P_3$-partite graph is composed of $n^{\prime }=2n+2$ nodes partitioned as $V=\{s\}\bigsqcup A\bigsqcup B\bigsqcup \{t\}$, where $|A|=|B|=n$, and can only have edges of types $sA,AB,Bt$ (that is, $E\subseteq (\{s\}\times A)\cup (A\times B)\cup (B\times \{t\})$). To represent the OuMv problem using this graph, consider $u,v$ and $M$ as the indicators of the $sA,Bt$ and $AB$ edges, respectively (e.g., $(s,A_j)\in E\iff u(j)=1$). It is not hard to see that the product $u^{T}Mv$ is exactly the number of $s$-$t$ $3$-paths.

Assume we have a $P_3$-partite graph that represents $M$ and $(u_{i-1},v_{i-1})$ as above, and we get the next pair $(u_i,v_i)$ and want to update the graph accordingly. In worst-case analysis, such reduction can use adversarial choices: flip the $sA$ and $Bt$ edges to represent $(u_i,v_i)$, leave the $AB$ edges intact, and then query the number of $s$-$t$ $3$-paths to retrieve $u_i^{T}M{v}_i$. When random changes are involved in the process, however, undesired changes to $AB$ edges are bound to occur. Moreover, such changes are more likely than others, as there are $n^2$ potential edges of types $AB$ and only $2n$ potential edges of the other types ($sA$ and $Bt$). Next, we describe how to overcome this challenge.

For the mere problem of having any changes in $AB$ edges, a standard solution used in [17] serves here as well: the reduction creates $3$ copies of the graph, such that whenever a query is made, each has different $AB$ edges but they have exactly the same $sA$ and $Bt$ edges. To be precise, the $AB$ edges in the 3 graphs will represent 3 matrices $M_1,M_2,M_3$ such that $M{\equiv }_{{}_2}{M}_1+M_2+M_3$, while the $sA$ and $Bt$ edges in all the graphs represent $u_i$ and $v_i$. This assures that the sum modulo 2 of the number of $s$-$t$ $3$-paths in the three graphs gives $u_i^{T}M{v}_i$ with the original matrix $M$:

The harder challenge is to synthesize $3$ such correlated change sequences that resemble authentic $p$-smoothed change sequences. To this end, consider an oblivious adversary whose strategy is not deterministic, but instead chooses an $sA$ or $Bt$ edge u.a.r. That is, each change is distributed on the graph edges by

After applying $p$-smoothing, each change has the following distribution over the graph edges

This guarantees the highest chances for a change of type $sA$ and $Bt$ after smoothing, which is crucial for avoiding redundancies in the reduction and obtaining a tight lower bound. Moreover, since all edge changes are drawn from ${𝒟}_{\text{adv}}^p$, we can simulate a sequence by generating a multi-set of edges and later randomize the order in which they are changed. We create a sequence of roughly $t=5n\log (n)/p$ changes using Poissonization. This breaks dependencies and allows us to construct a multi-set of samples by drawing the number of appearances of each edge independently.

Finally, we show how to count $s$-$t$ $3$-paths in the restricted class of $P_3$-partite graphs using an algorithm that counts such paths in general graphs. This reduction uses inclusion-edgeclusion: it takes a $P_3$-partite graph $𝒢$, and constructs $16$ (general) graphs by adding edges that were previously not allowed (exterior edges). The same approach was taken in the average-case analysis, but smoothed inputs require more attention due to the adversarial presence.

To account for the adversarial presence, the transition from a $p$-smoothed $P_3$-partite graph to $p^{\prime }$-smoothed graphs must use $p^{\prime }\le p$ that sufficiently weakens the adversary. Still, this can be done using $p^{\prime }\in [p/2,p]$, which is crucial for a lossless reduction leading to (nearly) tight lower bounds.

The $16$ new dynamic graphs all use the original node set $V=\{s\}\bigsqcup A\bigsqcup B\bigsqcup \{t\}$, and initially all have the same interior edges as the $P_3$-partite graph. Their initial exterior edges are correlated in the following sense: they properly partition the four exterior edge sets $E_{At},E_{AA},E_{BB},E_{sB}$. That is, there exists four partitions, one for each edge set, such that the exterior edges of each of the $16$ initial graphs constitute a unique combination of the parts, one from each edge set.

We next describe how to construct a single change, using a parameter $\alpha (n,p)\approx \frac{1}{2-p}\in [1/2,1]$. We flip a coin $C\sim Bin(\alpha )$; if $C=1$ we make an interior change, the next change in the $p$-smoothed sequence of $𝒢$, while if $C=0$ we change a random exterior edge. Choosing $\alpha$ carefully and $p^{\prime }=\alpha \cdot p$ guarantees that a sequence of such changes is $p^{\prime }$-smoothed on a general graph, for an appropriate adversarial strategy. We apply this sequence of changes to each of the $16$ graphs.

Since the graphs undergo the exact same changes, they properly partition the four exterior edge sets at all times. This invariant ensures that the total number of exterior $s$-$t$ $3$-paths (i.e., not of type $sABt$) in all $16$ graphs is always easy to compute. After querying all graphs for their $s$-$t$ $3$-paths count, we sum the answers, subtract the exterior paths, and divide by $16$. This gives the number of $sABt$ paths in $𝒢$, since each interior path appears in all graph and was counted $16$ times.

To summarize, steps 1-3 dictate a chain of fine-grained reductions as follows. An algorithm for counting $s$-$t$ $3$-paths in general graphs can be used to count them in a $P_3$-partite graph, which in turn can be used to solve the average-case parity OuMv problem. A solution for the average-case parity OuMv problem implies a solution to the OMv problem, contradicting the OMv conjecture.