Dynamic MIS Revisited:
Incremental, Fault Tolerant and Fully Dynamic

Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a set $ℳ\subseteq V$ forms an independent set if no two vertices in $ℳ$ share an edge, i.e., $\forall x,y\in ℳ,(x,y)\notin E$. A maximal independent set is one that cannot be extended by including any other vertex while preserving independence. Although computing a maximum cardinality independent set is NP-hard [8], a simple greedy algorithm computes a maximal independent set (MIS) in $O(m)$ time.

A graph is incremental if it gains edges over time, decremental if it loses edges, and fully dynamic if both insertions and deletions occur. In dynamic settings, one can trivially maintain a maximal independent set (MIS) in $O(m)$ update time by recomputing it from scratch after each update. Recent work has focused on improving this update time. Censor-Hillel et al. [5] presented the first non-trivial algorithm requiring $O(\mathrm{\Delta })=O(n)$ amortized update time, where $\mathrm{\Delta }$ is the maximum degree of a vertex in the graph. Assadi, Onak, Schieber, and Solomon [1] improved it to an $O(m^{3/4})$ time algorithm to maintain an MIS. Du and Zhang [7] improved this update time to $\tilde{O}(m^{2/3})$²²2$\tilde{O}$ hides polylogarithmic factors in $n$ amortized, and independently Gupta and Khan [10] acheived $O(m^{2/3})$, all using deterministic algorithms. Du and Zhang [7] also proposed a randomized algorithm with $\tilde{O}(\sqrt{m})$ update time, which was later improved to $\tilde{O}(\sqrt{n})$ and $\tilde{O}(m^{1/3})$ by Assadi et al. [2]. Finally, Chechik and Zhang [6] and Behnezhad et al. [3] independently achieved an $\tilde{O}(1)$ update time using randomized methods. All known algorithms with $o(m^c)$ update time are randomized assuming an oblivious adversary. Recently, Bernstein et al. [4] showed that even for randomized algorithms with an adaptive adversary, assuming the combinatorial BMM conjecture, there exists a lower bound of $O(n^{1-o(1)})$ amortized update time for incremental MIS, which naturally extend to deterministic and fully dynamic variants.

In this paper, we focus on deterministic algorithms for dynamically maintaining MIS. Despite not improving the state-of-the-art fully dynamic algorithm, our aim is to present further insights into the problem by using an alternate approach, potentially paving a way for improving the theoretical bounds in the future. Our results are as follows:

As a first step, we present a deterministic algorithm for maintaining an MIS in an incremental graph, where only edge insertions occur. Our algorithm achieves an amortized $O(\sqrt{m})$ update time, improving over the current state-of-the-art [10].

Next, we design a fault-tolerant algorithm for maintaining an MIS. In this setting, the graph $G(V,E)$ remains static, and we preprocess it to construct a data structure that can efficiently answer the following query:

FaultTolerant($F$): Compute an MIS of $G(V,E\setminus F)$, where $F$ is a set of edge failures.

We present a deterministic fault-tolerant algorithm with the following guarantee:

Finally, we combine the incremental and fault-tolerant algorithms to get the following:

Although our algorithm does not improve the state-of-the-art theoretical bound, the new approach may present new insights to potentially improve the state-of-the-art in the future.

Given a graph $G(V,E)$ having $n$ vertices and $m$ edges, which is connected $(m\ge n-1)$. We represent the graph $G$ formed by deleting a set of edges $F\subseteq E$ from $G$ as $G(V,E\setminus F)$. Also, we represent a subgraph of $G$ induced by the vertices in $V^{\prime }$ as $G(V^{\prime })$ which refers to $G(V^{\prime },E^{\prime })$ where $E^{\prime }=E\cap \{V^{\prime }\times V^{\prime }\}$. We represent the degree of a vertex $v$ by $deg(v)$, i.e., the number of neighbours of a vertex $v$ in $G$. We also represent the maximum degree of a vertex in $G$ as $\mathrm{\Delta }$. A set $M\subseteq V$ is independent if no two vertices in $M$ share an edge, i.e., $\forall x,y\in M,(x,y)\notin E$. A maximal independent $ℳ$ set is an independent set that cannot be extended by including any other vertex while preserving independence.

We now consider the problem of maintaining an MIS in an incremental graph. We refer to a vertex $v$ as light if $deg(v)\le {\mathrm{\Delta }}_l$ and heavy otherwise, where ${\mathrm{\Delta }}_l$ shall be computed later. Since the graph is incremental, all vertices start as light, and once a vertex becomes heavy, it remains heavy. Note that this distinction is required only for the analysis and not the algorithm. Similar to the $O(\mathrm{\Delta })$ algorithm, each vertex $v$ maintains the count of its neighbours in the $ℳ$ as $count[v]$.

Now, our algorithm matches the insert procedure Insert$\mathrm{\Delta }$ exactly except for one crucial modification (see Algorithm 2). On insertion of an edge $(u,v)$, if both the vertices are in $ℳ$, instead of arbitrarily removing a vertex $u$ from $ℳ$, we perform a degree biased removal, i.e., we remove the vertex $u$ having lower degree $deg(u)$. Since the remaining procedure exactly matches Insert$\mathrm{\Delta }$, it correctness also follows from the correctness of $O(\mathrm{\Delta })$ algorithm.

We now analyze the running time of our algorithm. Lemma 6 shows that the amortized update time of an update is $O(deg(u))$ if a vertex $u$ leaves $ℳ$. Moreover, in each update, at most one vertex can leave $ℳ$. Let the $i^{th}$ edge update inserts the edge $(u_i,v_i)$, such that $u_i$ leave $ℳ$ (if any). We analyze the total time taken by a vertex over two phases: when it is light ($deg(u_i)\le {\mathrm{\Delta }}_l$) and when it becomes heavy ($deg(u_i)>{\mathrm{\Delta }}_l$). If $u_i$ is light, then we remove it from $ℳ$ in $O({\mathrm{\Delta }}_l)$ amortized time, since $deg(u_i)\le {\mathrm{\Delta }}_l$. If $u_i$ is heavy, then $v_i$ must also be heavy since $u_i$ was removed from $ℳ$ only because $deg(v_i)\ge deg(u_i)\ge {\mathrm{\Delta }}_l$. Let the number of times a heavy vertex leaves $ℳ$ be $n_h$. Since a heavy $u_i$ can leave $ℳ$ only when $v_i$ is heavy, $n_h\le O(\frac{m}{{\mathrm{\Delta }}_l})$ as there are $O(\frac{m}{{\mathrm{\Delta }}_l})$ heavy vertices in the final graph. Therefore, $u_i$ can be removed from $ℳ$ at most $O(n_h)=O(\frac{m}{{\mathrm{\Delta }}_l})$ times due to its heavy neighbors.

Combining both phases, we now compute the total amortized update time for $m$ insertions.

Hence, the total amortized update time of our incremental algorithm is $O(m({\mathrm{\Delta }}_l+n_h))$, giving amortized $O({\mathrm{\Delta }}_l+n_h)$ update time, resulting in the following lemma:

Since $n_h=O(\frac{m}{{\mathrm{\Delta }}_l})$, substituting ${\mathrm{\Delta }}_l=\sqrt{m}$ gives us the following result.

We now describe our fault tolerant algorithm. It follows from the simple delete procedure Delete$\mathrm{\Delta }$ of the $O(\mathrm{\Delta })$ algorithm with a careful analysis. Given that static graph $G(V,E)$, we preprocess it to build a data structure to answer the following query.

FaultTolerant($F$): Compute an MIS of $G(V,E\setminus F)$, where $F$ is a set of edge failures.

Our fault tolerant algorithm preprocesses the graph to compute the maximal independent set $ℳ$ of $G$ and $count[v]$ for every $v\in V$. These can be computed in $O(m)$ time using the static algorithm. The pseudocode for the query algorithm is shown in Algorithm 3.

Let the end vertices of the edges in $F$ be $V_F$. The deletion of edges in $F$ can potentially reduce the $count[v]$ for a vertex $v\in V_F$ if the other end vertex is in $ℳ$. In case this count becomes zero, the vertex may be potentially added to $ℳ$. Let the set of such vertices be $V_d$. Since the vertices in $V_d$ may not be independent, we cannot simply add all the vertices in $V_d$ to $ℳ$. Instead, we add the MIS $ℳ$’ of the subgraph $G(V_d)$ to $ℳ$. However, since we are dealing with the fault tolerant model, we do not modify the $count[\cdot ]$ and $ℳ$ directly. We instead make a copy $c[v]$ of $count[v]$, which is modified, so that the changes need not be reversed after the query. Thus, our data structure can be directly used for the next query $F^{\prime }$.

Let $\overline{n}$ be the number of vertices on which the edges in $F$ are incident, hence $|V_F|=\overline{n}$. Now, $V_F$ can be computed in $O(k)$ time, $c[v]$ can be initialized in $O(\overline{n})$ time and updated in $O(k)$ time while processing each edge in $F$. Thereafter, $V_d$ can be computed in $O(\overline{n})$ time where $V_d\subseteq V_F$ hence $|V_d|=O(\overline{n})$. The MIS on $G(V_d)$ can computed in $O({|V_d|}^2)=O({\overline{n}}^2)$ time. We thus get the following result for fault tolerant MIS.

We now describe our fully dynamic algorithm for MIS requiring $O(\min \{\mathrm{\Delta },m^{2/3}\})$ time which matches the state-of-the-art algorithm [10]. While the previous algorithm was based on $O(\mathrm{\Delta })$ algorithm [1] and the static algorithm, our algorithm is based on the incremental and fault tolerant algorithms described earlier.

At its core, our algorithm classifies a vertex $v$ as light if $deg(v)\le m^{2/3}$, and heavy otherwise (similar to [10]). All insertions are performed using the incremental algorithm, while the deletions are performed based on the incident vertices. In case at least one of the incident vertices is light, we use the delete procedure Delete$\mathrm{\Delta }$ from the basic $O(\mathrm{\Delta })$ algorithm. However, if both incident vertices are heavy, we collect the deleted edges in $F$ and use our fault tolerant algorithm to report the solution after every update. This essentially handles the harder case of edge insertion between two heavy vertices, as handling their deletion limits such insertions similar to the incremental algorithm. If such an edge (deleted and stored in $F$) is inserted back into the graph, it is simply removed from $F$, and the fault tolerant algorithm updates $ℳ$ accordingly (see pseudocode in Algorithm 4).

The main intuition behind the time complexity is to limit the number of times a heavy vertex $v$ leaves the MIS in the incremental algorithm. This is bounded by the number of edges inserted between $v$ and a heavy vertex. In the fully dynamic setting, we avoid repeated insertions of such edges using the fault tolerant algorithm to process their deletions temporarily without affecting the main algorithm. Thus, given ${\mathrm{\Delta }}_l=m^{2/3}$ and $n_h=m^{1/3}$ (as an edge to each of $m^{1/3}$ heavy vertex can be inserted exactly once), the edge insertions can be processed in amortized $O(m^{2/3})$ time (Lemma 7). Now, the edges collected in $F$ are incident on both heavy vertices, resulting in $k=m^{2/3}$ and $\overline{n}=m^{1/3}$, allowing the fault tolerant algorithm to be processed in $O(m^{2/3})$ time (Theorem 3). Thus, the edge deletions can be processed in $O(m^{2/3})$ amortized time requiring $O(1)$ amortized if at least one incident vertex is light (Lemma 6, as no vertex leaves $ℳ$) and $O(m^{2/3})$ for the fault tolerant algorithm. This results in the following fully dynamic algorithm.

The dynamic MIS problem is one of the unique problems in which handling edge insertions is apparently harder than edge deletions. For most classical graph problems, such as connectivity, reachability, shortest paths, etc., handling edge deletions is harder than edge insertions. Hence, given a faster algorithm for incremental MIS requiring $O(\sqrt{m})$ amortized update time, we are hopeful to achieve the same bound for the fully dynamic case. Further, given the lower bound of $O(n^{1-o(1)})$ for incremental MIS, a polynomial improvement is not possible even for a randomized algorithm with an adaptive adversary.

In this paper, we highlighted an alternate way to handle insertions faster. We also presented a fully dynamic algorithm utilizing insights from the incremental and fault tolerant algorithm, although without improving the state-of-the-art. We believe that new insights may be drawn from our work, potentially resulting in a faster fully dynamic algorithm.