# Problems/properties of dynamic graphs with strong lower bounds

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.

Background:

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