  The first fully dynamic algorithm for maintaining a maximal independent set
(MIS) with update time that is sublinear in the number of edges was presented
recently by the authors of this paper [Assadi et.al. STOC'18]. The algorithm is
deterministic and its update time is $O(m^{3/4})$, where $m$ is the
(dynamically changing) number of edges. Subsequently, Gupta and Khan and
independently Du and Zhang [arXiv, April 2018] presented deterministic
algorithms for dynamic MIS with update times of $O(m^{2/3})$ and $O(m^{2/3}
\sqrt{\log m})$, respectively. Du and Zhang also gave a randomized algorithm
with update time $\widetilde{O}(\sqrt{m})$. Moreover, they provided some
partial (conditional) hardness results hinting that update time of
$m^{1/2-\epsilon}$, and in particular $n^{1-\epsilon}$ for $n$-vertex dense
graphs, is a natural barrier for this problem for any constant $\epsilon >0$,
for both deterministic and randomized algorithms that satisfy a certain natural
property.
  In this paper, we break this natural barrier and present the first fully
dynamic (randomized) algorithm for maintaining an MIS with update time that is
always sublinear in the number of vertices, namely, an
$\widetilde{O}(\sqrt{n})$ expected amortized update time algorithm. We also
show that a simpler variant of our algorithm can already achieve an
$\widetilde{O}(m^{1/3})$ expected amortized update time, which results in an
improved performance over our $\widetilde{O}(\sqrt{n})$ update time algorithm
for sufficiently sparse graphs, and breaks the $m^{1/2}$ barrier of Du and
Zhang for all values of $m$.
