Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi Krzysztof Onak Baruch Schieber Shay Solomon



 
 









skins,breakable
enhanced jigsaw


















-@thistlm










theoremTheorem
lemmaLemma[section]
proposition[lemma]Proposition
corollary[theorem]Corollary
claim[lemma]Claim
fact[lemma]Fact
conj[lemma]Conjecture
definitionDefinition
*DefinitionDefinition
problemProblem

remark[lemma]Remark
observation[lemma]Observation

*claim*Claim
*proposition*Proposition
*lemma*Lemma
*problem*Problem

mdresult[theorem]Theorem
Theorem[backgroundcolor=lightgray!40,topline=false,rightline=false,leftline=false,bottomline=false,innertopmargin=2pt]

mdinvariantInvariant
invariant[hidealllines=false,backgroundcolor=gray!10,innertopmargin=0pt]
































cTheorem


cClaim


cDefinition


cProblem


cLemma


cRemark




cEnumerate[1][1.]







cItemize











































































































































































































tbox[
		enlarge top by=5pt,
		enlarge bottom by=5pt,
		 breakable,
		 boxsep=0pt,
                  left=4pt,
                  right=4pt,
                  top=10pt,
                  arc=0pt,
                  boxrule=1pt,toprule=1pt,
                  colback=white
                  ]
	






























































































































































































































Fully Dynamic Maximal Independent Set
 with Sublinear Update Time
    Sepehr Assadisassadi@cis.upenn.com Supported in part by NSF grant CCF-1617851.  
 University of Pennsylvania
Krzysztof Onakkonak@us.ibm.com 
 IBM Research
Baruch Schiebersbar@us.ibm.com 
 IBM Research
Shay Solomonsolo.shay@gmail.com 
 IBM Research

    
============================================================================================================================================================================================================================================================



empty

A maximal independent set (MIS) can be maintained in an evolving m-edge graph
by simply recomputing it from scratch in O(m) time after each update.
But can it be maintained in time sublinear in m in fully dynamic graphs?



We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(min{Δ,m^3/4}), where Δ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges.  



We further present a distributed implementation of our algorithm with O(min{Δ,m^3/4}) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices
that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary. 










§ INTRODUCTION



Dynamic graph algorithms constitute an active area of research in theoretical computer science.

Their objective is to maintain a solution to a combinatorial problem in an input graph—for example, a minimum spanning tree or maximal matching—under insertion and deletion of edges.
The research on dynamic graph algorithms addresses the natural question of whether one essentially needs to recompute the solution from scratch after every update.

This question has been asked over the years for a wide range of problems such as connectivity <cit.>, minimum spanning tree <cit.>,
maximal matching <cit.>, approximate matching and vertex cover <cit.>, shortest
paths <cit.>, and graph coloring <cit.>
(this is by no means a comprehensive summary of previous results).

Surprisingly however, almost no work has been done for the prominent problem of maintaining a maximal independent set (MIS) in dynamic graphs. Indeed, the only
previous result for this problem that we are aware of is due to Censor-Hillel  <cit.>, who developed a randomized algorithm for this problem in distributed dynamic networks and left the sequential case (the main focus of this paper)
as a major open question. We note that implementing their distributed algorithm in the sequential setting requires Ω(Δ)[ It is not clear whether O(Δ) time
is also sufficient for this algorithm or not; see Section 6 of their paper.] update time in expectation, where Δ is a fixed upper bound on the degree of vertices in the graph and
can be as large as Θ(m) in sparse graphs.

The maximal independent set problem is of fundamental importance in graph theory
with natural  connections to a plethora of other basic problems, such as vertex
cover, matching, vertex coloring, and edge coloring (in fact, all these problems
can be solved approximately by finding an MIS, see, e.g., the paper of
Linial <cit.>).  As a result, this problem has been studied extensively
in different settings, in particular in parallel and distributed
algorithms <cit.>.
(We refer the interested reader to the papers of Barenboim
 <cit.> and Ghaffari <cit.> for the story of this
problem in these settings and a comprehensive summary of previous work.)

In this paper, we concentrate on sequential algorithms for maintaining a maximal independent set in a dynamic graph. Our results are also applicable to the dynamic distributed setting
and improve upon the previous work of Censor-Hillel  <cit.>.



 §.§ Problem Statement and Our Results


Recall that a maximal independent set (MIS) of an undirected graph, is a maximal collection of vertices subject to the restriction that no pair of vertices in the collection are adjacent. In the maximal independent set problem,
the goal is to compute an MIS of the input graph.

We study the fully dynamic variant of the maximal independent set problem in which the goal is to maintain an MIS of a dynamic graph G, denoted by := (G), subject to a sequence of edge
insertions and deletions. When an edge change occurs, the goal is to maintain  in time significantly faster than simply recomputing it from scratch. Our main result is the following:



Starting from an empty graph on n fixed vertices, a maximal independent set can be maintained deterministically over any sequence of edge insertions and deletions in O(m^3/4) amortized update time,
where m denotes the dynamic number of edges.






As a warm-up to our main result in Theorem <ref>, we also present an extremely simple deterministic algorithm for maintaining an MIS with O(Δ) amortized update time, where Δ is a fixed
upper bound on the maximum degree of the graph. Our algorithms can be combined together to achieve a deterministic O(minΔ,m^3/4) amortized update time algorithm for maintaining an MIS in dynamic graphs.
This constitutes the first improvement on the update time required for this problem in fully dynamic graphs over the naïve O(m) bound for all possible values of m.  We now elaborate more on the details of our algorithm in Theorem <ref>.









  
Deterministic Algorithm. An important feature of our algorithm in Theorem <ref> is that it is deterministic. The distinction between deterministic and randomized algorithms
is particularly important in the dynamic setting as almost all existing randomized algorithms require the assumption of a non-adaptive oblivious adversary who is not allowed to learn anything about the algorithm's random bits. Alternately, this setting can be
viewed as the requirement that the entire sequence of updates be fixed in advance, in which case the adversary cannot use the solution maintained by the algorithm in order to break its guarantees. While these assumptions can be naturally justified in many
settings, they can render randomized algorithms entirely unusable in certain scenarios (see, e.g., <cit.> for more details).

As a result of this assumption, obtaining a deterministic algorithm for most dynamic problems is considered a distinctively harder task compared to finding a randomized one.
This is evident by the polynomial gap between the update time of best known deterministic algorithms compared to randomized ones for many dynamic problems.
For example, a maximal matching can be maintained in a fully dynamic graph with O(1) update
time via a randomized algorithm <cit.>, assuming a non-adaptive oblivious adversary, while the best known deterministic algorithm for this problem requires Θ(√(m)) update time <cit.> (see <cit.> for a similar
situation for (Δ+1)-coloring of vertices of a graph).



  
O(1)-Amortized Adjustment Complexity. An important performance measure of a dynamic algorithm is its adjustment complexity (sometimes called recourse) that counts the number of vertices (or edges) that
need to be inserted to or deleted from the maintained solution after each update (see, e.g. <cit.>).
For many natural graph problems such as maintaining a maximal matching, constant worst-case adjustment complexity
can be trivially achieved since one edge update cannot ever necessitate more than a constant number of changes in the maintained solution. This is, however, not the case for the MIS problem: by inserting an edge
between two vertices already in , the adversary can force the algorithm to delete at least one end point of this edge from , which in turn forces the algorithm to pick all neighbors of this deleted
vertex to ensure maximality (this phenomena also highlights a major challenge in the treatment of this problem compared to the maximal matching problem which we discuss further below). 

Nevertheless, we prove that the adjustment complexity of our algorithm in Theorem <ref> is O(1) on average which is clearly optimal. Can we further improve
our results to achieve an O(1) worst-case adjustment complexity? We claim that this is indeed not possible by showing that the worst-case adjustment complexity of any algorithm for maintaining an MIS is Ω(n), using
a simple adaption of an example proposed originally by <cit.> for proving a similar result in distributed settings when vertex deletions are also allowed by the adversary (this follows seamlessly from the result in <cit.> and is provided in
Appendix <ref> only for completeness).



  
Distributed Implementation. Finding a maximal independent set is one of the most studied problems in distributed computing. In the distributed computing model, there is a processor on each vertex of the graph.
Computation proceeds in synchronous rounds during which every processor can communicate messages of size O(log n) with its neighbors (this corresponds to the
 model of distributed computation; see Section <ref> for further details). In the dynamic setting, both edges and vertices can be inserted to or deleted from the graph and the goal is
to update the solution in a small number of rounds of communication, with small communication cost and adjustment complexity.

Our results in the sequential setting also imply a deterministic distributed algorithm for maintaining an MIS in a dynamic network
with O(1) amortized round complexity, O(1) amortized adjustment complexity, and O(minΔ,m^3/4) amortized message complexity per each update.
This result achieves an improved message complexity compared to the distributed algorithm of <cit.> with asymptotically the same round and adjustment complexity (albeit in amortized sense as opposed
to in expectation; see Section <ref>).
More importantly, our result is achieved
via a deterministic algorithm and does not require the assumption of a non-adaptive oblivious adversary.
Similar to <cit.>, our algorithm can also be implemented in the asynchronous model, where there is no global synchronization of communication between nodes.
We elaborate more on this result in Section <ref>.




  
Maximal Independent Set vs. Maximal Matching.
We conclude this section by comparing the maximal independent set problem to the closely related problem of maintaining a maximal matching[A maximal matching in a graph G can be obtained by computing an
MIS of the line graph of G.] in dynamic graphs. We discuss additional challenges that one encounters for the maximal independent set problem.

In sharp contrast to the maximal independent set problem, maintaining maximal matchings in dynamic graphs  has been studied extensively, culminating in an O(√(m)) worst-case update time  deterministic algorithms <cit.> and O(1) expected update time randomized algorithm <cit.> (assuming a non-adaptive oblivious adversary).

















Maintaining an MIS in a dynamic graph seems inherently more complicated than maintaining a maximal matching. One simple reason is that as argued before, a single update can only change the status of O(1) edges/vertices in the
maximal matching, while any algorithm can be forced to make Ω(n) changes to the MIS for a single edge update in the worst case. As a result, a maximal matching can be maintained with an O(Δ) worst-case update time
via a straightforward algorithm (see, e.g. <cit.>), while the analogous approach for MIS only results in O(m) update time.

Another, perhaps more fundamental difference between the two problems lies in their different level of “locality.” To adjust a maximal matching after
an update, we only need to consider the neighbors of the recently unmatched vertices (to find another unmatched vertex to match with), while to fix an MIS, we need to consider the two-hop neighborhood of a recently
removed vertex from the MIS (to add to the MIS the neighbors of this vertex which themselves do not have another neighbor in the MIS). We note that this difficulty is similar-in-spirit to the barrier for maintaining
a better than 2 approximate matching via excluding length-3 augmenting paths in dynamic graphs. Currently, the best known algorithm for achieving a better than 2-approximation to matching in dynamic graphs
requires O(m^1/4) update time <cit.>. Achieving sub-polynomial in m update time—even using randomness and assuming a non-adaptive oblivious adversary—remains
a major open problem in this area (we refer the interested reader to <cit.> for more details).

We emphasize that even for the seemingly easier problem of maximal matching, the best upper bound on update time using a deterministic algorithm (the focus of our paper) is only O(√(m)) <cit.>.



 §.§ Overview of Our Techniques




  
O(Δ)-Amortized Update Time. Consider the following simple algorithm for maintaining an MIS  of a dynamic graph: for each vertex, maintain the number of its neighbors in  in a counter, and
for each update in the graph or , spend O(Δ) time to update this counter for the neighbors of the
updated vertex. What is the complexity of this algorithm? Unfortunately, as argued before, an update to the graph may inevitably result in an update of size Ω(n) to . Processing it may take Ω(n ·Δ) time
as we have to update all neighbors of every updated vertex. However, all we need to handle this case is the following basic observation: while a single update can force the algorithm
to insert up to Ω(n) vertices to , it can never force the algorithm to remove more than one vertex from . We therefore charge the O(Δ) time needed to insert
a vertex into  (and there can be many such vertices per one update) to the time spent in a previous update in which the same vertex was (the only one) removed from . This allows us to argue that on average, we
only spend O(Δ) time per update.



  
O(m^3/4)-Amortized Update Time.
Achieving an o(Δ) amortized update time however is distinctly more challenging. On the one hand, we cannot afford to update all neighbors of a vertex after every change in the graph.
On the other hand, we do not have enough time to iterate over all neighbors of an updated vertex to even check whether or not they should be added to  and hence need to
maintain this information, which is a function of vertices in the two-hop neighborhood of a vertex, explicitly for every vertex.

To bypass these challenges, we relax our requirement for
knowing the status of all vertices in the neighborhood of a vertex, and instead maintain the status of some vertices that are in the two-hop neighborhood of a vertex. More concretely,
we allow “high” degree vertices to not update their “low” degree neighbors about their status (as the number of low degree neighbors can be very large), while making every “low” degree vertex update not only all its neighbors but even some of its
neighbor's neighbors, using the extra time available to this vertex (as its degree is small). This approach allows us to maintain
a “noisy” version of the information described above. Note that this information is not completely accurate as the status of some vertices in  would be unknown to their neighbors and their neighbor's neighbors (
in the actual algorithm, we use a more fine-grained partition of vertices based on their degree into more than two classes, not only “high” and “low”).

We now need to address a new challenge introduced by working with this “noisy” information:  we may decide that a vertex is ready to join  based on the information stored in the algorithm and insert this vertex to , only to find out
that there are already some vertices in  adjacent to this vertex. To handle this, we also relax the property of the basic algorithm above that only allowed for deleting one vertex from  per each update.
This allows us to insert multiple vertices to  as long as a large portion (but not all) of their neighbors are known to be not in . Then we go back and delete a small number of “violating” vertices
from  to make sure it is indeed an independent set. Note that deleting those vertices may now require inserting a new set vertices in their neighborhood to  to ensure maximality.

In order to be able to perform all those operations and recursively treat the newly deleted vertices in a timely manner, we maintain the invariant that whenever we need to remove more than one vertex from , the number of inserted vertices
leading to this case is much larger than the number of removed vertices. This allows us to extend the simple charging scheme used in the analysis of the basic algorithm above to this new algorithm and prove our upper bound on the amortized update time
of the algorithm.

We point out that despite the multiple challenges along the way that are described above, our algorithm turned to be quite simple in hindsight. The main delicate matters are in the choice of parameters and in the analysis. This in turn makes the implementation of our results in sequential and distributed settings quite practical.



  
Organization. We introduce our notation and preliminaries in Section <ref>. We then present a simple proof of the O(Δ)-amortized update time algorithm in Section <ref> as a warm-up to
our main result. Section <ref> contains the proof of our main result in Theorem <ref>. The distributed implementation of our result
and a detailed comparison of our results with that of Censor-Hillel  <cit.> appear in Section <ref>.








§ PRELIMINARIES




  
Notation. We denote the static vertex set of the input graph by V. Let = ⟨G_0,G_1,…⟩ be the sequence of graphs that are given to the algorithm: 
initial graph G_0 is empty and each graph G_t is obtained from the previous graph G_t-1 by either inserting or deleting a single edge e_t = (u_t,v_t). We use G_t(V,E_t) to denote
the graph at step t and define m_t := E_t. Finally, throughout the paper,  denotes the maximal independent set maintained by the algorithm at every time step. 





  
Greedy MIS Algorithm. Consider the following algorithm for computing an MIS of a given graph: Fix an arbitrary ordering of the vertices in the graph, add the first vertex to the MIS, remove all its neighbors from the list, and continue. 
This algorithm clearly computes an MIS of the input graph. In the rest of the paper, we refer to this algorithm as the greedy MIS algorithm. 



	For an n-vertex graph G with maximum degree Δ, the greedy MIS algorithm computes an MIS of size at least n/(Δ+1). 








§ WARM-UP: A SIMPLE O(Δ)-UPDATE-TIME DYNAMIC ALGORITHM


As a warm-up to our main result, we describe a straightforward algorithm for maintaining an MIS  in a dynamic graph with
O(Δ) amortized update time, where Δ is a fixed upper bound on the maximum degree in the graph.  For every vertex v in the graph, we simply maintain a counter v, counting number of its neighbors in .
In the following, we consider updating  and this counter after each edge update.

Let e_t=(u_t,v_t) be the updated edge. Suppose first that we delete this edge. In this case, u_t and v_t cannot both be in  by definition of an independent set. Also, if none of them belong to , there is nothing to do.
The interesting case is thus when exactly one of u_t or v_t belongs to ; without loss of generality, we assume this vertex is u_t. We first subtract one from v_t (as it is no longer adjacent to u_t). If v_t > 0 still,
it means that v_t is adjacent to some vertex in  and hence we are done.  Otherwise, we add v_t to  and update the counter of all its neighbors in O(Δ) time.
Clearly, this step takes O(Δ) time in the worst case, after that  is indeed an MIS.

Now suppose e_t was inserted to the graph. The only interesting case here is when both u_t and v_t belong to  (we do not need to do anything in the remaining cases, other than perhaps updating the neighbor list of u_t and v_t in O(1) time).
To ensure that  remains an independent set, we need to remove one of these vertices, say u_t, from . After this, to ensure the maximality, we have to insert to  any
neighbor of u_t that can now join . To do this, we first update the · of all neighbors of u_t in O(Δ) time. Next (using the updated counter), we iterate over all neighbors of u_t and for each one check if they can be inserted to  now or not. 
If so, we add this new vertex to  and inform all its neighbors in O(Δ) time to update their ·.
It is easy to see that in this case, we spend O(k ·Δ) time in the worst case, where k is the number of vertices added to . 

The correctness of this algorithm is straightforward to verify. We now prove that the amortized running time of the algorithm is O(Δ). The crucial observation is that whenever we change , we may increase its size without any restriction,
but we never decrease its size by more than one. We use the following straightforward charging scheme.

Initially, we start with all vertices being in  as the original graph is empty. Whenever we delete one vertex from , we spend O(Δ) time to handle this vertex (including updating its neighbors and checking which ones can
join ), and place O(Δ) “extra budget” on this vertex to be spent later. We use this budget when this vertex is being inserted to  again. Whenever we want to bring this vertex back to , we only need to spend
this extra budget and hence the O(Δ) time spent for inserting this vertex back to  can be charged to the time spent for this vertex when we removed it from .
This implies that the update time is O(Δ) in average. We can therefore conclude the following lemma.


	Starting from an empty graph on n vertices, a maximal independent set can be maintained deterministically over any sequence of K edge insertions and deletions in O(K ·Δ) time
	where Δ is a fixed bound on the maximum degree in the graph.





































§ AN O(M^3/4)-UPDATE-TIME DYNAMIC ALGORITHM


We present our fully dynamic algorithm for maintaining a maximal independent set in this section and prove Theorem <ref>.

The following lemma is a somewhat weaker looking version of Theorem <ref>. However, we prove next that this lemma is all we need to prove Theorem <ref>.



	Starting with any arbitrary graph on n vertices and m edges, a maximal independent set  can be maintained deterministically over any sequence of K = Ω(m) edge insertions and deletions
	in O(K · m^3/4) time, as long as the number of edges
	remains within a factor 2 of m.


We first show that this lemma implies Theorem <ref>.


	For simplicity, we define m=1 in case of empty graphs. We start from the empty graph and run the algorithm in Lemma <ref> until the number of edges m_t in the graph differs from m
	by a factor more than 2. This crucially implies that the total number of updates before terminating the algorithm (the parameter K in Lemma <ref>), is Ω(m). As such, we can invoke
	Lemma <ref> to obtain an upper bound of O(m^3/4) on the amortized update time of the algorithm throughout these updates. We then update m= m_t
	and start running the algorithm in Lemma <ref> on the current graph using the new choice of m. Clearly, this results in an amortized update time of O(m^3/4) where m now denotes the
	number of dynamic edges in the graph. As the algorithm in Lemma <ref> always maintain an MIS of the underlying graph, we obtain the final result.




















The rest of this section is devoted to the proof of Lemma <ref>. In the following, we first describe the data structure maintained in the algorithm for storing the required information and its main properties and then present our update algorithm.








 §.§ The Data Structure







For every vertex v, we maintain the following information:



	
  * v: a list of current neighbors of v in the graph.
	
  * v: an estimate of the degree of v to within a factor of two.
	
  * v: a list containing u for every vertex u in v.
	
  * v: a boolean entry indicating whether or not v belongs to .
	
  * v: a counter denoting the size of a suitable subset of current neighbors of v in . Any vertex counted in v belongs to  but not all neighbors of v in  are (necessarily) counted in v
	(see Invariant <ref> for more detail).
	
  * v: a list, containing for every vertex w in v, a counter that counts the size of a suitable subset of current neighbors of w in .
	Any vertex counted in v[w] is also counted in w but not vice versa
	(see Invariant <ref> below for more detail).



Additionally, we maintain a partition (,,,) of the vertices into four sets based on their current approximate degree, namely, v.
In particular, v belongs to  iff v≥ m^3/4, to  iff m^3/4 > v≥ m^1/2, to  iff m^1/2 > v≥ m^1/4,
and to  iff v < m^1/4. We refer to the vertices of  as the low-degree vertices.


Throughout, we assume that in any of the lists maintained for a vertex by the algorithm, we can directly iterate over vertices of a particular subset in (,,,).
(This can be done, for example, by storing these lists as four separate linked lists, one per each such subset.)

The following invariant is concerned with the information we need from v.


	For any vertex v ∈ V ∖, v counts the number of all neighbors of v  in .
	For any vertex v ∈, v counts the number of neighbors of v that are in  but not in , i.e., are in ∖.


By Invariant <ref>, any vertex either knows the number of all its neighbors in  or is a low-degree vertex
and can iterate over all its neighbors in O(m^1/4) time to count this number. Moreover, even a low-degree vertex knows
the number of its neighbors in ∖. This is crucial for our algorithm as in some cases, we need to iterate over many vertices that belong to  and
decide if they can join  and hence cannot spend O(m^1/4) time per each vertex to determine this information. Note that the information we obtain in this way is “noisy”, as we ignore some neighbors of vertices in  that
are potentially in . We shall address this problem
using a post-processing step that exploits the fact that the total number of ignored vertices, i.e., vertices in , is small.


The following invariant is concerned with the information we need from v.



	For any v ∈ V and and every u ∈v∩, v[u] counts the number of vertices in ∪ that belong to  and are neighbors of u (the entry in v[u] for any vertex u ∉ is
	).


Invariant <ref> allows us to infer some nontrivial information about the two-hop neighborhood of any vertex. We use Invariant <ref>
to quickly determine which neighbors of a vertex v can be added to  in case v is deleted from it. Similar to the one-hop information we obtain through maintaining Invariant <ref>, the information we obtain in this way
 is also “noisy”.


We show how to update the information per each vertex after a change in the topology or .
Maintaining v under edge updates is straightforward. To maintain v, each vertex simply keeps a 2-approximation of its degree in v.
Whenever the current actual degree of v differs from v by more than a factor of two, v updates v to its actual degree and informs all its neighbors u ∈v to update u.
This requires only O(1) amortized time.

The above information is a function of the underlying graph and not . We also need to update the information per each vertex that are functions of 
whenever  changes. Maintaining v is trivial for any vertex v, hence in the following we focus on the remaining two parts.


Once a vertex u changes its status in , we apply the following algorithm to
update the value of v for every vertex v  (we only need to update this for v ∈u).


Algorithm (u). An algorithm called whenever a vertex u enters or exists  to update v for neighbors of u.

	
  * If u ∈, update v for any vertex v ∈u not in  accordingly (i.e., add or subtract one depending on whether u joined or left ).
	
  * If u ∉, update v for every vertex v ∈u.




It is immediate to see that by running (u) in our main algorithm whenever a vertex u is updated in , we can maintain Invariant <ref>. Also each call to (u)
takes O(m^3/4) time in worst-case since in both cases of the algorithm, we only need to update O(m^3/4) vertices: (i) if u ∈, the algorithm only updates the vertices in V ∖ whose size is
O(m^3/4), and (ii) if u ∉, u only has O(m^3/4) neighbors to update. We also point out that v can be updated easily whenever an edge incident on (u,v) is inserted or deleted in O(1) time
by simply visiting u and updating v accordingly.

Now consider updating ·. We use the following algorithm on a vertex u that has changed its status in 
to update v for every vertex v in the
graph (we only need to update this information for the two-hop neighborhood of u).


Algorithm (u). An algorithm called when a vertex u enters or exists  to update v for the two-hop neighborhood of u. 

	
  * If u ∈∪, for any vertex w ∈u:
	
	
		
  * If w belongs to , iterate over all vertices v ∈w.
		
  * For any such v, update v[w] accordingly (i.e., add or subtract one depending on whether u joined or left ).
	




Each call to (u) takes O(m^3/4) time in the worst case. This is because u only updates its neighbors if it has O(m^1/2) neighbors as u should be in ∪ and
when it updates its neighbors, it changes the counter of O(m^1/4) vertices (as w should be in ). This ensures that the running time of the algorithm is O(m^1/2· m^1/4) = O(m^3/4).
Whenever an edge (u,v) is updated in the graph, we can run a similar algorithm to update the two-hop neighborhood of u and v in the same way in O(m^3/4) time; we omit the details.
It is also straightforward to verify that by running (u) in our main algorithm whenever a vertex u is updated in , we preserve Invariant <ref>.

Finally, recall that we also need a preprocessing step that given a graph G initializes this data structure. We can implement this step by first initializing all non-MIS-related information in this data structure in O(m) time (we do not need to
handle isolated vertices at this point).
Next, we run the greedy MIS algorithm to compute an MIS   of this graph in O(m) time (again only on non-isolated vertices).
Finally, we update the information for every vertex in  using the two procedures above which takes O(m · m^3/4) time in total.
(We note that a more efficient implementation for this initial stage is possible.)
As K = Ω(m) in Lemma <ref>, this (one time only) initialization cost is within the bounds stated in the lemma statement.

We summarize the results in this section in the following two lemmas.


	After updating any single edge, the data structure stored in the algorithm can be updated in O(m^3/4) amortized time. Moreover, Invariants <ref> and <ref>
	hold after this update.



	After updating any single vertex in , the data structure stored in the algorithm can be updated in O(m^3/4) worst case time. Moreover, Invariants <ref> and <ref>
	hold after this update.








 §.§ The Update Algorithm


The update algorithm is applied following edge insertions and deletions to and from the graph. After
any edge update, the algorithm updates the data structure and . In order to do the latter task, the algorithm may need to remove and/or insert multiple vertices from and to .
Since we already argued that maintaining the data structure requires O(m^3/4) amortized time (by Lemma <ref>), from now on, without loss of generality, we only
measure the time needed to fix  after any edge update and ignore the additive term needed to update the data structure.
The following is the core invariant that we aim to maintain in our algorithm.

[Core Invariant]
	Following every edge update, the set  maintained by the algorithm is an MIS of the input graph. Moreover,
	
	
	
  *  if only a single vertex leaves , then there is no restriction on the number of vertices joining  (which could be zero).
	
  *  if at least two vertices leave , then at least twice as many vertices join .
	
	
	In either case, the total time spent by the algorithm to fix  for an edge update is at most an O(m^3/4) factor larger than the total number of vertices leaving and joining .


Before showing how to maintain Invariant <ref>, we present the proof of Lemma <ref> using this invariant.


The main idea behind the proof is as follows.
By Invariant <ref>, after each step, the size of  either decreases by at most one, or it will increase.
At the same time,  cannot grow more than n, the number of vertices in the graph. It then follows that the average number of
changes to  per each update is O(1). As we only spend O(m^3/4) per each update,
we obtain the final result. We now present the formal proof using the following charging scheme.

Recall that we compute an MIS  of the initial graph in the preprocessing step and that the initialization phase takes O(m · m^3/4) time in total.
We place O(m^3/4) “extra budget” on vertices in the initial graph that do not belong to  to be spent
later when these vertices are inserted to . As the number of  such vertices is O(m), this
extra budget can be charged to the time spent in the initialization phase. Note that at this point, an extra budget is allocated to any vertex not in  and we maintain this throughout the algorithm.

Whenever an update results in only a single vertex leaving  (corresponding to Part <ref> of Invariant <ref>),
we spend O(m^3/4) time to handle this vertex and additionally place O(m^3/4) budget on this vertex and then for the vertices inserted to , we simply use the extra budget allocated to these vertices before
to charge for the O(m^3/4) time needed to handle each.
If an update results in removing k > 1 vertices from , we know that at least 2 · k vertices would be added to  after this update (corresponding to Part <ref> of Invariant <ref>).
In this case, we use the O(m^3/4) extra budget on these (at least) 2· k vertices that are joining  to charge for the time needed to insert these vertices to , remove the k initial vertices from , and place O(m^3/4) extra budget
on every removed vertex. As a result, this type of updates can be handled free of charge. Finally, if an update only involves inserting some vertices to , we simply use the budgets on these vertices to handle them free of charge.
This finalizes the proof of Lemma <ref>.

We point out that using the above charging scheme, we can also argue that the average number of changes to  is O(1) in each update.



Fix a time step t and suppose the invariant holds up until this time step. Let e_t = (u_t,v_t) be the edge updated at this time step.
In the remainder of this section, we describe one round of the update algorithm to handle this single edge update and preserve Invariant <ref>.



  §.§.§ Edge Deletions


We start with the easier case of deleting an edge e_t = (u_t,v_t).

Case 1: Neither u_t nor v_t belong to . In this case, there is nothing to do.

Case 2: u_t belongs to  but not v_t (or vice versa). After deleting the edge e_t, it is possible that v_t may need to join  as well. We first check whether v_t = 0.
If not, there is nothing else to do as v_t is still adjacent to some vertex in . Otherwise, we need to ensure that v_t does not have any neighbor in  (outside those vertices counted in v_t).
If v_t ∈ V ∖, by Invariant <ref>,
v_t counts all neighbors of v_t and hence there is nothing more to check. If v_t ∈, we can go over all the O(m^1/4) vertices in the neighborhood of v_t and check
whether v_t has a neighbor in  or not. This only takes O(m^1/4) time in the worst case. Again, if we find a neighbor in  there is nothing else to do. Otherwise, we add v_t to  and update
the data structure which takes O(m^3/4) time in the worst case by Lemma <ref>. After this step,  is again a valid MIS and hence Invariant <ref> is preserved as
we only spent O(m^3/4) time and inserted at most one vertex to  without deleting any vertex from it.





Case 3: Both u_t and v_t belong to . This case is not possible in the first place by Invariant <ref> as otherwise  maintained by the algorithm before this edge update was not an MIS.



  §.§.§ Edge Insertions


We now consider the by far more challenging case of edge insertions where we concentrate bulk of our efforts.
It is immediate to see that the only time we need to handle an edge insertion is when the inserted edge e_t = (u_t,v_t) connects two vertices already in  (there is nothing to do in the remaining cases).
Hence, in the following, we assume both u_t and v_t belong .

To ensure that  is an independent set, we first need to remove one of u_t or v_t from it and then potentially insert some of the neighbors of the deleted vertex to  to ensure its maximality.
Let u_t be the deleted vertex (the choice of which vertex to delete is arbitrary). After deleting u_t, we update the algorithm's data structure in O(m^3/4) time by Lemma <ref>.

Let L := u_t∩ denote the set of low degree neighbors of u_t.
We first show that one can easily handle all neighbors of u_t which are not in L. To do so, we can iterate over these vertices as there are O(m^3/4) of them and for any vertex w, by Invariant <ref>, we know
whether w can be added  or not by simply checking w. Hence, we can add the necessary vertices to  and spend O(m^3/4) time for each inserted one using Lemma <ref>.
As such, we spend O(m^3/4) time for iterating the vertices which did not join  and k · O(m^3/4) time for the k vertices that joined .
Hence, Invariant <ref> is preserved after this step.

We now consider the challenging case of updating the neighbors of u_t that belong to L. As the number of such vertices is potentially very large, we cannot iterate over all of them anymore.
Define the following subsets of L:


	
  * ⊆ L: the set of vertices in L that do not have any neighbor in .  
	
  * ⊇: all vertices w ∈ L where w = 0 i.e., our algorithm did not count any  neighbor for them in . Recall that w does not count
	all neighbors of w in ; it is missing the vertices in  by Invariant <ref>. 
	
  * ⊇⊇: all vertices w ∈ L, where u_t[w] = 0. Again, recall that u_t[w_t] does not count
	all neighbors of w ∈w (and consequently in ); it misses the vertices in  in w (and additionally  in )
	by Invariant <ref>. 
	


Let :=, := and :=, where ≤≤.
Our algorithm does not know the sets  and  or even their sizes. However, the update algorithm knows the value of  and
has access to vertices in  through the list u_t and can iterate over them in O(1) time per each vertex in  (notice that even this can be potentially too time
consuming as size of this list can be too large). We consider different cases based on the value of these parameters.

Case 1: when  is small, i.e., ≤ 4 · m^3/4.
In this case, we iterate over vertices w ∈ in O() = O(m^3/4) time and check whether w = 0 or not.
This allows us to compute the set  and  as well. We further distinguish between two cases.

Case 1-a: when  is very small, i.e., ≤ 4 · m^1/2.
We iterate over vertices w ∈ and for each vertex, spend  O(m^1/4)  time to
go over all its neighbors and decide whether w has any neighbor in  or not (degree of w is O(m^1/4) since it belongs to ). Hence, in this case, we can obtain the
set  fully in O(m^3/4) time in total.

We then iterate over vertices in , insert each one greedily to , and update the data structure in O(m^3/4) time using Lemma <ref>. It is possible that some vertices in  are adjacent to each other and hence
before inserting any vertex w, we first need to check w to make sure it is zero still (by Invariant <ref> and since all vertices in  belong to , any vertex added to  here would update
w for any neighbor w). Hence, in this case, we spend O(m^3/4) time for each vertex inserted to  and did not delete any vertex from it. Therefore, Invariant <ref> is preserved after the edge update
in this case.



Case 1-b: when  is not very small, i.e., > 4 · m^1/2.
In this case, we cannot afford to compute  explicitly. Rather, we simply add the vertices in  to  directly,
without considering whether they are adjacent to vertices already in  or not at all (although we check that they are not adjacent to the previously inserted vertices from ).
As a result, it is possible that after this process,  is not an independent set of the graph anymore. To fix this,
we perform a post processing step in which we delete some vertices from  to ensure that the remaining vertices indeed form an MIS of the original graph.

Concretely, we go over vertices in  and insert each to  if none of its neighbors have been added to  in this step, and then invoke Lemma <ref> to update the algorithm's data structure. Since in this step, we
are only adding vertices that are in , we can check in O(1) time whether a vertex has a neighbor in  (that has been added in this step) or not by Invariant <ref>. This step clearly takes O(m^3/4) time per each vertex inserted to the
MIS.

At this point, it is possible that there are some vertices in  which are adjacent to the newly inserted vertices. By Invariant <ref>, we know that these vertices can only belong to  and hence there are at most m^1/4
of them. We iterate over all vertices in  and check whether they have a neighbor in  (by Invariant <ref>, we stored this information for these vertices) and mark all such vertices. Next,
we remove all these marked vertices from  simultaneously and update the algorithm's state by Lemma <ref>. We are not done yet though because after removing these vertices, it is possible that we may need to bring
some of their neighbors back to . We solve this problem recursively using the same update algorithm by treating these marked vertices the same as u_t.

We argue that Invariant <ref> is preserved. As the degree of vertices in  is bounded by m^1/4, the number of vertices
added to  in this part is at least /(m^1/4+1)≥ 2 · m^1/4 (by Fact <ref> and the assumption on  in this case). On the other hand, the number of vertices removed from 
is at most equal to size of  which is m^1/4. As a result, in this specific step, the number of vertices inserted to  is at least twice as many as the vertices removed from it.
For any vertex inserted or deleted from  also, we spent O(m^3/4) time. As we are performing the recursive step using the same algorithm, we can argue inductively that for any vertex deleted in those recursive calls, at least
twice as many vertices would be added to  and that the total running time would be proportional to the number of vertices added or removed from  times O(m^3/4). We point out that any recursive call that leads to another one in this algorithm
necessarily increase the number of vertices in  and hence the algorithm does indeed terminate (see also case 2).


Case 2: when  is not small, i.e., > 4 · m^3/4.
We use a similar strategy as case 1-b here as well. We iterate over all vertices in , greedily add each vertex to   as long as this vertex is not adjacent to any of the newly added vertices (which can be checked in O(1) time by Invariant <ref>), and
update the data structure using Lemma <ref>. As the maximum degree of
vertices in  is at most m^1/4, we add at least /m^1/4 + 1 > 2 · m^1/2 vertices to  by Fact <ref>. By Invariant <ref>, if a vertex belongs to , the only neighbors
of this vertex in  belong to  or  and hence has degree at least m^1/2. We go over these vertices next and mark them. Then, we remove all of them from  simultaneously and update the algorithm by Lemma <ref>.
Similar to case 1-b, we now also have to consider bringing some of the neighbors of these vertices to  which is handled recursively exactly the same way as in case 1-b.

We first analyze the time complexity of this step. Iterating over  takes O() = O(m) time and since we are inserting at least m^1/2 vertices from  to , we can charge the time needed
for this step to the time allowed for inserting these vertices to . Moreover, we inserted at least 2 · m^1/2 vertices to  and would remove at most m^1/2 vertices after considering violating vertices in  and . Hence,
number of inserted vertices is at least twice the number of removed ones at this step. We can also argue inductively that this property hold for each recursive call similar to the case 1-b. This finalizes the proof of this case.




To conclude, we proved that Invariant <ref> is preserved after any edge insertion or deletion in the algorithm, which finalizes the proof of Lemma <ref>.





§ MAXIMAL INDEPENDENT SET IN DYNAMIC DISTRIBUTED NETWORKS


We consider the  model of distributed computation (cf. <cit.>) which captures the essence of both spatial locality and congestion.
The network is modeled by an undirected graph G(V,E) where the vertex-set is V, and E corresponds to both the edge-set in the current graph and also the vertex pairs that can directly communicate with each other.
We assume a synchronous communication model, where time is divided into rounds and in each round, each vertex can send a message of size O(logn) bits to any of its neighbors, where n = V.
The goal is to maintain an MIS  in G in a way that each vertex is able to output whether or not it belongs to .

We focus on dynamically changing networks where both edges and vertices can be inserted to or deleted from the network. For deletions, we consider
graceful deletions where the deleted vertex/edge may be used for passing messages between its neighbors (endpoints),
and is only deleted completely once the network is stable again.
After each change, the vertices communicate with each other to adjust their outputs, namely make the network stable again.
We make the standard assumption that the changes occur in large enough time gaps, and hence the network is always stable before the next change occurs (see, e.g., <cit.>).
We further assume that each change in the network is indexed and vertices affected by this change know how many updates have happened before[This is only needed by our algorithm in Theorem <ref> to
have an approximation of the number of edges in the graph, which is a global quantity and cannot be maintained by each vertex locally].

There are three complexity measures for the algorithms in this model. The first is the so-called adjustment complexity, which measures the number of vertices that change their output as a result
of a recent topology change. The second is the round complexity, the number of rounds required for the network to become stable again after each update.
The third is the message complexity, measuring the total number of O(logn)-length messages communicated by the algorithm.

Our main result in this section is an implementation of Theorem <ref> in this distributed setting for maintaining an MIS in a dynamically changing network.

	Starting from an empty distributed network on n vertices, a maximal independent set can be maintained deterministically in a distributed fashion (under the communication model)
	over any sequence of vertex/edge insertions and (graceful) deletions with (i) O(1) amortized adjustment complexity, (ii) O(1) amortized round complexity, and (iii) O(m^3/4) amortized message complexity.
	Here, m denotes the number of dynamic edges.


The algorithm in Lemma <ref> can also be trivially implemented in this distributed setting, resulting in an extremely simple deterministic distributed algorithm for maintaining an MIS of a dynamically
changing graph in O(1) amortized adjustment complexity and round complexity, and O(Δ) amortized message complexity. As argued before, this simple algorithm already strengthens the previous randomized
algorithm of Censor-Hillel  <cit.> by virtue of being deterministic and not requiring an assumption of a non-adaptive oblivious adversary.  In the following, we compare our results in the distributed setting with
those of <cit.>.



  
Amortized vs in Expectation Guarantee. The guarantees on the complexity measures provided by our deterministic algorithms in this setting are amortized, while the randomized algorithm in <cit.> achieves
its bound in expectation which may be considered somewhat stronger than our guarantee. To achieve this guarantee however, the algorithm in <cit.>, besides using randomization, also assumes
a non-adaptive oblivious adversary. An adaptive adversary (the assumption supported by all our algorithms in this paper) can force the algorithm in <cit.> to adjust the MIS by Ω(n) vertices in every round, which
in turn blows up all the complexity measures in <cit.> by a factor of Ω(n). It is also worth mentioning that the guarantee achieved by <cit.> only holds in expectation and not with high probability and for a
fundamental reason: It was shown in <cit.> that for every value of k, there exists an instance for which at least Ω(k) adjustments are needed for any algorithm with probability at least 1/k (see Section 1.1 of their paper).



  
Broadcast vs Unicast. The communication in algorithm of <cit.> in each round is O(1) broadcast messages in expectation that requires only O(1) bits on every edge
(i.e., each vertex communicates the same O(1) bits to every one of its neighbors). As such, the total communication at every round of this algorithm is O(Δ) bits in expectation.
Our amortized O(Δ)-message complexity algorithm (distributed implementation of Lemma <ref>) also works with the same guarantee: indeed, every
vertex simply needs to send O(1) bits to all its neighbors in a broadcast manner so that their neighbors know whether to add or subtract the contribution of this vertex to or from their counter.
This is however not the case for our main algorithm in Theorem <ref> which requires a processor to communicate differently to its neighbor over each edge (in general, one cannot hope to achieve o(Δ) communication
with only broadcast messages). Additionally, this algorithm
now requires to communicate O(logn) bits (as opposed to O(1) in the previous two algorithms) over every edge. This is mainly due to the fact that in this new algorithm we need to communicate
with vertices which are at distance 2 of the current vertex and hence we need to carry the ID of original senders in the messages also.



  
Graceful vs Abrupt Deletions. A stronger notion of deletion in the dynamic setting is abrupt deletion in which the neighbors of the deleted vertex/edge simply discover that this vertex/edge is being deleted and
the deleted vertex/edge cannot be used for communication anymore right after the deletion happens. Censor-Hillel  <cit.> also extend their result to this more general setting and achieved the same guarantees except for
message complexity of abrupt deletion of a node which is now O(minlogn,Δ) broadcasts as opposed to O(1). We do not consider this model explicitly. However, it is straightforward to verify that our
amortized O(Δ)-message complexity algorithm (distributed implementation of Lemma <ref>) works in this more general setting with virtually no change and even still achieves amortized
O(1) broadcast per abrupt deletion of a vertex as well. We believe that our main algorithm in Theorem <ref> should also work in this more general setting with proper modifications but we did not prove this formally.




  
Synchronous vs Asynchronous Communication. We focused only on the synchronous communication in this paper. Censor-Hillel <cit.> also considered the asynchronous
model of communication and showed that their algorithm holds in this model as well, albeit with a weaker guarantee on its message complexity. Our algorithms can be modified to work in an asynchronous model as well, as at each stage of the algorithm
we can identify a (different) local “coordinator” that can be used to synchronize the operations with an added overhead that is within a constant multiplicative of the synchronous complexity (as per each update only vertices within two-hop neighborhood of a vertex
need to communicate with each other in our algorithm); we omit the details but refer the reader to Section <ref> for more information on the use of a local coordinator in our algorithms.




We now turn to proving Theorem <ref>, using the following lemma the same way we used Lemma <ref> in the proof of Theorem <ref>.



	Starting with any arbitrary graph on n vertices and m edges, a maximal independent set  can be maintained deterministically in a distributed fashion (under the communication model) over any
	sequence of K = Ω(m) vertex/edge insertions and (graceful) deletions as long as the number of edges in the graph remains within a factor 2 of m. The algorithm:
	
		
  * makes O(K) adjustment to  in total, i.e., has O(1) amortized adjustment complexity,
		
  * requires O(K) rounds in total, i.e., has O(1) amortized round complexity, and
		
  * communicates O(K · m^3/4) messages in total, i.e., has O(m^3/4) amortized message complexity.
	


The algorithm in Lemma <ref> is a simple implementation of our sequential dynamic algorithm in Lemma <ref>. In the following, we first adapt the data structures
introduced in Section <ref> to the distributed setting. We then show that with proper adjustments,  the (sequential) update algorithm in Section <ref> can also be used
in the model and prove Theorem <ref>.



 §.§ The Data Structure


We store the same exact information in Section <ref> per each vertex here as well and maintain Invariants <ref> and <ref>.
We first prove that the two
procedures  and  can both be implemented in constant rounds and O(m^3/4) messages in total. In particular,


	For any vertex u ∈ V,
	
	
  * (u) operation requires spending 1 round and m^3/4 messages in total, and
	
  * (u) operation requires 2 rounds and 2· m^3/4 messages in total.
	


	Part (i). If u ∈, it only needs to send a message to its neighbors in V ∖ and inform them on the status of u (whether it is inserted to or deleted from ), which requires
	only 1 round (as they are all neighbors to u) and m^3/4 messages as V ∖≤ m/m^1/4 = m^3/4. If u ∉, it would update all its neighbors again in 1 round
	and m^3/4 messages as the latter is an upper bound on number of its neighbors.

	Part (ii). If u ∉∪ there is nothing to do. Otherwise, u needs to send a message to all its (at most m^1/2)
	neighbors that belong to  and ask them to relay this information
	to their neighbors. These vertices can then spend another round to inform all  their (at most m^1/4) neighbors about the status of u. This takes 2 rounds and m^1/2 + m^1/2· m^1/4 < 2· m^3/4 messages in total.


Lemma <ref> ensures that Invariants <ref> and <ref> (the only MIS-related information stored for u beside u that can be trivially updated) are preserved after
any change in  within a constant number of rounds and O(m^3/4) messages.

In the following, we briefly describe how to update the information stored for vertices per each topology change in the graph.



  
Vertex Updates. Let u be the updated vertex. In case of vertex insertion, we simply initialize the data structures at u and we are almost done as the neighbors of u are already informed about u being inserted to the graph
and hence can update their information locally. We only need to send u to all the neighbors (the time needed for this can be charged to the initialization cost of this algorithm).
Now suppose u is being deleted. We can update v and v for any neighbor v of u without any communication as they are informed that u is deleted. We can also run (u) (virtually) with no communication
as this procedure only informs the neighbors of u that this vertex is being deleted from  and by knowing that u has left the graph, any vertex v in the neighborhood of u can update v accordingly. Finally, we can also
run (u) with only 1 round of communication and m^3/4 messages (see Lemma <ref>)
by relaying the information from the neighbors of u (which are informed about u leaving the graph) to their neighbors.



  
Edge Updates. These updates are handled exactly the same as in our sequential algorithm. Let (u,v) be the updated edge. Nertices u and v can update all information
except for updating · (in particular · can be updated by the procedure described in Section <ref> with O(1) worst-case round complexity and O(1) amortized message complexity).
To do the latter task, vertex u (resp. v) can simulate (v) (resp. (u)) as described above, which takes
m^3/4 messages and 1 round.

We hence showed that after each change in the topology, all the information stored for vertices can be updated in O(1) rounds and O(m^3/4) amortized messages.



 §.§ The Distributed Algorithm


We design a distributed algorithm for updating  in the network in the spirit of our update algorithm in Section <ref>.
The algorithm is a simple adaption of our sequential algorithm to this dynamic model.
For every update, we first perform the steps in the previous section to update the information on every vertex in the graph and then make the network stable again by adjusting .

Throughout, we aim to maintain the following invariant which is the direct analogue of Invariant <ref> in the dynamic setting.


	Following every vertex/edge update, the set  maintained by the algorithm is an MIS of the input graph. Moreover,
	
	
  * if only a single vertex leaves  then there is no restriction on the number of vertices joining  (which could be zero).
	
  * if at least two vertices leave , then at least twice as many vertices are added to .
	
	In either case, the worst case number of rounds and messages spent by the algorithm for any update is within, respectively, an O(1) and an O(m^3/4) factor of the total number of vertices leaving and joining .


Using the same exact argument as in the proof of Lemma <ref>, maintaining Invariant <ref> ensures that the amortized adjustment complexity and amortized round complexity of the algorithm is O(1)
and its amortized message complexity is O(m^3/4). Hence, to prove Lemma <ref>, it suffices to prove that Invariant <ref> is preserved after every update.
We consider different cases based on insertion and deletion of edges and vertices.



  §.§.§ Edge Deletions


Suppose we delete the edge (u,v). We only consider the case that u belongs to  and v is not; the remaining cases are either symmetric to this one or need no update in  (see Section <ref>).
If v is not in , by Invariant <ref>, it knows all its neighbors in  and can decide whether to join  or not to locally; if it enters , it can update the network in O(1) rounds and
O(m^3/4) messages by Lemma <ref>. If v is in , it first sends a message to all its O(m^1/4) neighbors and ask for their status to which its neighbors reply whether they belong to  or not.
This only takes 2 rounds and O(m^1/4) communication and then v can decide again whether to join  or not to. Note that this part of the result holds even with abrupt deletions.



  §.§.§ Edge Insertions


Suppose we insert the edge (u,v). We only consider the case when both u and v belong to ; the remaining cases need no update in  (see Section <ref>). Remember that in Section <ref>, we needed
to handle these updates in three separate cases. While the algorithm and analysis in each case is different, the procedures needed to carry the information around the network are essentially the same among these cases and hence in the following, for simplicity,
we only consider one of the main cases, namely case 1-b (see Section <ref> for definition of this case). The algorithm in the remaining cases can be adapted to this setting in the same exact way.

Recall that in this case, the vertex u is deleted from  and moreover u knows the set  entirely, which is of size O(m^3/4). The general approach is to make u a “coordinator” for running the update algorithm
in Section <ref> by communicating with its two-hop neighborhood and gather the necessary information to run the sequential update algorithm.

Vertex u first sends a message to all its neighbors in 
and asks for their status to which they respond whether or not they belong to . This takes 2 rounds and O(m^3/4) messages.
Next, u informs one of its neighbors that it can join  and this new vertex updates its status and the information in the graph which takes O(1)
rounds and O(m^3/4) messages by Lemma <ref>. After this, u again sends a message to all its neighbors in  and asks for their status in  to which they respond whether they belong to  or whether one of their neighbors in  has been added to  in this step. Then, again, u informs one of its neighbors (if such exists) that it can join , and continues. This way, we only spend O(1) rounds
and O(m^3/4) communication per each vertex entering  in addition to O(1) rounds and O(m^3/4) communication for communicating with neighbors of u that would not join  eventually.

After processing the list , we also need to delete from , the set of vertices in  that are now incident to vertices in  that just joined . Note that such vertices are necessarily in the two-hop neighborhood
of u and hence u can communicate with them (which are only O(m^1/4) many) in O(1) rounds and use the above idea to implement the same update algorithm in Section <ref> in this model. This allows us to
preserve Invariant <ref> by the same exact analysis in Section <ref>.



  §.§.§ Vertex Deletions




This case is essentially equivalent to the edge insertion case discussed above. Since we have a graceful deletion, we can treat the deleted vertex the same way as in Section <ref> by deleting it from
 (if it belonged to it) and using it as the “coordinator” to implement the process described in Section <ref>.

 

  §.§.§ Vertex Insertions


The only thing we need to do in this case is to check whether we need to add this new vertex to  or not. If this vertex is not in , it already knows this information and hence can decide whether or not to join ; after
that we are done. Otherwise, if the vertex belongs to , it sends a message to all its O(m^1/4) neighbors and ask for their status in , and use that to decide about joining . In either case,
we only need O(1) rounds and O(m^1/4) total communication. After this, we update the neighbors using first part of Lemma <ref> in O(m^3/4) communication and O(1) rounds.



To conclude, we showed that Invariant <ref> is preserved after any edge or vertex insertion or deletion by the distributed algorithm, hence proving Lemma <ref>. We are now ready to prove
Theorem <ref>.



	The proof is identical to the proof of Theorem <ref>. The only difference is that in this distributed setting, we are not able to maintain the exact number of edges in the graph in a distributed fashion across all vertices.
	However, recall that we assumed vertices affected by an update in the topology know the index of this update, i.e., how many updates have happened before this one. Hence, whenever the number of updates reaches Ω(m),
	any vertex that knows this information sends a message to all its neighbors to terminate the process which would then be broadcast across the whole graph. This takes O(m) rounds and O(m) communication and can be charged
	to the total number of updates, i.e., Ω(m) in this step. Hence, the vertices can initialize their data structure using the new choice of m and continue the distributed algorithm in Lemma <ref>.









abbrv




































§ AN Ω(N) LOWER BOUND ON WORST-CASE ADJUSTMENT COMPLEXITY


By a straightforward modification of the lower bound example in <cit.>, we can show that adjustment-complexity of any deterministic algorithm is Ω(n) in the worst-case.

Consider the following example: Let G_1 be a complete bipartite graph between two sets of vertices
L_1 and R_1, each of size n/4. We create an identical copy of G_1 named G_2 with bipartition L_2,R_2 on the remaining vertices and let G be the union of these graphs.
Consider any deterministic algorithm  for maintaining an MIS on G.
Without loss of generality, assume L_1 ∪ L_2 is the MIS chosen by  (in any MIS of G either L_1 is entirely in the MIS or R_1 and similarly for L_2 and R_2).
Let u_1 and u_2 be two arbitrary vertices in L_1 and L_2. The adversary starts deleting all edges incident to all vertices in L_1 ∖u_1 and L_2 ∖u_2.  Finally, it adds an edge between u_1 and u_2.
We argue that at some point during these updates,  adjusted Ω(n) vertices in the maintained MIS.
There are two cases to consider. For simplicity of exposition, we assume that at each time step, all edges incident to a vertex are deleted at once.

Suppose at some point before inserting the last edge,
 decides to add a vertex in R_1 to the MIS for the first time (the argument is symmetric for R_2 as well). Since u_1 is incident to all vertices in R_1, this means that u_1 needs to leave the MIS. Also, since a vertex in
R_1 has joined the MIS, we know that there cannot be any edge from vertices in the MIS to any vertex in R_1 (as we start with a complete bipartite graph and assumed that all edges incident to a vertex are deleted simultaneously). This
means that after this step, all vertices in R_1 should join the MIS to ensure maximality. Therefore, at this step, Ω(n) vertices are inserted to the MIS at once, proving the claim in this case.

Now suppose that before inserting the last edge, no vertex in R_1 and R_2 belong to the MIS and hence both u_1 and u_2 should be inside it. By adding an edge between u_1 and u_2,  is forced to remove
at least one of them, say u_1, from the MIS, which in turn forces all R_1 to join MIS to keep the maximality. Hence, again, Ω(n) vertices are inserted to the MIS at once, finalizing the proof.


We remark that this simple example explains why we obtain our results in amortized bounds rather than worst-case bounds. 





