Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi Seri Khoury Aaron Schild Gregory Schwartzman





















theoremTheorem 
lemmaLemma
remarkRemark
corollaryCorollary
claimClaim
definitionDefinition
axiomAxiom
observationObservation
factFact
propositionProposition
oqOpen Question


lemma-repeat[1]

  Lemma <ref> 

theorem-repeat[1]

  Theorem <ref> 










polylog
Unweighted
poly
CONGEST

refproofProof

































	
	
	
		Improved Distributed Approximations for Maximum-Weight Independent Set
    Ken-ichi KawarabayashiNII, Japan, 
		Seri KhouryUniversity of California, Berkeley,  seri_khoury@berkeley.eduAaron SchildUniversity of California, Berkeley, Gregory SchwartzmanNII, Japan, 
    
================================================================================================================================================================================================



	
		We present improved results for approximating maximum-weight independent set () in the CONGEST and LOCAL models of distributed computing. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let (n,Δ) be the the running time of finding a maximal independent  set () in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for  in O((n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as high as (n). Whether their algorithm is deterministic or randomized depends on the  algorithm that is used as a black-box. Our results:
		
			
  * A deterministic O((n,Δ)/ϵ)-round algorithm that finds a (1+ϵ)Δ-approximation for  in the CONGEST model.
			
  * A randomized ((loglog n)/ϵ)-round algorithm that finds, with high probability, a (1+ϵ)Δ-approximation for  in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result. 		Due to a lower bound of Ω(√(log n/loglog n)) that was given by Kuhn, Moscibroda and Wattenhofer [JACM, 2016] on the number of rounds for any (possibly randomized) algorithm that finds a maximal independent set (even in the LOCAL model) this result implies that finding a (1+ϵ)Δ-approximation for  is exponentially easier than . 
			
  * A randomized O(log n·(loglog n)/ϵ)-round algorithm that finds, with high probability, a 8(1+ϵ)α-approximation for  in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α<Δ/(8(1+ϵ)), this result improves upon the previous best known result in both the approximation factor and the running time. 
		
		
		One may wonder whether it is possible to approximate  in fewer than (loglog n) rounds. We show that this is possible for unweighted graphs of maximum degree Δ≤ n/log n. For such graphs, we give a randomized O(1/ϵ)-round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/(1+ϵ)(Δ+1), which is a (1+ϵ)(Δ+1)-approximation to the optimal solution. This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any (possibly randomized) algorithm that finds an independent set of size Ω(n/Δ) in unweighted graphs, even in the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ=Ω(n/log^*n).
	
empty


























§ INTRODUCTION AND RELATED WORK


One of the most fundamental problems in distributed graph algorithms is the maximal independent set problem (), where given an input graph, we need to find a maximal subset of the nodes such that no two nodes in the subset are adjacent. This problem has received a tremendous amount of attention in various distributed models (see for example <cit.>). It is considered one of the four classic problems of local distributed
algorithms, along with edge coloring, vertex coloring, and maximal matching <cit.>.

Independent sets have many applications in practical and theoretical computer science. Especially independent sets of large size. These include applications in economics <cit.>, computational biology <cit.>, coding theory <cit.>, and experimental design <cit.>. In unweighted graphs, a maximum independent set is an independent set of maximum size. In weighted graphs, a maximum-weight independent set () is an independent set of maximum total weight, where by total we mean the sum of weights of nodes in the independent set. 



In an unweighted graph, any  constitutes a Δ-approximation for , where Δ is the maximum degree of a node in the graph. This implies that  cannot be easier than Δ-approximation for  in unweighted graphs, regardless of the computational model. This leaves a natural question of whether Δ-approximation for  is easier than . In the classical sequential setting, finding an  has the same complexity as finding a Δ-approximation for  (even in weighted graphs) as both problems admit simple linear-time greedy algorithms. In this work, we show that in the distributed setting, finding a (1+ϵ)Δ-approximation for  is exponentially easier than .



 §.§ Distributed Computing and Our Results


The major two models of distributed graph algorithms are the LOCAL and CONGEST models. In the LOCAL model <cit.>, there is a synchronized communication network of n computationally-unbounded nodes, where each node has a unique O(log n)-bit identifier. In each communication round, each node can send an unbounded-size message to each of its neighbors. The task of the nodes is to compute some function of the network (e.g., its diameter, the value of a maximum independent set, etc.), while minimizing the number of communication rounds. The CONGEST model <cit.> is similar to the LOCAL model, where the only difference is that the message-size is bounded by O(log n) bits. 


In this work we study the problem of approximating , which has been studied in both the LOCAL and CONGEST models <cit.>. In unweighted graphs, one can find a Δ-approximation for  by finding an . In recent years, our understanding of the complexity of  has been substantially improving<cit.>, leading to a recent remarkable breakthrough by Rozhon and Ghaffari <cit.>, where they show a deterministic (log n)-round algorithm for finding an , even in the CONGEST model. This result also implies a randomized algorithm that finds an  with high probability in O(logΔ)+(loglog n) rounds, in the CONGEST model[We say that an algorithm succeeds with high probability if it succeeds with probability 1-1/n^c for an arbitrary constant c>1.] <cit.>. 
 

In a weighted graph, an  doesn't necessarily constitute a Δ-approximation for . For the weighted case, Bar-Yehuda et al. <cit.> showed a Δ-approximation algorithm in the CONGEST model that takes O((n,Δ)·log W) rounds, where (n,Δ) is the running time for finding an  in graphs with n nodes and maximum degree Δ,  and W is the maximum weight of a node in the graph (which can be as high as (n)). Whether their algorithm is deterministic or randomized, depends on the  algorithm that is used as a black-box.

In this work we present faster algorithms compared to <cit.>, by paying only a (1+ϵ) multiplicative overhead in the approximation factor. Our main result (Theorem <ref>) is a randomized algorithm that achieves an exponential speed-up compared to <cit.>. Our results:



	


	

Due to a lower bound of Ω(√(log n/loglog n)) that was given by Kuhn, Moscibroda and Wattenhofer <cit.>, against any (possibly randomized) algorithm that finds an , even in the LOCAL model, Theorem <ref> implies that finding a (1+ϵ)Δ-approximation for  is exponentially easier than .  

Using the algorithm from Theorem <ref>, we can also get an improved approximation algorithm for a wide range of arboricity. Let α be the arboricity of the input graph (See also Definition <ref>). For graphs of arboricity α≤Δ/(8(1+ϵ)), Theorem <ref> improves upon <cit.> in both the running time and approximation factor.


	



  
Results for unweighted graphs: Recently, Boppana et al. <cit.> showed that running the one-round classical ranking algorithm yields a solution with an expected weight at least w(V)/(Δ+1), where w(V) is the total weight of nodes in the graph.[To the best of our knowledge, the classical ranking algorithm has first appeared in the book of Alon and Spencer <cit.> and is due to Boppana (see also the references for this algorithm in <cit.>).] In the classical ranking algorithm, each node v picks a number r_v uniformly at random in [0,1]. If r_v>r_u for any neighbor u of v, then v joins the independent set. Since every node joins the independent set with probability at least 1/(Δ+1), the expected weight of the independent set is at least w(V)/(Δ+1). However, algorithms that work well in expectation don't necessarily work well with good probability. In fact, for the algorithm given by <cit.>, it is not very hard to construct examples in which the variance of the solution is very high, in which case the algorithm doesn't return the expected value with high probability. In this work we prove the following stronger theorem for any algorithm.


	Any algorithm that finds an independent set of size Ω(n/Δ) in unweighted graphs, with success probability p≥ 1-1/log n must spend Ω(log^*n) rounds, even in the LOCAL model.


Interestingly, this hardness result applies for graphs of maximum degree Δ=Ω(n/log^*n). One may wonder whether we can extend the lower bound for much smaller maximum degree graphs. We rule out this possibility, with the following theorem. The proof of Theorem <ref> relies on a novel idea for analyzing the classical ranking algorithm using martingales, and the local-ratio technique, on which we elaborate in the technical overview. 


	For unweighted graphs of maximum degree Δ≤ n/log n, there is an O(1/ϵ)-round algorithm in the CONGEST model that finds, with high probability, an independent set of size at least  n/(1+ϵ)(Δ+1).




  
Further Related Work. 

Ghaffari et al. <cit.>, showed that there is an algorithm for the LOCAL model that finds a (1+ϵ)-approximation for  in O((log n/ϵ)) rounds, for a constant ϵ. The results in <cit.> give a lower bound of Ω(log^* n) rounds for any deterministic algorithm that returns an independent set of size at least n/log^*n on a cycle, and a randomized O(1)-round algorithm for O(1)-approximations in planar graphs, in the LOCAL model. The results by <cit.> give fast algorithms for approximating  in unweighted graphs, where the approximation guarantees are only in expectation. 



  
Road-map: 
In Section <ref> we provide a technical overview. Section <ref> contains some basic definitions and useful inequalities. The technical heart of the paper starts in Section <ref>, where we prove our first two results (Theorems <ref> and <ref>). Our results for low-degree and low-arboricity graphs are presented in Sections <ref> and <ref>, respectively. Our lower bound result is presented in Section <ref>. Finally, we conclude the paper with a discussion and open questions in Section <ref>.




§ TECHNICAL OVERVIEW




  
Results for weighted graphs: Our first two results (Theorems <ref> and <ref>) share a similar proof structure. First, we show that there are fast algorithms for O(Δ)-approximation. Then we use the local-ratio technique <cit.> to prove a general boosting theorem that takes a T-round algorithm for O(Δ)-approximation, and use it as a black-box to output a (1+ϵ)Δ-approximation in O(T/ϵ) rounds. An overview of the local-ratio technique and the boosting theorem is provided in Section <ref>. The key ingredient to show a fast O(Δ)-approximation algorithm is a new weighted sparsification technique, where we show that it suffices to find an independent set of a good approximation in a sparse subgraph. An overview of the weighted sparsification technique is provided in Section <ref>.

Our improved approximation algorithm for low-arboricity graphs (Theorem <ref>) uses Theorem <ref> as a black-box, where the main technical ingredient is the local-ratio technique. An overview of this algorithm is also provided in Section <ref>.



  
Results for unweighted graphs: Our upper bound for unweighted graphs of maximum degree Δ≤ n/log n (Theorem <ref>) has a similar two-step structure as the first two results. We first show an O(Δ)-approximation algorithm, and then we use the local-ratio technique to boost the approximation factor. For the O(Δ)-approximation part, we show that running the classical one-round ranking algorithm (that was used by <cit.>) for c rounds already returns an O(Δ)-approximation for unweighted graphs of maximum degree Δ≤ n/log n, with probability ≈ 1-1/n^c. The main technical ingredient for showing this result is a new analysis of the classical ranking algorithm using martingales. An overview of this result is provided in Section <ref>. Finally, in Section <ref>, we provide an overview of the lower bound result (Theorem <ref>).  


 §.§ Weighted Sparsification for O(Δ)-Approximation


A good way to understand the O(Δ)-approximation algorithm is to first consider the unweighted case. Let G=(V,E) be an unweighted graph. We can find an O(Δ)-approximation for  in G as follows. First, we sample a sparse subgraph H of G with the following properties. (1) The maximum degree Δ_H of H is small (O(log n)). (2) The ratio between the number of nodes (n_H) and the maximum degree of H is at least as in G, up to a constant multiplicative factor. That is, n_H/Δ_H=Ω(n/Δ). Since any  in H has size at least n_H/Δ_H=Ω( n/Δ), it suffices to find an  in H, which take (n_H,Δ_H)≤(n,log n) rounds (recall that (n,Δ) is the running time of finding an  in graphs of n nodes and maximum degree Δ). By the recent breakthrough of Rozhon and Ghaffari <cit.>, (n,log n)=O(loglog n) +(loglog n)=loglog n rounds. Furthermore, sampling a subgraph with the aforementioned properties is almost trivial. Each node joins H with probability min{log n/Δ,1}, independently. It is not very hard to show, via standard Chernoff (Fact <ref>) and Union Bound arguments, that H has the desired properties. While this approach is straightforward for the unweighted case, it runs into challenges when trying to apply it for the weighted case, as we explain next.




  
The challenge in weighted graphs: Perhaps the first thing that comes into mind when trying to extend the sampling technique to weighted graphs is to try to sample a sparse subgraph H with the following properties. (1) The maximum degree Δ_H=O(log n). (2) The ratio between the total weight in H and the max degree of H is the same as in G, up to a constant multiplicative factor. That is w(V_H)/Δ_H=Ω( w(V)/Δ), where w(V_H) is the total weight of nodes in H and w(V) is the total weight of nodes in G. However, this approach runs into two challenges. The first challenge is that in the weighted case, an  doesn't necessarily constitute a Δ-approximation for . Therefore, even if we are able to sample a subgraph H with the desired properties, running an  algorithm on H might result in an independent set of a very small weight. To overcome this challenge, we show a very simple (n,Δ)-round algorithm that finds an O(Δ)-approximation. This algorithm runs an  algorithm on the subgraph induced by nodes that are relatively heavy, compared to their neighbors. Specifically, a node is considered relatively heavy compared to its neighbors, if it is of weight at least Ω(1/Δ)-fraction of the sum of weights of its neighbors. It is not very hard to show that this algorithm returns an independent set of total weight Ω(w(V)/Δ), where w(V) is the total weight of nodes in the graph. The proof of this argument is provided in Section <ref>.

Furthermore, another challenge is that the same sampling procedure doesn't work for the weighted case. In particular, if we sample each node with probability p=min{(log n)/Δ,1}, then light-weight nodes will have the same probability of joining H as heavy-weight nodes. Intuitively, we need to take the weights into account. For this, we boost the sampling probability of a node v by an additive factor of w(v)log n/w(V), where w(v) is the weight of v and w(V) is the total weight of nodes in the graph. In order to show that the sampled subgraph has the desired properties, it doesn't suffice to use standard Chernoff and Union-Bound arguments. Instead, we present a more involved analysis that uses Bernstein's inequality (Fact <ref>). Observe that the nodes don't know the value w(V). Therefore, we define a notion of weighted degree of a node, which is the sum of weights of its neighbors. We show that it suffices for a node v to use the maximum weighted degree in its neighborhood, instead of w(V). The full argument is provided in Section <ref>.




 §.§ Boosting the Approximation Factor using Local-Ratio


A useful technique for approximation algorithms is the local-ratio technique <cit.>. In recent years, the local-ratio technique has been found to be very useful for the distributed setting <cit.>, and the Δ-approximation algorithm of <cit.> also uses this technique. In this work we use local-ratio to boost the approximation guarantee for . We start with stating the local-ratio theorem for maximization problems. Here, we state it specifically for . Given a weighted graph G_w=(V,E,w), where w is a  node-weight function w:V→ℝ, we say that an independent set I⊆ V is r-approximate with respect to w if it is r-approximate for the optimal solution in G_w.

[Theorem 9 in <cit.>]

	Let G_w=(V,E,w) be a weighted graph. Let w_1 and w_2 be two node-weight functions such that w=w_1+w_2. If an independent set I is r-approximate with respect to w_1 and with respect to w_2 then it is r-approximate with respect to w as well.


Theorem <ref> already gives a simple linear-time sequential algorithm for Δ-approximation for , as follows. Pick an arbitrary node v of positive weight, push it onto a stack, and reduce the weight of any node in the inclusive neighborhood of v (v and its neighbors) by w(v). Continue recursively on the obtained graph, until there are no nodes of positive weight. When there are no remaining nodes of positive weight, pop out the stack, and construct an independent set I greedily, as follows. For each node v that is popped out from the stack, add v to I, unless it already contains a neighbor of v. 

The reason that this simple algorithm gives a Δ-approximation is as follows. Consider the first iteration, when the algorithm picks an arbitrary node v, pushes it onto a stack, and reduces the weight of any node in the inclusive neighborhood of v by w(v). This first iteration implicitly defines two weight functions: the reduced weight function w_1, and the residual weight function w_2, where w=w_1+w_2. That is, the reduced weigh of a node u in the first step is w_1(u)=w(v) if it belongs to the inclusive neighborhood of v, and w_1(u)=0 otherwise. The residual weight of a node u is the remaining weight w_2(v)=w(v)-w_1(v). To prove that the algorithm returns a Δ-approximation, we can assume by reverse induction that I is a  Δ-approximation with respect to the residual weight function w_2. Furthermore, the independent set is constructed in a way such that it must contain at least one node in the inclusive neighborhood of v, where the weight of this node with respect to w_1 is w(v). Since the degree of v is at most Δ, and the value of the optimal solution with respect to w_1 is at most Δ w(v), it follows that I is also Δ-approximation with respect to the reduced weight function w_1. Hence, by the local-ratio theorem, the independent set is also a Δ-approximation with respect to w=w_1+w_2.

One can extend this idea, and rather than picking a single node in each step, the algorithm can pick an arbitrary independent set I', push all the nodes in I' onto a stack, and perform local weight reductions in the inclusive neighborhood of any node in I'. The algorithm continues recursively on the obtained graph after the weight reductions, until there are no remaining nodes of positive weight. Then, the algorithm constructs an independent set I by popping out the stack and adding nodes in the stack to I greedily. Using a similar local-ratio argument, one can show that this algorithm also returns a Δ-approximation for . The idea of picking an independent set rather than a single node in each step was used by <cit.> to show a Δ-approximation algorithm in O((n,Δ)log W) rounds.

In this work, we prove a simple yet powerful property about the local-ratio technique. Specifically, we show that the total weight of the independent set I that is constructed in the pop-out stage (with respect to the original input weight function w), is at least the total weight of the nodes in the stack (with respect to the residual weight function at the time they were pushed onto the stack). That is, let S be set of nodes that are pushed onto the stack. For v∈ S, let w_i_v be the residual weight of v at the time it was pushed onto the stack. We prove (Proposition <ref> in Section <ref>) that w(I)≥∑_v∈ S w_i_v(v). We refer to this property as the stack property.

The stack property allows us to show a general boosting theorem, as follows. We use the local-ratio algorithm described above, where in each step we pick an independent set I' that is (cΔ)-approximation for , for some constant c>1. Hence, intuitively, after ≈ c/ϵ steps, the total weight in the stack should be at least OPT(G_w)/(1+ϵ)Δ, where OPT(G_w) is the value of an optimal solution in the input graph G_w. The full argument of the boosting theorem is provided in Section <ref>.



  
Low-arboricity graphs: Moreover, the stack property allows us to show an improved approximation algorithm for low-arboricity graphs, as follows. In each step, we run a (1+ϵ)Δ-approximation algorithm on the subgraph induced by the nodes of degree at most 4α, where α is the arboricity of the graph. We push the nodes in the resulting independent set I' onto the stack, and perform local weight reduction in the neighborhoods of the nodes in I'. Then, we delete all the nodes of degree at most 4α, and continue recursively on the resulting graph. Finally, we construct an independent I by popping out the stack greedily. By a standard Markov argument, after log n push steps, the graph becomes empty. Furthermore, since in each step the algorithm finds a (1+ϵ)4α approximation in the subgraph induced by the nodes of degree at most 4α, and this independent set is pushed onto the stack, we are able to use the stack property to show that the constructed independent set I is roughly of the same approximation for G_w. The full argument for low-arboricity graphs is provided in Section <ref>.



 §.§ Analysis of the Ranking Algorithm using Martingales


In this section we provide an overview of our result for unweighted graphs of maximum degree Δ≤ n/log n  (Theorem <ref>).  First, we find an O(Δ)-approximation, and then we use the boosting theorem to get a (1+ϵ)Δ-approximation. To find an O(Δ)-approximation, we use the classical ranking algorithm. Recall that in the ranking algorithm, each node v picks a number r_v uniformly at random in [0,1]. If r_v>r_u for any neighbor u of v, then v joins the independent set. Let I be the independent set that is returned by the ranking algorithm. The crux of the analysis is in using concentration inequalities to get a high-probability lower bound on the number of nodes in I. However, it is unclear how to make this approach work, as the random variables X_v = 1_v∈ I are not independent. While these random variables are not independent, one can obtain a weaker result in this direction. Specifically, for graphs of maximum degree at most n^1/3/poly(log n), one can get a useful bound on the maximum dependency among these variables. In particular, one can show that each X_v is dependent on at most (n^1/3/poly(log n))^2 = n^2/3/poly(log n) other X_us, which makes it possible to show concentration using the bounded dependence Chernoff bound given in <cit.>. However, it is unclear how to use this approach for higher degree graphs.

The main idea of our approach is to view the ranking algorithm from a sequential perspective. Instead of picking ranks for the nodes and including a node in I if its rank is higher than that of its neighbors, we draw nodes v from V uniformly at random one at a time and add v to I if it is not adjacent to any previously drawn node. We show that the resulting independent set is identical in distribution to the independent set produced by the ranking algorithm (Proposition <ref> in Section <ref>). Note that this is not the same as a sequential greedy algorithm for maximal independent set, which would add v to I if it is not adjacent to any node in I (a weaker condition). The sequential perspective of the ranking algorithm allows us to think about the size of I incrementally. One could directly show concentration if the family of random variables {I_t}_t was a martingale. However, this is not the case, as |I_t+1| ≥ |I_t| so it is not possible for expected increments to be 0. Instead, we create a martingale by shifting the increments so that they have mean 0. More formally, let I_t be the independent set I after the first t nodes have been drawn. Let v_t be the tth node drawn. The random variable


    Y_t = |I_t| - |I_t-1| - [v_t∈ I | I_t-1]

has mean 0 conditioned on I_t-1. Therefore, the Y_ts are increments for the martingale X_t = ∑_i=1^t Y_t. Using Azuma's Inequality, one can show that X_t concentrates around its mean, which is 0. To lower bound the size of the obtained independent set I, one therefore just needs to get a lower bound on the sum of the increment probabilities [v_t∈ I | I_t-1]. This can be lower bounded by 1/2 when t= o(n/Δ) because when a node is drawn, it eliminates at most Δ other nodes from inclusion into I. But when t = Θ(n/Δ), the sum of these probabilities is already 1/2(Θ(n/Δ)) = Θ(n/Δ), so the independent set is already large enough, as desired. The reason that this technique works for Δ≤ n/log n is that the success probability is roughly exponential in n/Δ. Hence, by having Δ≤ n/log n, we get a high probability success, as desired. The full argument is provided in Section <ref>.



 §.§ An Overview of the Lower Bound

In this section we give an overview of our lower bound (Theorem <ref>). For the  deterministic case, one can show a lower bound for finding an independent set of size Ω(n/Δ) in a cycle, by a reduction to the classical lower bound of Linial for finding an  in a cycle <cit.>. However, for the randomized case, this approach becomes more challenging. In fact, the cycle graph cannot be a hard instance for finding an independent set of size Ω(n/Δ), as  there is a constant-round algorithm for low degree graphs (as  we show in Theorem <ref>). In order to show hardness for the randomized case, we use a cycle of cliques graph. We are able to reduce the problem of finding an independent set of size Ω(n/Δ) in a cycle of cliques, to the problem of finding an  in a cycle. And we use Naor's lower bound <cit.> for finding an  in a cycle, which holds even against randomized algorithms. We start by stating Naor's lower bound.

(Lower bound for the cycle <cit.>).
	Any randomized algorithm in the LOCAL model for finding a  maximal independent set that takes fewer than 1/2(log^* n) - 4 rounds, succeeds with probability at most 1/2, even for a cycle of length n.


Perhaps a good way to understand our reduction to Naor's lower bound is to first consider deterministic algorithms. Let  be a deterministic algorithm for approximate MaxIS. Suppose that it takes T(n) rounds in graphs of n nodes. We can use  to find a maximal independent set in a cycle C of n nodes, as follows. We start by running   on C to produce an independent set I. Since C is a cycle, there is a natural clockwise ordering for the nodes of I. Between any two consecutive nodes of I, there may be nodes along the cycle that are not adjacent to a node in I. We informally call these nodes the “gaps” between consecutive nodes in I. We can obtain a maximal independent set in C by “filling in” the gap between every two consecutive nodes in I with a maximal independent set (sequentially). To bound the runtime of this algorithm, we need to bound the maximum length of a gap. Since  is deterministic, it is not very hard to show that the maximum length of a gap is O(T(n)). This is because from a local perspective, the nodes cannot distinguish between C and a path of length ω(T(n)), by a standard indistinguishability argument. Hence, one can show that if there is a gap of length  ω(T(n)), then  doesn’t return the required approximation on a path of length ω(T(n)). As a result, filling in the  gaps between nodes in I takes O(T(n)) rounds. Therefore, by running 𝒜 on C and then filling in the gaps sequentially, we get an  in O(T(n)) rounds. And by Linial's lower bound <cit.>, we have that T(n)=Ω(log^*n).

However, the argument above fails if  is a randomized algorithm. The main issue is that when running a randomized algorithm on a cycle, the maximum length of a gap between two consecutive nodes in the independent set can be larger than O(T(n)). This is because randomized algorithms that succeed with high probability can fail with probability 1/(n), where n is the number of nodes in the graph. Hence,   can fail on a path of length O(T(n)) with probability 1/(T(n)) which is non-negligible when T(n)≪ n. In particular, since there are Ω(|C|/T(n))=Ω(n/T(n)) subpaths of length O(T(n)) in C, it is likely that 𝒜 fails on at least one of these subpaths. If on the the other hand the number of nodes in the O(T(n))-radius neighborhood of a node was larger, then one could hope to get around this issue, as it would amplify the “local" success probability in the neighborhood of a node.

Hence, instead of running 𝒜 on C, we run it on a cycle of cliques C_1, which is obtained from C as follows. Each node v∈ C is replaced with a clique of size ≈ 2^|C|, denoted by D(v), where every two adjacent cliques are connected by a bi-clique (see also Figure 1, for an illustration). By running  on C_1 instead of C, it boosts the success probability of  in a small-radius neighborhood of any given node. As a result, a small-radius neighborhood of any node in C_1 must contain a node in the independent set. Using the independent set I_1 that was found in C_1, we can map it to an independent set I in C, as follows. Every v∈ C joins I if and only if I_1 contains a node in D(v). Due to the approximation guarantee of 𝒜 in C_1, we can prove that the maximum distance between two consecutive nodes in I_1 is small and therefore, the maximum length of a gap in I is small. Finally, we can run a greedy sequential  algorithm to fill the gap between every two consecutive nodes in I and find an  in C. Hence, if we can find an approximate- in C_1 in o(log^* |C_1|) rounds, then we can find an  in C in o(log^*(2^|C|))=o(log^*|C|) rounds, contradicting Naor's lower bound (Theorem <ref>). An illustration of the reduction with all the steps is provided in Figure 1 in Section <ref>. A detailed reduction is provided in Section <ref>, together with the full proof of the lower bound. 



§ PRELIMINARIES



Some of our proofs use the following standard probabilistic tools. An excellent source for the following concentration bounds is the book by Alon and Spencer <cit.>. These bounds can also be found in many lecture notes about basic tail and concentration bounds.

(Multiplicative Chernoff Bound).
	 Let X_1, ..., X_n be independent random variables taking values in {0, 1}. Let X denote their sum and let μ = E[X] denote the sum's expected value. Then for any 0≤ϵ≤ 1, it holds that: 
    Pr[|X - μ| ≥ϵμ] ≤ 2 exp(-ϵ^2/2+ϵμ)



(Bernstein's Inequality).
	Let X_1, ..., X_n be independent random variables such that ∀ i,  X_i≤ M. Let X denote their sum and let μ = E[X] denote the sum's expected value. Then for any positive t, it holds that: 
    Pr[|X - μ| ≥ t] ≤ 2 exp(-t^2/2/Mt/3+∑_i=1^nVar(X_i))


(One-sided Azuma's Inequality).
	Suppose {X_i: i=0,1,2,} is a martingale and that |X_i - X_i-1|≤ c_i almost surely. Then, for all positive integers N and all positive reals t,
	
	
    [X_N - X_0 ≤ -t] ≤exp(-t^2/2∑_i=1^N c_i^2)



In Section <ref> we show an improved approximation algorithm for a wide range of arboricity. We define the arboricity of a graph, which is denoted by α, as follows <cit.>.


	Given a graph G, Let m_H and n_H be the number of edges and nodes of a subgraph H of G, respectively. The arboricity of G is α=max_H⊆ G⌈m_H/n_H-1⌉.




  
Assumptions: In all of our upper and lower bounds, we don't assume that the nodes have any global information. In particular, they don't know n or Δ. The only information that each node has before the algorithm starts is its own identifier, and some polynomial upper bound on n (Since the nodes can send clog n bits in each round to each of their neighbors, naturally, they know some polynomial upper bound on n).



  
Some notations: The input graph is denoted by G_w=(V,E,w), where V is the set of nodes, E is the set of edges, and w is the weight function. The reason that we choose to add the weight function in a subscript is that some parts of the analysis deal with graphs that have the same sets of nodes and edges as the input graph, but a different weight function. Hence, such a graph will be denoted by G_w'=(V,E,w'), to indicate that it is the same as the input graph, but with weight function w' rather than w. 

We denote by N^+(v) the inclusive neighborhood of v, which consists of N(v)∪{v}, where N(v) is the set of neighbors of v. Furthermore, we denote by deg(v)=|N(v)| the number of neighbors of a node v. Finally, we denote by w(V') the total weight of nodes in V'⊆ V. That is, w(V')=∑_v∈ V' w(v). 





§ A (1+Ε)Δ-APPROXIMATION ALGORITHM


In this section we prove Theorems <ref> and <ref>.

thm:main
	

thm:Wmain
	

Theorems <ref> and <ref> share a similar proof structure. First, we present algorithms for O(Δ)-approximation in Sections <ref> and <ref>. Then, by using a general boosting theorem (Theorem <ref> in Section <ref>), we get (1+ϵ)Δ-approximation algorithms.



 §.§ An O((n,Δ))-Round Algorithm for O(Δ)-Approximation

In this section we show a very simple O((n,Δ))-round algorithm that finds an O(Δ)-approximation for .

	



  
Algorithm For every v∈ V, let δ(v) be the maximum degree of a node in the inclusive neighborhood of v. That is, δ(v)=max{deg(u)| u∈ N^+(v)}. A node v is called good if w(v)≥1/2(δ(v)+1)∑_u∈ N^+(v) w(u). The algorithm finds a maximal independent set I in the subgraph induced by the set of good nodes. We prove the following lemma.


	w(I)≥ w(V)/4(Δ+1)
	
		Let V_good be the set of good nodes, and let V=V∖ V_good. Observe that,
		
    ∑_v∈V w(v)≤∑_v∈V1/2(δ(v)+1)∑_u∈ N^+(v) w(u)≤∑_v∈ Vdeg(v)+1/2(deg(v)+1) w(v)= w(V)/2
    ⇒   ∑_v∈ I w(v)≥∑_v∈ I1/2(δ(v)+1)∑_u∈ N^+(v)w(u)≥∑_v∈ I1/2(Δ+1)∑_u∈ N^+(v)∩ V_goodw(u)
       ≥1/2(Δ+1)∑_v∈ V_goodw(v)≥ w(V)/4(Δ+1)

		as desired. Since the value of an optimal solution in G_w is at most w(V), the algorithm returns an O(Δ)-approximation for .
	




  
Success with high probability: Given a graph of n nodes, an algorithm that finds a maximal independent set in the graph with high probability is an algorithm that succeeds with probability at least 1-1/n^c for some constant c>1. In the algorithm above, the black box can be a randomized algorithm that is run on a subgraph H=(V_H,E_H) of G_w. Since n_H=|V_H| is potentially much smaller than n, one may wonder whether the algorithm above actually succeeds with high probability with respect to n. The main idea is to use an algorithm that is intended to work for graphs with n nodes, rather than n_H nodes. We prove the following lemma, whose proof is by a simple padding argument that is deferred to  Appendix <ref>.


	Let 𝒜 be an (n,Δ)-round algorithm that finds a maximal independent set with success probability p in a graph of n nodes and maximum degree Δ. Let H=(V_H,E_H) be a graph of n_H≤ n nodes with (clog n)-bit identifiers, for some constant c, and let Δ_H be the maximum degree in H. There is an O((n,Δ_H))-round algorithm 𝒜' that finds a maximal independent set in H with success probability p.
 










 §.§ A (loglog n)-Round Algorithm for O(Δ)-Approximation

In this section we show a (loglog n)-round algorithm that finds an O(Δ)-approximation.


	

Our algorithm has the following two-step structure. 



	
  * First, we sample a sparse subgraph H_w=(V_H,E_H,w) of G_w with the following two properties:
	
		
  * The maximum degree Δ_H of H_w is at most O(log n).
		
  * w(V_H)/Δ_H=Ω( w(V)/Δ). That is, the ratio between the total weigh and maximum degree in H_w is at least, up to a constant factor, as in G_w.
	 
	
  * Then, we use Theorem <ref> to find an independent set in H_w of size at least  w(V_H)/4(Δ_H+1)=w(V)/cΔ, for some constant c>1, in O((n,Δ_H))=O((n,log n))=(loglog n) rounds.
 






  
The first step: sampling a subgraph with the desired properties. Recall that w(N(v)) is the sum of weights of the neighbors of v, which we call the weighted degree of v. For each node v∈ V, let  w_max(v)=max{w(N(u))| u∈ N^+(v)}. It is useful to think about w_max(v) as the maximum weighted degree of a node in the inclusive neighborhood of v. We sample a subgraph H_w=(V_H,E_H,w), as follows. Let λ≥ 1 be a constant to be chosen later. Recall that δ(v) is the maximum degree of a node in the inclusive neighborhood of v. Each node v∈ V joins V_H with probability 
    p(v)=min{λlog n· (1/δ(v)+w(v)/w_max(v)),1}



In Lemma <ref>, we show that the maximum degree of H_w is Δ_H=O(log n). In Lemma <ref>, we show that w(V_H)=Ω(min{w(V),w(V)log n/Δ}).


The maximum degree Δ_H in H_w is O(log n), with high probability.


	Let V^+={v∈ V| p(v)≥ 1}. We show that each node u has at most O(log n) neighbors in V^+∩ V_H, and at most O(log n) neighbors in (V∖ V^+)∩ V_H. Let N_H(v) be the set of neighbors of v in H.
	
		
  * For every v∈ V, |N_H(v)∩ V^+|≤ 2λlog n:  Assume towards a contradiction that there are more than 2λlog n nodes in N_H(v)∩ V^+. Since each node v∈ V^+ has p(v)≥ 1. it holds that 
    ∑_u∈ N(v)∩ V^+ p(u)≥∑_u∈ N_H(v)∩ V^+p(u)> 2λlog n

		On the other hand, 
    ∑_u∈ N(v)∩ V^+ p(u)≤∑_u∈ N(v)p(u)=∑_u∈ N(v)λlog n· (1/δ(v)+w(v)/w_max(v))

		Since deg(v)=|N(v)| and w(N(v))=∑_u∈ N(v) w(u) are lower bounds on δ(v) and w_max(v), respectively, we have that 
    ∑_u∈ N(v)λlog n· (1/δ(u)+w(u)/w_max(u))≤∑_u∈ N(v)λlog n·(1/deg(v)+w(u)/w(N(v)))=2λlog n

		which is a contradiction.
		
  * |N_H(v)∩ (V∖ V^+)|≤ 2λlog n: Observe that the expected number of neighbors of v in N_H(v)∩ (V∖ V^+) is 
    ∑_u∈ N(v) p(u)≤ 2λlog n

		 Since |N_H(v)∩ (V∖ V^+)| is a sum of independent random variables, one can apply Chernoff's bound (Fact <ref>) to achieve that this number concentrates around its expectation with high probability.
	
	By applying a standard Union-Bound argument over all the nodes, we conclude that the maximum degree in H_w is Δ_H=O(log n) with high probability.



The rest of this section is devoted to the task of proving that w(V_H)=Ω(min{w(V),w(V)log n/Δ}). This is proved in Lemma <ref>. First, we start by proving a slightly weaker lemma, that assumes that for all v∈ V, p(v)≤ 1.


	Assume p(v)≤ 1, for all v∈ V. It holds that w(V_H)=Ω(w(V)log n/Δ), with high probability.




  
Main idea of the proof of Lemma <ref>: Let w_1≥ w_2≥...≥ w_n be a sorting of the weights of nodes in V in a decreasing order (where ties are broken arbitrarily). Let V_high={u∈ V| w(u)∈{w_1,...,w_Δ}}, and let V_low=V∖ V_high={u∈ V| w(u)∈{w_Δ+1,...,w_n}}. That is, V_high contains the Δ heaviest nodes, and V_low contains all the other nodes.  The proof is split into the following two cases that are proven separately in Claims <ref> and <ref>.

	
  * w(V_high)≥ w(V)/2: In this case, at least half of the total weight is distributed among high-weight nodes. Intuitively, we need to make sure that we get many of these high-weight nodes. Since the number of high-weight nodes that are sampled is a sum of independent random variables, we are able to use Chernoff's bound to prove that many of them are sampled, with high probability. The full proof for this case is presented in Claim <ref>.
	
  * w(V_low)≥ w(V)/2: In this case, at least half of the total weight is distributed among low-weight nodes. Therefore, it is sufficient to show that w(V_H)=Ω(w(V_low)log n/Δ). The key property here is that we can bound the maximum weight of a node in V_low by w(V)/Δ. We show how to use this property together with Bernstein's inequality to prove Lemma <ref> for this case. The full proof for this case is presented in Claim <ref>.



	Assume that for all v∈ V,  p(v)≤ 1. Let V_high={u∈ V| w(u)∈{w_1,...,w_Δ}}. If w(V_high)≥ w(V)/2, then w(V_H)=Ω(w(V)log n/Δ), with high probability.
	
		Let S={v∈ V_high| w(v)≥ w(V)/4Δ}. We start by showing that at least a constant fraction of the total weight in G_w is distributed among nodes in S. Let S=V_high∖ S, we start by showing that w(S)≤ w(V)/4: 
		
		
    w(S)≤∑_v∈S w(v)≤∑_v∈Sw(V)/4Δ≤w(V)/4

		
		
		where the last inequality holds because |S|≤ |V_high|=Δ. Therefore, w(S)=w(V_high∖S)= w(V_high)-w(V(S))≥ w(V)/4. Next, we show that |S∩ V_H|=Ω(log n), by using  Chernoff's bound. Let x_v be a {0,1} random variable indicating whether v∈ V_H, and let X=∑_v∈ Sx_v. We show that the expectation of X is at least clog n/4.  
    𝔼[X]   =∑_v∈ S𝔼[x_v]= ∑_v∈ Sp(v)=∑_v∈ Sλlog n· (1/δ(v)+w(v)/w_max(v))
       ≥∑_v∈ Sw(v)λlog n/w(V)≥λlog n/w(V)·∑_v∈ Sw(v)=w(S)λlog n/w(V)≥λlog n/4

		
		Furthermore, sine X is a sum of independent {0,1} random variables with expectation Ω(log n), by applying Chernoff's bound (Fact <ref>), we conclude that there are at least Ω(log n) nodes in S∩ V_H, with high probability. Since each node in S has weight at least w(V)/4Δ, this implies that the total weight in V_H is w(V_H)≥ w(S∩ V_H)= Ω(w(V)log n/Δ), with high probability, as desired.
	



	Assume that for all v∈ V,  p(v)≤ 1. Let V_low={v∈ V| w(v)∈{w_Δ+1,...,w_n}}. If w(V_low)≥ w(V)/2, then w(V_H∩ V_low)=Ω(w(V)log n/Δ), with high probability.
	
	 Let x_v be a {0,1} random variable indicating whether v∈ V_H, let y_v=x_v· w(v), and let Y=∑_v∈ V_lowy_v. We prove the following 3 properties:
	 
		
  * 𝔼(Y)≥w(V)λlog n/2Δ: this is because 
	 
		 
    𝔼[Y]   =∑_v∈ V_lowp(v)· w(v)=∑_v∈ V_lowλlog n· (1/δ(v)+w(v)/w_max(v))· w(v)
       ≥∑_v∈ V_loww(v)λlog n/Δ= w(V_low)λlog n/Δ≥w(V)λlog n/2Δ

	 
		 where the last equality holds since w(V_low)≥ w(V)/2. 
	 
	 
	 	
  * For any v∈ V_low, it holds that w(v)≤ w(V)/Δ: Recall that {w_1,⋯,w_n} is an ordering of the weight of nodes by a decreasing order. Hence, for any j, it holds that
	 	
    w_j· j≤∑_i=1^j w_j≤ w(V)

	 	
	 	where the first inequality holds because w_j is the minimum among {w_1,...,w_j}. Hence, since each node v∈ V_low has weigh w_j where j>Δ, we have that w(v)≤ w(V)/Δ for any v∈ V_low.
	 	
	 	
	 	
  * It holds that ∑_v∈ V_low𝔼[y_v^2]≤ w(V)·𝔼[Y]/Δ: First, observe that 
    ∑_v∈ V_low𝔼[y_v^2]≤max{w(v)| v∈ V_low}·∑_v∈ V_low𝔼[y_v]=max{w(v)| v∈ V_low}·𝔼[Y]
       ≤w(V)·𝔼[Y]/Δ

	 	where the last inequality holds by the second property.
	 	
 	
	 	By proving these three properties, we have satisfied all the prerequisites of Bernstein's inequality. A direct application of the inequality yields:
	 	
	 	
    Pr[|Y - 𝔼[Y]| ≥𝔼[Y]/2] ≤ 2 exp(-𝔼[Y]^2/8/M·𝔼[Y]/6+∑_v∈ V_lowVar(y_v))

		By the second and third properties, we have that
		
    ∑_v∈ V_lowVar(y_v)= ∑_v∈ V_low𝔼(y_v^2)-𝔼[y_v]^2≤∑_v∈ V_low𝔼(y_v^2)≤w(V)·E[Y]/Δ
    ⇒    Pr[|Y - 𝔼[Y]| ≥𝔼[Y]/2] ≤ 2 exp(-𝔼[Y]^2/8/w(V)·𝔼[Y]/6Δ+w(V)·𝔼[Y]/Δ)≤ 2 exp(-6Δ·𝔼[Y]/8/7w(V))

	 	
	 	
	 	
	 	Furthermore, by the first property, we have that 
    𝔼[Y]≥ w(V)λlog n/2Δ
    ⇒    2 exp(-6Δ·𝔼[Y]/8/7w(V))≤ 2 exp(-6 w(V)λlog n/56w(V))=2 exp(-6λlog n/56))
 
	 	
		
	 	
	 	 Finally, choosing λ=112/6 implies that:
	 	
	 	
    Pr[|Y - 𝔼[Y]| ≥𝔼[Y]/2]≤1/n^2log e<1/n^2

	 	
	 	as desired. Furthermore, we can boost the success probability to 1-1/n^k for any constant k>1, by setting λ=112k/3.
		
	


Having proved claims <ref> and <ref>, this finishes the proof of Lemma <ref>. Lemma <ref> makes the assumption that p(v)≤ 1 for all v∈ V. We remove this assumption in the proof of the following lemma. 


 It holds that w(V_H)=Ω(min{w(V),w(V)log n/Δ}), with high probability.
 
 	Let V^+={u∈ V| p(w)≥ 1}. The proof is split into two cases:
 	
 		
  * w(V^+)≥ w(V)/2: Since all the nodes in V^+ join V_H deterministically, this implies that w(V_H)≥ w(V^+)≥ w(V)/2.
 		
  * w(V^+)<w(V)/2: This implies that w(V∖ V^+)≥ w(V)/2. Since each node w∈ V∖ V^+ has p(w)<1, we can apply Lemma <ref> directly on the nodes in V∖ V^+ to conclude that w(V_H)=Ω(w(V∖ V^+)log n/Δ)=Ω(w(V)log n/Δ), with high probability, as desired.
 	
 


Now we are ready to finish the proof of Theorem <ref>.


	Since both Lemma <ref> and <ref> above hold with high probability, we can apply another standard Union-Bound argument to conclude that both of them hold with high probability (simultaneously). Hence, by running the algorithm from Section <ref> on H_w, we get an independent set of weight Ω(w(V_H)/Δ_H)=Ω(min{w(V),w(V)log n/Δ}/Δ_H)=Ω(w(V)/Δ), in (n,Δ_H)=(n,log n)=(loglog n) rounds, with high probability, as desired.





 §.§ Boosting for (1+ϵ)Δ-Approximation


In this section we prove the following theorem. 

	Let 𝒜 be a T-round algorithm that finds an independent set of weight at least (1/cΔ)-fraction of the total weight in the graph, in the CONGEST model. There is a (2Tc/ϵ)-round algorithm 𝒜' that finds a (1+ϵ)Δ-approximation for maximum-weight independent set in the CONGEST model.




  
Description of algorithm 𝒜':
Our algorithm consists of two stages. In the first stage we iteratively call algorithm 𝒜, which returns an independent set, and perform weight reductions based on the independent set. Then, we push all nodes in the independent set onto a stack. The next time we invoke 𝒜 in the first stage, it is invoked on the graph with the reduced weight. In the second stage we iteratively pop the independent sets from the stack and greedily construct another independent set which we return as the solution.
𝒜' is formally given in Algorithm <ref>. We continue with a formal description of our algorithm.

Let t=c/ϵ. As stated before, there are two stages in 𝒜', each consists of t phases. 


  
First Stage: For i=1 to t phases, in each phase, we first run algorithm 𝒜 to find an independent set I_i in G_w_i, where w_1=w, and G_w_1=G_w=(V,E,w) is the original input graph. Then, we insert the nodes in I_i to a stack S that is initially defined to be empty, and continue to G_w_i+1=(V,E,w_i+1), where w_i+1 is defined as follows. For each v∈ V,

    w_i+1(v)=
    0     v∈ I_i
    
    w_i(v)-∑_u∈ N(v)∩ I_iw_i(u)


That is, w_i+1 is a weight function which results from weight reductions to w_i, as follows. For each v∈ I_i, we reduce its total current weight, w_i(v), and therefore its weight becomes zero. For each v∉ I_i, we reduce its current weight, w_i(v), by the total weight of its neighboring nodes in I_i. This concludes the first stage. Before we proceed to the second stage, let us define the following weight functions w'_i, for every i∈ [t], that are used in the analysis. For each v∈ V,

    w'_i(v)=w_i(v)-w_i+1(v)

Hence, w'_i(v) is the reduced weight from v at the end of phase i. We define another weight function w', which is the total reduced weight function. For each v∈ V,

    w'(v)=∑_i=1^t w'_i(v)




  
Second Stage: We construct an independent set I as follows. For i=0 to t-1 phases, we pop out I_t-i from the stack, and insert each v∈ I_t-i to I unless I already contains a neighbor of v. 

In Lemma <ref>, we prove that I is a (1+ϵ)Δ-approximation for maximum-weight independent set for G_w. First, let us start with the following helper propositions. Recall that given a weight function ŵ we denote by G_ŵ=(V,E,ŵ) the same graph as the input graph G_w but with weight function ŵ rather than w. For every set of nodes, V' ⊆ V, we define ŵ(V')=∑_v∈ V'ŵ(v).


	I_i is a Δ-approximation for maximum-weight independent set in G_w'_i.


	First, observe that for every v∈ I_i, it holds that w'_i(v)=w_i(v)-w_i+1(v)=w_i(v), and for every v∉ I_i, it holds that w'_i(v)=w'_i(N(v)∩ I_i).
	
	
	
	
	Let I^*_i be an optimal maximum-weight independent set in G_w'_i. We can assume that I^*_i contains only nodes in I_i∪ N(I_i), as all the other nodes in G_w'_i have zero weight[Recall that N(I_i) denotes the set of neighbors of all nodes in I_i.]. We have that,
	
    w'_i(I^*_i)= w'_i(I^*_i∩ I_i)+ w'_i(I^*_i∖ I_i) = w'_i(I^*_i∩ I_i)+∑_v∈ I^*_i∖ I_i w'_i(N(v)∩ I_i)
       = w'_i(I^*_i∩ I_i) + Δ w'_i(I_i∖ I^*_i) ≤Δ w'_i(I_i)

	as desired.

In the following proposition we draw a connection between w(I), the final value of our solution, and the total value stored in our stack. Formally, we show the following.


	It holds that w(I)≥∑_i=1^t w'_i(I_i)=∑_i=1^t w_i(I_i).
	
		We assume without loss of generality that 𝒜 never picks nodes of non-positive weight to the independent set, as we can always remove them and increase the size of the solution. 
		
		Observe that for every v∈ I, it holds that v∈ I_i for some i∈ [t]. Let i_v be the phase for which v∈ I_i_v. It holds that,
		
    w(v)=w_i_v(v)+∑_i=1^i_v-1 w_i(N(v)∩ I_i) = w_i_v(v) + ∑_ u∈(N(v)∩(⋃_i=1^i_v-1I_i)) w_i_u(u)

		The first equality is because the weight of v at phase i_v was positive, as otherwise it wouldn't be in I_i_v, and, until phase i_v, the total amount of weight that was reduced from v is ∑_i=1^i_v-1 w_i(N(v)∩ I_i). And the second equality is because for every u which contributes to the sum ∑_i=1^i_v-1 w_i(N(v)∩ I_i), its contribution is exactly w_i_u(u).
		Hence, we have that,
		
    w(I)   =∑_v∈ I(w_i_v(v)+∑_i=1^i_v-1  w_i(N(v)∩ I_i)) =(∑_v∈ I w_i_v(v))+(∑_v∈ I∑_ u∈(N(v)∩(⋃_i=1^i_v-1 I_i)) w_i_u(u))
       ≥(∑_v∈ I w_i_v(v))+(∑_ u∈(⋃_i=1^t I_i)∖ I w_i_u(u))=∑_i=1^t w_i(I_i)

		where the last inequality holds because for every u∈ (∪_i=1^t I_i)∖ I, there is at least one neighbor v of u in I, with i_v>i_u. 
		Finally, since for every i∈ [t] and for every v∈ I_i, w'_i(v)=w_i(v), the claim follows.
	

Now we are ready to show that I is a (1+ϵ)Δ-approximation for maximum-weight independent set in the original input graph G_w.

	I is a (1+ϵ)Δ-approximation for maximum-weight independent set in G_w.
	
		Let OPT(G_w) be the value of an optimal solution in G_w. The proof is by the following case analysis.
		
			
  * w_t(V)≤ϵ/1+ϵOPT(G_w):

			Recall that for all v∈ V, w'(v)=∑_i=1^tw'_i(v). First, observe that,
			
    w'(V)   ≥∑_v∈ V∑_i=1^t-1w'_i(v)=∑_v∈ V∑_i=1^t-1w_i(v)-w_i+1(v)
       =∑_v∈ V w_1(v)-w_2(v)+w_2(v)-w_3(v)+⋯ -w_t-1(v)+w_t-1(v)-w_t(v)
       = w(V)- w_t(V) ≥ w(V)-ϵ/1+ϵOPT(G_w)

			Therefore, the value of an optimal solution in G_w' cannot be very small compared to the value of an optimal solution in G_w. Namely, OPT(G_w')≥ (1-ϵ/1+ϵ)OPT(G_w) = OPT(G_w) / (1+ϵ).
			
			
			
			Finally, by Propositions <ref>, I_i is a Δ-approximation to OPT(G_w'_i), and by Proposition <ref>, we have that,
			
			
    w(I)≥∑_i=1^t w'_i(I_i)≥∑_i=1^t OPT(G_w'_i)/Δ≥OPT(G_w')/Δ≥OPT(G_w) /(1+ϵ)Δ
 
			
			as desired.
			
  * w_t(V)≥ϵ/1+ϵOPT(G_w):

			Observe that for any i<t, it holds that w_i(V)≥ w_t(V).
			Therefore, since 𝒜 returns an independent set of weight at least (1/cΔ)-fraction of the total weight in the graph, for each phase i∈ [t], it holds that w_i(I_i)≥ϵ/(1+ϵ)cΔOPT(G_w), which implies:
			
    ∑_i=1^t w_i(I_i)≥ tϵ/(1+ϵ)cΔOPT(G_w)=1/(1+ϵ)ΔOPT(G_w)

			Finally, by Proposition <ref>, we have that w(I)≥∑_i=1^t  w_i(I_i)≥1/(1+ϵ)ΔOPT(G_w). Which completes the proof.
			
			
			
			
			
		    
	





  
Remark:
One can show that the same algorithm also returns an independent set of weight at least w(V)/(1+ϵ)(Δ+1), which is sometimes better than (1+ϵ)Δ-approximation, and sometimes worse. The proof of this argument similar to the proof above. The only difference is that the case analysis in Lemma <ref> is with respect to ϵ/1+ϵw(V). That is, the first case is in which w_t(V)≤ϵ/1+ϵw(V), and the second case is in which w_t(V)≥ϵ/1+ϵw(V). It is straightforward to show that in both cases I is of weight at least w(V)/(1+ϵ)(Δ+1), by using the stack property (Proposition <ref>).


		Let 𝒜 be a T-round algorithm that finds an independent set of weight at least (1/cΔ)-fraction of the total weight in the graph, in the CONGEST model. There is a (2Tc/ϵ)-round algorithm 𝒜' that finds an independent set I of weight at least w(V)/(1+ϵ)(Δ+1) in the CONGEST model.






§ FASTER ALGORITHM FOR LOW-DEGREE GRAPHS


In this section we show that there is an O(1)-round algorithm that finds an independent set of size  Ω(n/Δ) for graphs in which Δ≤ n/log n. Using the boosting theorem that is presented in the previous section (in particular, Corollary <ref>), this implies that there is an O(1/ϵ)-round algorithm that finds an independent set of size at least n/(1+ϵ)(Δ+1) in unweighted graphs of maximum degree Δ≤ n/log n, proving Theorem <ref>.

The algorithm is based on a new analysis of one round of the classical ranking algorithm for independent set, which is (to the best of our knowledge) due to Boppanna. This classical algorithm finds an independent set in a graph by independently selecting a rank for each vertex and including a vertex in the output independent set if its rank is greater than the ranks of its neighbors (Algorithm <ref>).



In discussion, notice that  can be implemented in O(c) rounds in the CONGEST model. We analyze this algorithm by considering a sequential view. The independent set I returned by the algorithm only depends on the order of the r_vs. We could run  instead by picking a uniformly random permutation of the vertices and include a vertex v in I if no neighbor of v has a higher rank in the permutation. Furthermore, we can sample the permutation by repeatedly selecting uniformly random vertices without replacement. Equivalently, sample a permutation by repeatedly selecting vertices with replacement, but reject samples seen before (Algorithm <ref>).



To analyze (G), it suffices to analyze (G):


	For any unweighted graph G and constant c > 0, (G) produces a distribution over sets I with total variation distance at most 1/n^c from the distribution produced by (G); in particular
	
	
    ∑_sets  I_0 |_I∼(G)[I = I_0] - _I∼(G)[I = I_0]|≤ 1/n^c




	Let n = |V| and 𝒟_0 be the uniform distribution over {1,2,,100n^c+2}^n. This is the distribution over rank tuples (r_u)_u∈ V used by algorithm . Let 𝒟_1 be the uniform distribution over tuples in {1,2,,n}^n with distinct coordinates. Let _1 denote the algorithm with the tuple (r_u)_u∈ V sampled from 𝒟_1 instead of 𝒟_0:
	
	
	
	By a union bound over all pairs of vertices, r_u r_v for all u,v∈ V(G) with probability at least 1 - n21/100n^c+2 > 1 - 1/(2n^c). Let E denote the event {r_u r_v ∀ u,v∈ V(G)} and let E denote the negation. Conditioned on r_u r_v for all u,v∈ V(G), the output of  is identically distributed to the output of _1. Therefore,
	
	
    ∑_sets  I_0 |_I∼(G)[I = I_0] - _I∼_1(G)[I = I_0]|
       =∑_sets  I_0 |_I∼(G)[I = I_0] - _I∼(G)[I = I_0 | E]|
       =∑_sets  I_0 |[I = I_0 | E][E] + [I = I_0 &E] - [I = I_0 | E]|
       ≤∑_sets  I_0 ([I = I_0 | E][E] + [I = I_0 &E])
       = 2[E]
       ≤ 1/n^c

	so the total variation distance between the output distributions of  and _1 is at most 1/n^c. Next, we show that _1(G) produces the same distribution over sets as the following algorithm, _0(G):
	
	
	Since the u_rs are selected without replacement from V, the distribution over tuples (u_n,u_n-1,,u_1) is a uniform distribution over permutations of V. Let ℛ⊆{1,2,,n}^n and 𝒰⊆ V^n denote the families of {1,2,,n} and V-tuples with distinct coordinates respectively. Fix an ordering v_1,v_2,,v_n of vertices in G and let τ: ℛ→𝒰 be the map
	
	
    τ(r_1,r_2,,r_n-1,r_n) = (v_r_1,v_r_2,,v_r_n-1,v_r_n)

	τ is a bijection. Furthermore, for any tuple r∈ℛ, _1(G) with v_i-rank r_i outputs the same set S as _0(G) with vertex ordering u = τ(r). Therefore, _1(G) outputs the same distribution over sets as _0(G).
	
	Finally, _0(G) produces the same distribution over sets as (G), because the permutation can be sampled with replacement and rejection of previous samples (as in ) rather than without replacement (as in _0). Therefore, (G) and  (G) produce distributions over sets S with total variation distance at most 1/n^c, as desired.


To lower bound the size of the independent set produced by (G), we use an exposure martingale. We start by stopping the  algorithm early: we only consider the first k = n/(2(Δ+1)) iterations. Each iteration samples 1 vertex, which precludes at most Δ other vertices from joining the independent set in the future. Therefore, after k iterations, a randomly sampled vertex has a probability of at least n - (Δ+1) k/n≥ 1/2 of still being able to join the independent set. Thus, I has size at least (1/2)(n/2(Δ+1)) = n/8(Δ+1) in expectation. To obtain a high-probability lower bound on the size of I, we use the following proposition, which we prove using Azuma's Inequality:


	Consider a set 𝒳, a distribution 𝒟 over 𝒳, a collection X_1,X_2,,X_k of independent, identically distributed random variables sampled from 𝒟, and a collection of functions f_1,f_2,,f_k, where f_i: 𝒳^i→ℝ. Suppose that there are numbers M_0,M_1 > 0 such that for all i∈{1,2,,k-1} and all tuples x_1,x_2,,x_i∈𝒳, the following conditions hold:
	
	
		
  * (Max change) |f_i+1(x_1,x_2,,x) - f_i(x_1,x_2,,x_i)|≤ M_0 and |f_1(x)|≤ M_0 for all x∈𝒳
		
		
  * (Expected increase) 𝔼_X∼𝒟 [f_i+1(x_1,x_2,,x_i,X)] ≥ M_1 + f_i(x_1,x_2,,x_i) and 𝔼_X∼𝒟 [f_1(X)] ≥ M_1.
	
	Then
	
	
    [f_k(X_1,X_2,,X_k) < k M_1 - t] ≤exp(-t^2/8M_0^2 k)




	Set up a martingale {Y_i: i=0,1,,k} based on the sequence of function values. Let Y_0 = 0 and for all i ∈{1,2,,k}, let
	
	
    Y_i    = f_i(X_1,X_2,,X_i) - 𝔼[f_i(X_1,X_2,,X_i) | X_1,,X_i-1] + Y_i-1

	For all integers i≥ 1, 𝔼[Y_i | X_1,,X_i-1] = Y_i-1, so the Y_is are a martingale. Let f_0 denote the constant function f_0 = 0. By the Max change condition,
	
	
    |Y_i - Y_i-1|    = |f_i(X_1,X_2,,X_i-1,X_i) - 𝔼[f_i(X_1,X_2,,X_i-1,X_i) | X_1,,X_i-1]|
       ≤max_a,b∈𝒳 |f_i(X_1,X_2,,X_i-1,a) - f_i(X_1,X_2,,X_i-1,b)|
       ≤max_a,b∈𝒳 (|f_i(X_1,X_2,,X_i-1,a) - f_i-1(X_1,,X_i-1)|
       + |f_i-1(X_1,,X_i-1) - f_i(X_1,X_2,,X_i-1,b)|)
       ≤ 2M_0

	Therefore, by Fact <ref>,
	
	
    [Y_k < -t] ≤exp(-t^2/8kM_0^2)

	By the Expected increase condition, for all integers i≥ 1,
	
	
    Y_i    = f_i(X_1,X_2,,X_i) - 𝔼[f_i(X_1,X_2,,X_i) | X_1,,X_i-1] + Y_i-1
       = f_i(X_1,X_2,,X_i) - f_i-1(X_1,,X_i-1)
       + f_i-1(X_1,,X_i-1) - 𝔼[f_i(X_1,X_2,,X_i) | X_1,,X_i-1] + Y_i-1
       ≤ f_i(X_1,X_2,,X_i) - f_i-1(X_1,,X_i-1) - M_1 + Y_i-1

	As a result,
	
	
    Y_k≤ f_k(X_1,,X_k) - kM_1

	which means that
	
	
    [f_k(X_1,,X_k) < kM_1 - t] ≤[Y_k < -t] ≤exp(-t^2/8kM_0^2)

	as desired.


We now prove our main result by letting f_i denote the size of the independent set after i iterations of :


	For any c > 1, there is an (c)-round CONGEST algorithm (G) that, given a parameter p ∈ (0,1) and an n-vertex graph G with max degree Δ≤ n/(256 log(1/p)) - 1, returns an independent set I for which |I| ≥ n/(8(Δ + 1)) with probability at least 1 - p - 1/n^c.



	(G) is an O(c)-round algorithm in the CONGEST model. Furthermore, the set I returned is an independent set because each vertex v∈ I has a strictly higher rank r_v than its neighbors, which is not simultaneously possible for two adjacent vertices. Therefore, to prove the theorem, we just need to lower bound the size of the set I returned by (G). By Proposition <ref>, it suffices to show that the set I returned by (G) has size at least n/(8(Δ + 1)) with probability at least 1 - p.
	
	To lower bound the size of I, we apply Proposition <ref> with the following parameter settings:
	
	
		
  * k = n/(2(Δ+1))
		
  * 𝒳 = V(G)
		
  * 𝒟: the uniform distribution over 𝒳
		
  * X_i: the vertex u sampled during the ith iteration of the while loop in (G).
		
  * f_i(x_1,x_2,,x_i): the function that maps a set of vertices x_1,,x_i to |I_i|, where I_i is the set I between the i and (i+1)th iterations of the while loop of (G) with u being x_j in the jth while loop iteration.
		
  * M_0 = 1
		
  * M_1 = 1/2
		
  * t = k/4
	
	We now check the conditions of Proposition <ref> with each of these parameters. The Max change condition follows immediately from the fact that I_i+1 = I_i or I_i+1 = I_i∪{X_i+1} for all i≥ 1 and the fact that |I_1|≤ 1, so we focus on the Expected increase condition. Consider a set of choices x_1,x_2,,x_i of the first i while loop vertices u and let V_i = {x_1,x_2,,x_i} for all i∈{0,1,,k}. Let X be a random variable denoting the (i+1)th vertex u selected by the while loop from U. X is uniformly chosen from V. By the if statement of the  algorithm, X is added to I if and only if X is not equal to or adjacent to any vertex in V_i. There are at most (Δ + 1)|V_i| such vertices, so
	
	
    _X∼𝒟[f_i+1(x_1,x_2,,x_i,X)  f_i(x_1,,x_i)] ≥ 1 - (Δ + 1)|V_i|/n

	Since i≤ k≤ n/(2(Δ + 1)) and |V_i| = i, _X∼𝒟[f_i+1(x_1,x_2,,x_i,X)  f_i(x_1,,x_i)] ≥ 1/2 for all i∈{0,1,,k-1}. Furthermore,
	
	
    𝔼_X∼𝒟 [f_i+1(x_1,x_2,,x_i,X)]    = [f_i+1(x_1,x_2,,x_i,X)  f_i(x_1,,x_i)] + f_i(x_1,x_2,,x_i)
       ≥ 1/2 + f_i(x_1,x_2,,x_i)

	
	Plugging in our lower bound on the probability shows that the Expected increase condition is satisfied. Therefore, Proposition <ref> applies and shows that
	
	
    [|I_k| < k/4] ≤exp(-(k/4)^2/8k) = exp(-k/128)

	In particular, since |I| ≥ |I_k|,
	
	
    [|I| < n/(8(Δ + 1))] ≤exp(-n/(256(Δ + 1))) ≤ p

	Therefore, the independent set I returned by  has the desired size with probability at least 1 - p, as desired.




§ AN IMPROVED APPROXIMATION FOR LOW-ARBORICITY GRAPHS


In this section we prove the following theorem. Recall that α is the arboricity of the input graph (see also Definition <ref>). Theorem <ref> is a corollary of Theorems <ref> and <ref>.

	Let 𝒜 be a T-round algorithm that finds a (1+ϵ)Δ-approximation for maximum-weight independent set in the CONGEST model. There is an O(Tlog n)-round algorithm 𝒜' that finds a 8(1+ϵ)α-approximation for maximum-weight independent set in the CONGEST model.




  
Description of algorithm 𝒜': 𝒜' is formally given in Algorithm <ref>.
The algorithm is similar to Algorithm <ref> that was presented in Section <ref>. The main difference is that we run 𝒜 on subgraphs of maximum degree 4α, rather than on the input graph, which has maximum degree Δ. We do this to ensure that the approximation factor we get is not too far from 4α(1+ϵ).
𝒜' is formally given in Algorithm <ref>. There are two stages, each consists of log n+1 phases. 


  
First Stage: Let V^4α_i be the set of nodes of degree at most 4α in G^i_w_i, where G^1_w_1=(V_1,E_1,w_1)=(V,E,w) is the original input graph, and for i>1, G^i_w_i will be defined shortly. For i=1 to log n+1 phases, in each phase, we run algorithm 𝒜 on the subgraph induced by the nodes in V^4α_i and insert the resulting independent set I_i into a stack S, that is initially empty. We then continue to the graph G^i+1_w_i+1=(V_i+1,E_i+1,w_i+1), that is defined as follows. Let w_1=w be the original input weight function. We begin with defining w_i+1.


    w_i+1(v)=
    0     v∈ V^4α_i
    
    w_i(v)-∑_u∈ N(v)∩ I_iw_i(u)


Unlike the algorithm presented in Section <ref>, we reduce the total current weight, w_i(v), from every v∈ V^4α_i, and not only from the nodes in I_i. For every node v∉ V^4α_i, we reduce the total weight of the neighboring nodes in I_i. Similarly to Section <ref>, we define the following reduced weight function w'_i(v)=w_i(v)-w_i+1(v), for any i. 





The idea behind the definition of w_i and w'_i is that I_i is a good approximation, as to be shown later, to the graph G^i_w'_i=(V_i,E_i,w'_i), which is the same graph as G^i_w_i but with weight function w'_i rather than w_i. Therefore, I_1 is a good approximation to the graph G^1_w'_1, which is the same graph as the input graph G_w, but with weight function w'_1 rather than w. Hence, intuitively, after finding I_1, we just need to find an independent set I'  that is a good approximation to the graph (V,E,w-w'_1), and incorporate the two independent sets I_1 and I' together to construct an independent set I that is a good approximation to the original input graph G=(V,E,w). The main issue with applying this approach recursively on G_w_2=(V,E,w-w'_1) is that the set of nodes is the same as the set of nodes of G_w, and therefore, the set of nodes of maximum degree 4α in G_w_2 is the same as in G_w, which implies that we don't make any progress by running 𝒜 again on the same set of nodes. Therefore, in order to guarantee that our algorithm makes progress, we run 𝒜 on G^2_w_2=(V_2,E_2,w_2)=(V_2,E_2,w-w'_1), where we keep in V_2 only nodes of positive weight in w_2. Since we can assume without loss of generality that 𝒜 never picks nodes of non-positive weight, we can keep only the nodes of positive weight in V_2. Furthermore, by keeping the nodes of positive weight in V_2, we ensure that every v∈ V^4α_1 is not in V_2, and therefore our algorithm makes progress by running 𝒜 again on the set of nodes of maximum degree 4α in G^2_w_2, which is denoted by V^4α_2, which is necessarily different than V^4α_1. Hence, we define V_i+1 and E_i+1 as follows.


    V_i+1={v∈ V_i| w_i+1(v)>0}
       E_i+1={{u,v}∈ E| u,v∈ V_i+1}


This concludes the first stage.



  
Second Stage: We construct an independent set I as follows. For i=0 to log n phases, we pop out I_log n+1-i from the stack, and insert each v∈ I_log n+1-i to I unless I already contains a neighbor of v. 

In Lemma <ref>, we prove that I is a 8(1+ϵ)α-approximation for maximum-weight independent set in the original input graph G_w. We start with the following helper propositions.


	For any i≥ 2, it holds that |V_i+1|≤ |V_i|/2.
	
		Since the arboricity of G is α, it holds that for any subgraph H=(V',E')⊆ G there are at least |V'|/2 nodes of degree at most 4α. Hence, for any i≥ 1, it holds that |V_i^4α|≥ |V_i|/2. Since all the nodes in V_i^4α have zero weight in w_i+1, and V_i+1={v∈ V_i| w_i+1(v)>0}, the claim follows.
	


	
			I_i is a 8α(1+ϵ)-approximation for maximum-weight independent set in G^i_w'_i
		
		
			First, observe that, for every v∈ V^4α_i, w'_i(v)=w_i(v), and for every v∈ V_i∖  V^4α_i, w'_i(v)= ∑_u∈ N(v)∩ I_i w_i(u). In total, we have that,
			
    w_i'(V_i)= w'_i(V^4α_i)+ w_i'(V_i∖ V^4α_i)
    			= w'_i(V^4α_i)+∑_v∈ V_i∖ V^4α_i w'_i(N(v)∩ I_i)
    			≤ w'_i(V^4α_i)+ 4α w'_i(I_i)

			where the last  inequality holds because each node in I_i has at most 4α neighbors in V_i, and w_i(v)=w'_i(v), for any v∈ I_i. 
			Let G^4α_w'_i=(V_i^4α,E(V_i^4α),w'_i) be the subgraph of G^i_w'_i induced by the nodes in V^4α_i with weight function w'_i. Let OPT(G^4α_w'_i) be the value of an optimal solution in G^4α_w'_i. Recall that G^i_w'_i=(V_i,E_i,w'_i). Observe that since w'_i(V_i)≤ w'_i(V^4α_i)+4α  w'_i(I_i), 
			
			
			
			it follows that 
			
    OPT(G^i_w'_i)≤ OPT(G^4α_w'_i)+4α w'_i(I_i)
       ⇒OPT(G^i_w'_i)-OPT(G^4α_w'_i)/4α≤ w'_i(I_i)

			
			Finally, since 𝒜 is a (1+ϵ)Δ-approximation algorithm, and since the maximum degree of G^4α_w'_i=G^4α_w_i is at most 4α, it holds that I_i is a 4(1+ϵ)α-approximation for G^4α_w'_i. Hence,
			
    w'_i(I_i)≥OPT(G^i_w'_i)-OPT(G^4α_w'_i)/4α
       ⇒ 2 w'_i(I_i)≥OPT(G^i_w'_i)-OPT(G^4α_w'_i)+OPT(G^4α_w'_i)/4α(1+ϵ)
       ⇒ w'_i(I_i)≥OPT(G^i_w'_i)/8(1+ϵ)α

			As desired. 
		

	I is a 8(1+ϵ)α-approximation to OPT(G_w).
	
		First, by Proposition <ref>, V_log n+2=∅. Therefore, for every v∈ V, there is a phase i_v∈ [log n+1] for which v∈⋃_i=1^i_vV_i and v∉ V_i_v+1. Hence,
		
    w(v)=∑_i=1^i_vw'_i(v)=∑_i∈ [log n+1]: i∈ V_i w'_i(v)

		In total, we have that, w(V)=∑_v∈ V∑_i∈ [log n+1]: i∈ V_i w'_i(v)=∑_i=1^log n+1 w'_i(V_i).
		
		
		
		Observe that the second stage in Algorithm <ref> is identical to the second stage of Algorithm <ref>. Therefore, we can apply Proposition <ref> from Section <ref> to argue that w(I)≥∑_i=1^log n+1w'_i(I_i).
		
		
		
		Hence, 
		
    w(I)≥∑_i=1^log n+1w'_i(I_i)
    		≥∑_i=1^log n+1OPT(G^i_w'_i)/8(1+ϵ)α≥OPT(G_w)/8(1+ϵ)α

		as desired, where the second inequality follows by Proposition <ref>.
		

	


§ LOWER BOUND


In this section, we prove Theorem <ref>. We do this by a reduction to Naor's <cit.> lower bound (Theorem <ref>). Our reduction is described by the following lemma:


	Suppose that there exists a T(n)-round algorithm (G) in the LOCAL model that outputs an independent set containing at least n/(cΔ) vertices in an n-vertex graph G with probability at least 1 - p(n), where p is a decreasing function. Then, for any integer n_1, there is an O(cT(n_0n_1))-round algorithm (C) in the LOCAL model that outputs a maximal independent set of an n_0-vertex cycle graph C with probability at least 1 - n_0 p(n_1) as long as n_1≥ n_0.






Let C be a cycle graph of n_0 nodes. Algorithm (C) runs 𝒜 on a graph C_1 which is a cycle of cliques, and will be formally defined shortly. After 𝒜 finds an independent set of size n/cΔ in C_1, it uses the resulting independent set to find a maximal independent set in C. We now formally define the graph C_1. For an n_0-vertex cycle C consisting of vertices u_1,u_2,,u_n_0 in that order, let C_1 be a graph on n_0n_1 vertices {{v_ij}_j=1^n_1}_i=1^n_0. There is an edge between two vertices v_ij,v_i'j' in C_1 if and only if |i' - i|≤ 1 or i' = n_0 and i = 1. The ID of a vertex v_ij in C_1 is the concatenation of the ID for u_i in C and the number j. Notice that these IDs have length at most log (n_0n_1). C_1 is a cycle of cliques, with a biclique between two adjacent cliques. This graph is depicted in Figure 1.



(C) starts by computing an independent set I_1 using (C_1). This randomized LOCAL algorithm can be implemented in the LOCAL model on C, with each vertex u_i simulating all of the actions performed by (C_1) on the vertices {v_ij}_j=1^n_1. The set I_1 maps to an independent set I in C since each u_i maps to a clique in C_1. Because the T(n_0n_1)-neighborhood of each vertex in C_1 is a ≥ n_1-vertex graph and the algorithm  is distributed, a O(T(n_0n_1))-neighborhood of a vertex in C must contain a vertex in I with probability at least 1 - p(n_1). By a union bound over all cliques in C_1, the distance between any two consecutive vertices in I along the cycle is at most O(T(n_0n_1)) with probability at least 1 - n_0 p(n_1). Therefore, all connected components of C∖ I have size at most O(T(n_0n_1)), so sequentially finding a maximal independent set in each component simultaneously takes O(T(n_0n_1)) time to extend I to an MIS for C.

In the proof of Lemma <ref>, we crucially exploit two properties of the algorithm  that follow from its correctness:


	
  *  is globally consistent in the sense that (G) returns an independent set of G with high probability (see Proposition <ref>).
	
  *  is locally present in the sense that a O(cT(n_0n_1))-neighborhood of any vertex intersects (C_1) with high probability (see Proposition <ref>).


Notice that the second property does not hold for one round of Boppanna's algorithm and that the first property does not hold for a o(log^* n)-time greedy algorithm.

We now implement the algorithm , which (1) calls  on C_1, (2) maps the found independent set back to C and (3) finds a maximal independent set in the connected components between consecutive independent set vertices:



We start by showing the correctness of the algorithm.


	(C) outputs a maximal independent set of the n_0-vertex cycle graph C with probability at least 1 - p(n_1).



	By definition of the algorithm , I_1 is an independent set of C_1 with probability at least 1 - p(n_0n_1)≥ 1 - p(n_1). For the rest of the proof, assume that I_1 is an independent set C_1 (the complement happens with probability at most p(n_1)). We now show that I is an independent set. Suppose, instead, that there exist adjacent u_i,u_i+1∈ I. By definition of I, there exist vertices v_ij,v_(i+1)j'∈ I_1. By construction of C_1, v_ij and v_(i+1)j' are adjacent vertices in C_1, a contradiction to the fact that I_1 is an independent set in C_1. Therefore, I must be an independent set in C.
	
	No vertices in C_2 are adjacent to vertices in I within C by definition of C_2. Therefore, S is an independent set in C. Furthermore, each vertex in J is adjacent to a vertex in I, while each vertex in V(C)∖ J is adjacent to a vertex in the maximal independent set computed for C_2. Therefore, S is also maximal at the end of the algorithm. Therefore, S is a maximal independent set if I is an independent set, which happens with probability at least 1 - p(n_1), as desired.


The rest of the analysis focuses on the runtime. To bound the runtime, we need to exploit the fact that  is a distributed algorithm to show that the independent set returned has small gaps with high probability. This is shown by using the fact that , in the neighborhood of a vertex v, cannot distinguish between C_1 and an O(T(n_0n_1))-length cycle of cliques containing v. We formalize this in Proposition <ref>. Let R_large = (100c + 1)T(n_0n_1) + 2 and R_small = 100cT(n_0n_1). Let L_v denote the set of vertices u∈ V(C_1) for which the distance from u to v is at most R_large. Let S_v denote the set of vertices u∈ V(C_1) for which the distance from u to v is at most R_small. Let C_v denote the induced subgraph of C_1 with respect to the set of vertices L_v. Recall that  is a randomized algorithm that outputs a distribution over sets of vertices in the input graph. We now show the following property of this distribution:


	For any vertex v∈ V(C_1), S_v∩(C_1) has the same distribution as S_v∩(C_v).



	For any vertex u∈ V(C_1), let f_u(C_1) = 1_u∈(C_1); that is, the indicator function of u's presence in the independent set (C_1). Let U_u be the set of vertices in C_1 with distance at most T(n_0n_1) from u. Since  is a T(n_0n_1)-round algorithm in the LOCAL model, f_u is only a function of the randomness, IDs, and edges incident with vertices in U_u for any u∈ V(C_1). By definition of f_u,
	
	
    S_v∩(C_1) = {u∈ S_v: f_u(C_1) = 1}

	The set S_v∩(C_1) is therefore only a function of the randomness, IDs, and edges incident with vertices in ∪_u∈ S_v U_u. All of this information is contained in the graph C_v, since any vertex in the set ∪_u∈ S_v U_u is within distance R_small + T(n_0n_1) = R_large - 2 of v. Therefore, S_v∩(C_1) is only a function of randomness, IDs, and edges in the graph C_v, which means that S_v∩(C_1) is identically distributed to S_v∩(C_v), as desired.


As a result, to show that S_v contains a vertex of the independent set with high enough probability, it suffices to think about C_v instead of C_1. In this proposition, we exploit the fact that  returns an independent set with size at least n/(cΔ) on n-vertex graphs with maximum degree higher than Ω(n/log^* n):


	For any vertex v∈ V(C_1), S_v∩(C_1)∅ with probability at least 1 - p(n_1).



	By Proposition <ref>, S_v∩(C_v) is identically distributed to S_v∩(C_1), so it suffices to lower bound the probability that S_v∩(C_v) is empty. Let I_v := (C_v). The maximum degree of vertices in C_v is 3n_1. Furthermore, |V(C_v)| = (2R_large + 1)n_1 ≥ 200cT(n_0n_1)n_1. By the output guarantee of , I_v is an independent set and |I_v|≥ |V(C_v)|/(c (3n_1))≥ 60T(n_0n_1) with probability at least 1 - p(n_1). The vertices on V(C_v)∖ S_v are a union of 2(R_large - R_small) ≤ 4T(n_0n_1) cliques on n_1 vertices. Therefore, since I_v is an independent set, |I_v∩ (V(C_v)∖ S_v)|≤ 4T(n_0n_1). Therefore, |I_v∩ S_v| ≥ 60T(n_0n_1) - 4T(n_0n_1) > 0 with probability at least 1 - p(n_1), as desired.


Now, we union bound to prove the desired property for all intervals with width 2R_small:


	Let I be the output of (C_1). With probability at least 1 - n_0 p(n_1), S_v∩ I∅ for all v∈ V(C_1).



	By Proposition <ref> and a union bound over all i∈{1,2,,n_0}, S_v_i1∩ I∅ for all i∈{1,2,,n_0} with probability at least 1 - n_0 p(n_1). For any j∈{1,2,,n_1}, S_v_ij = S_v_i1. Since every vertex in C_1 is equal to v_ij for some i∈{1,2,,n_0} and j∈{1,2,,n_1}, S_v∩ I∅ for all v∈ V(C_1) with probability at least 1 - n_0 p(n_1), as desired.


We now prove a runtime bound:


	Given an n_0-vertex cycle graph C, (C) runs in O(T(n_0n_1)) time with probability at least 1 - n_0 p(n_1).



	We go through the  algorithm line by line. The call to (C_1) can be implemented in the LOCAL model on C as follows. Any T-round LOCAL algorithm can be viewed as independently flipping coins at each vertex and sending the IDs and randomness of a vertex u to each vertex v in its T-neighborhood, followed by no additional communication. This communication can be done in C by having u_i generate the randomness used by all v_ijs in (C_1). Then, u_i sends this randomness and the IDs of all v_ijs to each vertex in the T(n_0n_1)-neighborhood of u_i in C. Finally, the  algorithm's execution on v_ij can be run on u_i instead. Thus, the call to (C_1) takes at most T(n_0n_1) rounds.
	
	I, J, and C_2 can each be computed in at most two rounds. By Proposition <ref>, C_2 has connected components with size at most O(T(n_0n_1)) with probability at least 1 - n_0 p(n_1). Thus, for each connected component D of C_2, the vertices u∈ D can be sent D in O(T(n_0n_1)) rounds. With no futher communication, the vertices u∈ D each use the same algorithm to compute a maximal independent set of D. This completes all lines of the algorithm. Therefore, the algorithm takes O(T(n_0n_1)) time with probability at least 1 - n_0 p(n_1), as desired.



	Follows immediately from Propositions <ref> (S is an MIS) and <ref> (for runtime).


Given Lemma <ref>, we can now prove that any algorithm for approximate independent set that succeeds with arbitrarily high probability must take Ω(log^* n) rounds:


	For any constant b, any randomized o(log^* n)-time algorithm that computes an independent set with size greater than Ω(n/Δ) in an n-vertex graph succeeds with probability at most 1 - 1/(10log^(b) n), where log^(b)(x) is the function defined recursively as log^(0)(x) = x and log^(b)(x) = loglog^(b-1)(x). 



	Suppose, for the sake of contradiction, that there exists a LOCAL algorithm (G) that, when given an n-vertex graph G, takes o(log^* n) time and outputs an Ω(n/Δ)-vertex independent set of G with probability at least 1 - 1/(10log^(b) n). For some value of n_0, define n_1 as follows. Let n_1^(0) = n_0, let n_1^(i) = 2^n_1^(i-1) for all i > 0, and let n_1 = n_1^(b). By Lemma <ref>
	and the fact that n_1≥ n_0, there is an o(log^* (n_0n_1)) = o(b + log^* n_0) = o(log^* n_0)-round LOCAL algorithm (C) that, given an n_0-vertex cycle graph C, outputs a maximal independent set of C with probability at least 1 - n_0 (1/(10log^(b)(n_1))) = 9/10. The existence of such an algorithm contradicts Theorem <ref>, as desired.



Theorem <ref> is implied immediately by Theorem <ref> with b = 2.




§ DISCUSSION

There are many interesting open questions that are left unsolved following this work. The first obvious open question is to close the gap between our upper and lower bounds. Here, we provide some more open questions. First, we showed that in the randomized case, when we usually look for algorithms that succeed with high probability, finding an O(Δ)-approximation to MaxIS is strictly easier than MIS. An immediate interesting open question in whether the same holds for the deterministic case. The following is open for both the LOCAL and CONGEST models.


	Let T_α() be the running time of finding an α-approximation to  deterministically in the CONGEST model, and let T(MIS) be the running time of finding a maximal independent set in the CONGEST model. Prove or disprove that there is a constant c for which it holds that 
    T_cΔ()=o(T())



Another interesting implication of our result is the following one. Observe that in the sequential setting, one can find a (Δ+1)-approximation for  by finding a (Δ+1)-vertex-colouring. This is because we can simply take the colour class of maximum weight, which is a (Δ+1)-approximation for . However, in the distributed setting, it not clear how to use a colouring to find a good approximation for . This is because finding the colour class of maximum weight requires Ω(D) rounds, where D is the diameter of the network, which can be as large as n-1. 

Interestingly, our upper and lower bounds for O(Δ)-approximation for  match the best currently known upper and lower bounds for distributed (Δ+1)-colouring <cit.>. While this doesn't necessarily imply any connection between the two problems in the distributed setting, it might hint for a possible one. The following is open for both the LOCAL and CONGEST models.


	Prove or disprove: Given a T rounds algorithm for (Δ+1)-colouring, it is possible to find an O(Δ)-approximation to  in O(T) rounds. 




  
Acknowledgments: We would like to thank Amir Abboud, Shafi Goldwasser, Siqi Liu, Sidhanth Mohanty, Omri Shmueli, Rotem Tsabary and Richard Zhang for fruitful discussions.

plain






§ DEFERRED PROOFS FROM SECTION <REF>



	The idea is to pad H with more vertices and then to run an algorithm for maximal independent set on the new graph. In fact, the easiest way to see this is to argue that 𝒜 finds a maximal independent set with high probability on the graph H' obtained by adding n-n_H isolated nodes to H with unique identifiers. Since any maximal independent set in H' induces a maximal independent set in H, the claim follows. However, some of the algorithms in the CONGEST model assume that the input graph is connected[This assumption is usually made for global problems such as computing the diameter or all-pairs-shortest-paths. This is because global problems admit an Ω(D) lower bound, where D is the diameter of the network, which is ∞ for disconnected graphs. While assuming connectivity might not seem reasonable for the MIS problem, for completeness, we want our reduction to hold even for algorithms that make this assumption.]. To get around the connectivity issue, we define the graph H' obtained by adding a path of (n) nodes with unique Θ(log n)-bit identifiers to each node that is local minimum in H (with respect to the identifiers). Each node that is added to a path connected to a local minimum u∈ V_H, is given a unique identifier starting with the clog n bits of the identifier of  u as the LSB's (least significant bits), followed by another clog n bits to ensure that the identifier is unique with respect to the other nodes on the same path. Observe that H' is a graph of (n) nodes, with unique identifiers of Θ(log n) bits. Hence, H' is an appropriate input to the CONGEST model. Furthermore, given a maximal independent set I' of H', one can easily find a maximal independent set in H, as follows. Let I=I'∩ V_H. Each node that is a local minimum in H joins I if none of its neighbors in H is in I. It holds that I (after adding the additional nodes) is a maximal independent set in H. Since the nodes in H can easily simulate a maximal independent set algorithm in H', without any additional communication cost, it follows that the total running time is (|V_H'|,Δ_H')+1, where V_H' and Δ_H' are the set of nodes and maximum degree in H', respectively. Since Δ_H'≤Δ_H+1, and |V_H'|=(n), it holds that (|V_H'|,Δ_H')=((n),Δ_H). Moreover, for any n we know that for the specific problem of finding a maximal independent set it holds that ((n),Δ)=O((n,Δ)). This is because the round-complexity of finding a maximal independent set is at most logarithmic in the number of nodes. Finally, since a maximal independent set algorithm in H' succeeds with probability 1-1/(|V_H'|)≥ 1-1/(n), the claim follows.





