I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and gives us a $k$-smoothed lower bound of $\Omega(n^{5/2}/\sqrt{k}\log{n})$; a significantly weaker lower bound.

In [3] they give a $k$-smoothed lower bound for flooding of $\Omega(n^{2/3}/k^{1/3})$, where the non-smoothed lower bound is $\Omega(n)$. They also state

There are many additional interesting dynamic network bounds that could be subjected to a smoothed analysis.

In [2] they give a lower bound of $\Omega(nk/\log{n})$ for solving the 𝑘-gossip problem on dynamic graphs. But do not give a smoothed version of it. This could thus be a candidate for smoothing.

I have also heard of the load balancing problem, where each node $v$ is given $w(v)$ tokens, and the goal is to balance the tokens amongst all the nodes so that $\max_{u\in V}|w_u - w_{avg}|$ is minimized. I am not aware of any unsmoothed lower bounds for this problem on dynamic graphs, but this could also be a candidate.

Finally, leader election in dynamic graphs which in each round are always connected could be studied. Although I am not aware of any existing lower bounds.

I want to know which other problems/properties of dynamic graphs, like the maximum hitting time, have strong lower bounds, indicating that a $k$-smoothed lower bound may be much weaker.


A dynamic graph $H$ is a sequence of static graphs $H=(G_1,G_2,...)$ on an unchanging set of vertices $V$. $H$ evolves in rounds, where in round $i$, $H$ takes the structure of $G_i=(V,E_i)$.

The lower bound for the hitting time assumes $H$ is selected from a family of dynamic graphs were each static graph is connected.

$k$-smoothing a dynamic graph $H$ belonging to a family of dynamic graphs $F$, means replacing every $G_i\in H$ with $G_i'\in\text{editdist}(G_i,k)\cap\{G|H\in F \text{ and }G\in H\}$. The set $\text{editdist}(G,k)$ is the set of static graphs which can be reached from $G$ by adding or removing at most $k$ edges.

[1] How to Explore a Fast-Changing World. Chen Avin, Michal Koucký, and Zvi Lotker.

[2] Information Spreading in Dynamic Networks. Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun

[3] Smoothed Analysis of Dynamic Networks. Michael Dinitz, Jeremy T. Fineman



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.