Large independent sets on random $d$-regular graphs with fixed degree $d$
Raffaele Marino Scott Kirkpatrick
cs.DS











 Raffaele Marino  Laboratoire de Théorie des Communications,

  Faculté Informatique et Communications,

  École Polytechnique Fédérale de Lausanne,

  1015, Lausanne, Switzerland

  Dipartimento di Fisica, Sapienza Università di Roma,

  P.le Aldo Moro 5, Roma, 00185, Italy

   

           Scott Kirkpatrick School of Computer Science and Engineering,

    The Hebrew University of Jerusalem,

    Edmond Safra Campus, Givat Ram, Jerusalem 91904, Israel







Large independent sets 
 on random d-regular graphs with fixed degree d
    Raffaele Marino          Scott Kirkpatrick  

    Received: date / Accepted: date
=======================================================================





This paper presents a linear prioritized local algorithm that computes large independent sets on a random d-regular graph with  small and fixed degree d. We studied experimentally the independence ratio obtained by the algorithm when d ∈ [3,100]. For all  d ∈ [5,100], our results  are larger than lower bounds calculated by exact methods, thus providing improved estimates of lower bounds. 








§ INTRODUCTION


Given a graph G(𝒩, E), where 𝒩 is the set of vertices of cardinality |𝒩|=N and E the set of edges of cardinality |E|=M, finding the maximum set of sites no two of which are adjacent is a very difficult task. This problem is known as the maximum independent set problem (MIS). It was shown to be NP-hard, and no known polynomial algorithm can guarantee to solve it <cit.>. In other words, finding a set ℐ of vertices, with the maximum cardinality, such that for every two vertices i,j ∈ℐ, there is no edge connecting the two, i.e., (i,j) ∉ E, needs a time which is super-polynomial if P≠ NP. 

For example, the first nontrivial exact algorithm for the MIS was due to Tarjan and Trojanowski’s O(2^N/3) ∼ O(1.2599^N) algorithm in 1977 <cit.>. Since then, many improvements have been obtained.  Today, the best algorithm that can solve the MIS exactly needs a time O(1.1996^N) <cit.>. Those results are a worst case bound.   We direct the interested reader to  <cit.>, and references therein, for a complete discussion on exact algorithms. 

The MIS  is important for applications in Computer Science, Operations Research, and Engineering, such as graph coloring, assigning channels to the radio stations, register allocation in a compiler, etc. 

Besides having several direct applications <cit.>, the MIS is closely related to another well-known optimization problem, the maximum clique problem <cit.>,<cit.>. For finding the maximum clique (the largest complete subgraph) of a graph G(𝒩, E), it suffices to search for the maximum independent set of the complement of G(𝒩, E).  










The MIS has been studied on many different random structures, like Erdős-Rényi graphs (ER),  random d-regular graphs (RRG). A random d-regular graph  is a graph selected from the distribution of all d-regular graphs on N vertices, with Nd even. A regular graph, is defined as a graph where each vertex has the same number of neighbors, i.e., d. Random d-regular graphs represent a subset of  Erdős-Rényi graphs distribution with probability p=<d>/N.

For the Erdős-Rényi class G_ER(N,p), where p is the probability that two different vertices are connected to each other, known local-search algorithms can find solutions only up to half the maximum independent set present, which is ∼ 2 log_1/(1-p) N <cit.> in the limit N→∞. 

This behavior also appears for random d-regular graphs G_d(N). 
In this cases, for example, Gamarnik and Sudan <cit.> showed that, for a sufficiently large value of d, local algorithms cannot find the size of the largest independent set in a d-regular graph of large girth with an arbitrarily small multiplicative error. 






The results of Gamarnik and Sudan <cit.>  was successively improved by Rahman, and Virág <cit.>, which analyzed the intersection densities of many independent sets in random d-regular graphs. They proved that for any ϵ > 0, local algorithms cannot find independent sets in random d-regular graphs with an independence ratio larger than (1 + ϵ) ln d/d if d is sufficiently large. The independence ratio is defined as the density of the independent set, thus α=|ℐ|/|𝒩|. Recently, the exact value of the independence ratio for all sufficiently large d was given by Ding et al. <cit.>.




However, these results appear to say nothing about small and fixed d. When d is small and fixed, e.g., d=3 or d=30, indeed, only lower and upper limits, expressed in terms of independence ratio, are known. 

Lower bounds on the independent sets' size identify sets that an efficient algorithm can find, while upper bounds are on the actual maximum independent set, not just on the size an algorithm can find.






The first upper bound for such a problem was given in 1981 by Bollobás <cit.>. He showed that the supremum of the independence ratio of 3-regular graphs with large girth is less than 6/13 ∼ 0.461538, in the limit N →∞. 

McKay, 1987, improved and generalized this result to d-regular graphs with large girth <cit.>, by using the same technique and a much more careful calculation. For example, for the cubic graph (3-regular graph), he was able to push Bollobás upper bound down to 0.455370. However, since then, only for cubic graphs, the upper bound has been improved by Balogh et al. <cit.>, namely to 0.454.  Replica methods suggest a slightly lower upper bound, and thus a smaller gap at small values of d <cit.>. For examples, the upper bounds given in  <cit.> for d=3 is 0.4509, while for d=4 is 0.4112.  A recent paper shows that this approach can be proven, but again, only for large d<cit.>.  

Remarkable results for lower bounds were obtained first by Wormald in 1995 <cit.>. He considered processes in which random graphs are labeled as they are generated and derived conditions under which parameters of the process concentrate around the values of real variables which come from the solution of an associated system of differential equations. By solving the differential equations he computed lower bounds for any fixed d returned by a prioritized algorithm, improving the values of bounds given by Shearer <cit.>. 


 

This algorithm is called prioritized because there is a priority in choosing vertices added to the independent set <cit.>. It follows the procedure of choosing vertices in the independent set ℐ one by one, with the condition that the next vertex is chosen randomly from those with the maximum number of neighbors adjacent to vertices already in ℐ.
	After each new vertex in ℐ is chosen (or labeled with an I), we must complete all of its remaining connections and label the neighbors which are identified as members of the set 𝒱 (for vertex cover). Although each vertex in ℐ can be chosen according to its priority, the covering vertices that complete its unfilled connections must then be chosen at random amount the remaining connections, to satisfy Bolobas' configuration model <cit.>. Following this priority is a simple way to minimize the size of the set of vertices covered and maximize the number of sites remaining as candidates for the set ℐ.

More precisely, we are given a random d-regular graph G_d(N), and we randomly choose a site i from the set of vertices 𝒩. We set i into ℐ, and we set all the vertices neighboring i into a set 𝒱. We label elements of ℐ with the letter I, while elements of 𝒱 with the letter V. Then, from the subset of vertices in 𝒩 that are neighbors of vertices in 𝒱, but are not yet labeled I or V, we choose randomly the element k that has the maximum number of connections with sites in 𝒱. We set it into ℐ. The vertices neighboring k, which are not in 𝒱, are added to the set 𝒱. This rule is repeated until  |ℐ|+|𝒱|=N. Along with this algorithm, one can consider an associated algorithm that simultaneously generates the random d-regular graph G_d(N) and labels vertices with the letter I or V. This associated algorithm, which will be described in detail in the next sections, allowed Wormald to build up the system of differential equations used for computing lower bounds for the MIS.

Improvements over this algorithm were achieved by Duckworth et al. <cit.>. These improvements were obtained by observing, broadly speaking, that the size of the structure produced by the algorithm is almost the same for d-regular graphs of very large girth, as it is for a random d-regular graph. However, since then, new lower bounds have been achieved only at small values of d, e.g., d=3 and d=4. Interesting results at d=3 have been achieved by Csóka, Gerencsér, Harangi and Virág <cit.>. They were able to find an independent set of cardinality up to 0.436194 N using invariant Gaussian processes on the infinite d-regular tree. This result was once again improved by Csóka <cit.> alone, which was able to increase the cardinality of the independent set on large-girth 3-regular graph up to 0.445327 N and on large-girth 4-regular graph up to 0.404070 N, by solving numerically the associated system of differential equations.


These improvements were obtained by deferring the decision whether a site i∈𝒩 must be labeled with a letter I or V. More precisely, he  requires that the sites for which a decision is deferred need additional (temporary) labels.  This means that counting the evolution of their populations, either through a differential equation or by experiment, gets more complicated.


Csóka <cit.> was able to improve lower bounds only for d=3 and d=4. This paper aims to generalize his method for any d ≥ 5, using an experimental approach. We recall in Tab. 1 the best upper and lower bounds[Recently in <cit.> has been presented a Monte Carlo method that can experimentally outperform any algorithm in finding a large independent set in random d-regular graphs, in a (using the words of the authors) " running time growing more than linearly in N" <cit.>. These authors conjectured lower bounds improvements only for d=20 and d=100, but with experimental results obtained on random d-regular graphs of order N=5· 10^4.  However, in this work, we are interested in comparing our results with the ones given by the family of prioritized algorithm because we believe that a rigorous analysis of the computational complexity would be performed on this algorithm.] for d∈ [3,100], first and second columns respectively. 

In this paper, as stated above, we  present experimental results of a greedy algorithm, built upon existing heuristic strategies, which leads to improvements on known lower bounds of large independent set in random d-regular graphs ∀ d ∈ [5, 100] <cit.>, <cit.>, <cit.>.

This new algorithm runs in linear time O(N) and melds Wormald’s, Duckworth and Zito’s, and Csoka’s ideas of prioritized algorithms <cit.>, <cit.>, <cit.>, <cit.>. The results obtained here are conjectured new lower bounds for large independent set in random d-regular graphs.

They are obtained by inferring the asymptotic values that  our algorithm can reach when N →∞ and by averaging sufficient simulations to achieve confidence intervals at 99%. These results lead improvements on known lower bounds ∀ d ∈ [5, 100] that, as far as we know, are not reached by any other greedy algorithms. Although the gap with upper bounds is still present, these improvements may imply new rigorous results in finding a large independent set in random d-regular graphs.

The paper is structured as follows: in section  <ref>  we define our deferred decision algorithm, and introduce a site labelling which will identify those sites for which we defer the I/V labelling decisions. In Sec. <ref> we present the deferred decision algorithm for d=3, and we introduce experimental results obtained on random 3-regular graphs of sizes [We recall that the order of a graph G(𝒩, E) is the cardinality of its vertices set 𝒩, while the size of a graph G(𝒩, E) is the cardinality of its edges set E.] up to 10^9. In Sec. <ref>, we present our deferred decision algorithm for d>3, and the experimental results associated with it, by extrapolation on random d-regular graphs with sizes up to 10^9 (see fourth column Tab. 1). 



§ NOTATION AND THE GENERAL OPERATIONS OF THE DEFERRED DECISION ALGORITHM





In this section, we define the notation used throughout this manuscript, and we define all operations that will be used to understand the deferred decision algorithm. 

We start by recalling that we deal with random d-regular graphs G_d(N), where d is the degree of each vertex i∈𝒩, where 𝒩 is the set of vertices and N=|𝒩|.
All vertices i ∈𝒩 are unlabeled.

For building a random d-regular graph we used the method described in <cit.>, and introduced in <cit.>. 


We take dN points, with dN even, and distribute them in N urns labeled 1,2,…, N, with d points in each urn. We choose a random pairing P=p_1, …, p_dN/2 of the points such that |p_i|=2 ∀ i. Each urn identifies a site in 𝒩. Each point is in only one pair p_i, and no pair contains two points in the same urn. No two pairs contain four points from just two urns. For building a d-regular graph G_d(N), then, we connect two distinct vertices i and j if some pair has a point in urn i and one in urn j. The conditions on the pairing prevent the formation of loops and multiple edges. 


The pairing referred to must be chosen uniformly at random, subjected to the constraints given. This can be done by repeatedly choosing an unpaired point and then choosing a partner for this point to create a new pair. As long as the partner is chosen uniformly at random from the remaining unpaired points, and as long as the process is restarted if a loop or multiple edge is created, the result is a random pairing of the required type <cit.>.  

In this paper, we use the method above described so that while we generate the random d-regular graph G_d(N), concurrently with our labelling process, labelling sites as we identify new links. 

The graphs built using the Generator of random d-regular graph Algorithm prevent the formation of loops and multiple edges, without introducing bias in the distribution where we sampling the graphs. We perform our analysis only on such graphs. In the case we meet on the last pair of vertices a loop, we set those sites not to be in the independent set. 

We define two separate sets ℐ and 𝒱 for independent and vertex cover sites. ℐ identifies the set of graph nodes that satisfies the property that no two of which are adjacent and 𝒱 its complement. A site i ∈ℐ is labeled with the letter I, while a site j ∈𝒱, it is labeled with the letter V.

We define Δ_i to be the degree of a vertex i, i.e. the number of links that a site is connected with, while with Δ_i the anti-degree of a vertex i, i.e. the number of free connections that i needs to complete during the graph building process. Of course, the constraint Δ_i + Δ_i = d is always preserved ∀ i ∈𝒩. At the beginning of the graph building process all i ∈𝒩 have Δ_i=0, Δ_i=d. At the end of graph building process all graph nodes will have Δ_i=d, Δ_i=0. We define ∂ i to be the set that contains all neighbors of i. 

For the sake of clarity, we define a simple subroutine on a single site i∈𝒩 of the Generator of random d-regular graph Algorithm (Subroutine GA(i, Δ_i)) that will be useful for understanding the algorithm presented in the next sections. The Subroutine GA(i, Δ_i) generates the remaining Δ_i connections of site i.  It keeps the supporting data to reflect the evolution of the network growth.


 


The sites that we choose following some priority, either the one we describe or any other scheme, will be called P sites.  The sites which are found by following links from the P sites (or by randomly generating connections from the P sites) are called C sites. More precisely, each site j ∈𝒩  we choose, not labeled yet with any letter (C or P) s.t.  Δ_j≤ 2 and the random connection(s) present on j are on site(s) in 𝒱   is a P site. The set 𝒫 defines the set of P sites. The set  𝒫 is kept in ascending order with respect to the anti-degree Δ_i of each site i∈𝒫. 

In general a site i labeled P will be surrounded by two sites labeled C. Because the labeling of those sites is deferred, we call those C-P-C structures virtual sites. A single virtual site, ṽ has an anti-degree Δ_ṽ equal  to the sum of all anti-degrees of sites l that compose site ṽ, i.e.  Δ_ṽ=∑_l ∈ṽΔ_l.  The number of sites l ∈ṽ is equal to the  cardinality of |ṽ|. The degree of  ṽ  is 
Δ_ṽ=d  |ṽ|-Δ_ṽ. As an example, we show in Fig. <ref> the operation of how a virtual site is created from a site s∈𝒫 with Δ_s=2, Δ_s=1,  and two sites j,k ∈𝒩 with Δ_j=3, Δ_k=3 and Δ_j=0, Δ_k=0. Let's assume that a site s ∈𝒩 s.t. Δ_s=2 exists. This is possible because a site l∈𝒱 is connected with it. This means that s must be labeled P and put into 𝒫. Let's run Subroutine GA(s, Δ_s) on s, and assume that the s connects with two neighbors j,k ∈𝒩. Being j,k ∈𝒩 connected to a P site, they are labeled C. We, then, define ṽ={s,j,k}. This set is a virtual node ṽ with  Δ_ṽ=4. 



  





We define 𝒜 to be  the set of virtual sites. The set  𝒜 is kept in ascending order respect to the anti-degree Δ of each virtual site ṽ∈𝒜. Virtual sites can be created, as described above, expanded or merged together (creating a new virtual site θ̃=∪_i ṽ_i).  Two examples are shown in Fig. <ref> and <ref>.

Fig. <ref> shows how to expand a virtual site ṽ_1. Let's imagine that a site m ∈𝒫, with anti-degree Δ_m=2,  is chosen. Let's run Subroutine GA(m, Δ_m) on m. Assume that m connects with n∈𝒩 (Δ_n=2) and with ṽ_1∈𝒜 (Δ_ṽ_1=4). In this case ṽ_1∈𝒜 expands itself, swallowing sites m and n and having a Δ_ṽ_1=5.

 Fig. <ref> shows how two virtual sites merge together. Let's imagine that a site p ∈𝒫, with anti-degree Δ_p=2,  is chosen during the building graph process.  Let's run Subroutine GA(p, Δ_p) on m. Assume that p  connects with two virtual sites ṽ_1∈𝒜 and ṽ_2∈𝒜 with Δ_ṽ_1=4 and Δ_ṽ_2=4. The new structure is a virtual site θ̃∈𝒜 with Δ_θ̃=6.



 










We define in the following a list of operations that will be useful for understanding the algorithm presented in the next sections.

Let 𝒳 and 𝒴 be two sets. Let i∈𝒳 and i∉𝒴. We define OP^i_move(i, 𝒳, 𝒴) to be the operation that moves the site i ∈𝒳 from the set 𝒳 to 𝒴, i.e., i∈𝒴 and i ∉𝒳. 

For example, OP^i_move(i, 𝒩, 𝒱) moves i∈𝒩 from the set 𝒩 to 𝒱, i.e., i∈𝒱 and i∉𝒩. Instead, the operation  OP^i_move(i, 𝒩, ℐ) moves i∈𝒩 from the set 𝒩 to ℐ, i.e., i∈ℐ and i∉𝒩. We recall that when a site is set into ℐ it is labeled with I, while when a site is set into 𝒱 it is labeled with V.


Let 𝒜 the set that contains virtual nodes ṽ. We define OP^ṽ_del(ṽ, 𝒜). to be the operation that deletes the site ṽ∈𝒜 from the set 𝒜,i.e., the element ṽ∉𝒜 anymore, and applies the operation OP^i_move(i, 𝒳, 𝒴) on each site i∈ṽ, following the rule: 


  * if i ∈ṽ is labeled with the letter P then 𝒳=𝒩 and 𝒴=ℐ;

  * if i ∈ṽ is labeled with the letter C then 𝒳=𝒩 and 𝒴=𝒱.






Let ṽ∈𝒜. We define SWAP-OP(ṽ) to be the operation such that ∀ i ∈ṽ:


  * if i is labeled P then the label P swaps to C;

  * if i is labeled C then the label C swaps to P;

Fig. <ref> shows how SWAP-OP(ṽ) acts on a virtual site ṽ.





§ THE DEFERRED DECISION ALGORITHM FOR D=3



In this section, we present our algorithm, simpler and slightly different from the one in <cit.>, but based on the same idea, for determining large independent set in random d-regular graphs with d=3, i.e., G_3(N).
It will also be the core of the algorithm developed in Sec. <ref>. As mentioned above, the algorithm discussed in this paper is basically a prioritized algorithm, i.e., algorithms that make local choices in which there is a priority in selecting a certain site. Our algorithm belongs to this class.

We start the discussion on the local algorithm for d=3 by giving the pseudo-code of the algorithm in  Algorithm <ref>. 

The algorithm starts by randomly taking a site i from the set 𝒩 and completes its connections in a random way, following the method described in Algorithm <ref>. 
Once all its connections are completed, site i has Δ_i=3 and Δ_i = 0. It is labeled with letter V, erased from 𝒩, and set into 𝒱. In other words, operation OP^i_move(i, 𝒩, 𝒱) is applied on it. Each neighbor of i, i.e., j∈∂ i, has degree Δ_j=1 and anti-degree Δ_j=2. Therefore, they are set into 𝒫, thus labeled P.

The algorithm picks a site k from 𝒫 with the minimum remaining connections. 

In general, If k has Δ_k≠0,  the algorithm completes all its connections, and removes it from 𝒫. Each site connected with a P is automatically labeled with the letter C. If a site k ∈𝒫 connects to another site j ∈𝒫, with j ≠ k, j is removed from 𝒫 and it is labeled C.

If k ∈𝒫 has Δ_k=0, the site k is set into ℐ, and it is removed from 𝒩 and 𝒫, i.e. the algorithm applies the operation OP^k_move(k, 𝒩, ℐ).

As defined in Sec. <ref>, a C-P-C structure is equivalent to a single virtual site, ṽ, which has an anti-degree Δ_ṽ. Each virtual site ṽ created with Δ_ṽ>2, is inserted into the set 𝒜. 


Once the set 𝒫 is empty, the algorithm selects a site ṽ∈𝒜 with the largest anti-degree Δ_ṽ, and it applies the operation OP^ṽ_del(ṽ, 𝒜) after having completed all the connections  ∀ i ∈ṽ with Δ_i≠ 0, using on each i  ∈ṽ with Δ_i≠ 0 Algorithm <ref>. 

We apply operation OP^ṽ_del(ṽ, 𝒜) on virtual sites ṽ∈𝒜 with the largest anti-degree because we hope the random connections outgoing from those sites could reduce the  anti-degrees of existing virtual sites in 𝒜, in such a way that the probability to have  virtual nodes with anti-degree Δ_ṽ≤ 2 increases. In other words, we want to create islands of virtual sites that are surrounded by a sea of V sites for applying the SWAP-OP(ṽ) on those nodes. This protocol, indeed, allows to increase the independent set cardinality and decrease the vertex cover set cardinality. 



For this reason, if virtual nodes with anti-degree Δ_ṽ≤ 2 exist in 𝒜, those sites have the highest priority in being selected. More precisely, the algorithm follows the priority rule:



  * ∀ṽ∈𝒜 s.t. Δ_ṽ=0 the algorithm applies sequentially the operation SWAP-OP(ṽ) and then the operation OP^ṽ_del(ṽ, 𝒜).


  * If no virtual sites ṽ∈𝒜 with Δ_ṽ = 0 are present, then the algorithm looks for those that have Δ_ṽ = 1. ∀ṽ∈𝒜 s.t. Δ_ṽ=1 it applies the operation SWAP-OP(ṽ), completes the last connection of the site i∈ṽ with Δ_i=1, applies on the last neighbour of i added OP^j_move(j, 𝒩, 𝒱), and then OP^ṽ_del(ṽ, 𝒜).


  * If no virtual sites ṽ∈𝒜 with Δ_ṽ = 0 and Δ_ṽ = 1 are present, then the algorithm looks for those that have Δ_ṽ = 2.  ∀ṽ∈𝒜 s.t. Δ_ṽ=2 it applies the operation SWAP-OP(ṽ), completes the last connections of the sites i∈ṽ with Δ_i≠ 0, labels the new added sites with the letter C, and updates the degree and the anti-degree of the virtual node ṽ.







The algorithm proceeds selecting virtual nodes and creating sites labeled P until 𝒩=∅. Once  𝒩=∅ it returns the set ℐ. The set of independent sites.
The code of the algorithm can be downloaded at <cit.>. 




We are comparing numerical results for independence ratios that agree with theoretical ones, at least, up to 5^th digit. For this reason, we performed an accurate analysis on random 3-regular graphs starting from those that have an order of 10^6, and pushing it up to 5·10^8. 
This analysis aims to compute the sample mean of the independence ratio size α(N) outputted by our algorithm. Each average is obtained in the following manner: for graphs of order N = 10^6 we averaged over a sample of 10^4 graphs; for order N = 2.5 · 10^6 we make an average over a sample of 7.5· 10^3 graphs; for order N = 5· 10^6 we make an average over a sample of 5· 10^3 graphs; for order N = 10^7 the average is performed over a sample of 10^3 graphs; for N = 2.5· 10^7 over 7.5· 10^2 graphs, for N = 5· 10^7 over 5· 10^2 graphs, for N = 10^8 over 10^2 graphs, for N = 2.5· 10^8 over 50 graphs, and for N = 5· 10^8 over 10 graphs. The mean and the standard deviation for each sample analyzed are reported in Tab. 2. Observing that the values of each independent set ratio sample mean reach an asymptotic value, we perform a linear regression on the model f(N)=(a/ ln N)+α_∞ for estimating the parameter α_∞ (blue line in Fig. <ref>). When N →∞ the first term of the regression, i.e., (a/ ln N), goes to 0 leaving out the value of α_∞ that describes the asymptotic value of the independence ratio that our algorithm can reach. Using the numerical standard errors obtained on each sample, we apply a General Least Square (GLS) method <cit.> for inferring the values of the parameters α_∞,  averaging sufficient simulations to achieve a confidence  interval at 99% on it. The value of α_∞ is the most important because it is the asymptotic value that our algorithm can reach when N →∞. From the theory of GLS, we know that the estimator of parameter α_∞ is unbiased, consistent and efficient, and a confidence interval on this parameter is justified. The analysis, performed on data reported in Tab. 2, shows that the independent set ratio reaches the asymptotic value α_∞= 0.445330 (3). This value agrees with the theoretical value proposed in <cit.>. 





  



§ THE DEFERRED DECISION ALGORITHM FOR D>3





In this section, we present how to generalize the  prioritized algorithm for all d>3. It, like the one previously described in Sec. <ref>, builds the random regular graph, and, at the same time, tries to maximize the independent set cardinality |ℐ|. 
The main idea that we propose is to melt down two existing algorithms, namely the one in <cit.> and the one above described, into a new prioritized algorithm, which  is able to maximize the independent set cardinality, providing improved estimates of lower bounds.    The new conjectured lower bounds  come from extrapolation on random  d-regular graphs of size up to 10^9. 

Before introducing the algorithm, we present a new operation that will allow us to simplify the discussion.


Let  i ∈𝒩. We define OP^i_build-del(i, 𝒩, ℐ, 𝒱) the operation that connects i to Δ_i sites following Algorithm <ref> rules, applies OP^i_move(i, 𝒩, ℐ), and ∀ j∈∂ i sequentially runs Algorithm <ref> and applies the operation OP^j_move(j, 𝒩, 𝒱). 


The pseudo-code of the last operation is described in Algorithm <ref>.




We start the discussion on the local algorithm for d>3 by giving the pseudo-code of the algorithm in  Algorithm <ref>. 



 





The algorithm starts randomly selecting a site z  from the set of all nodes 𝒩, i.e. z ∈𝒩.
It then applies OP^z_build-del(z, 𝒩, ℐ, 𝒱) on the site z (see Fig. <ref>). 
This operation creates nodes with different degrees and anti-degrees. 
The algorithm proceeds in choosing the node m, from those with minimum Δ_m. 
If the node m has Δ_m> 2, the algorithm applies the operation OP^m_build-del(m, 𝒩, ℐ, 𝒱) on site m.  In other words, we are using the algorithm developed in <cit.> until a site m ∈𝒩 with Δ_m≤ 2 pops up. When such a case appears, we label it as a P site and we move it into the set 𝒫.

As before, once 𝒫 is not empty, the sites in 𝒫 have the highest priority in being processed for creating virtual nodes. 

In principle more complex virtual nodes can be created. For instance defining a P site as a site i ∈𝒩 not labeled yet with any letter (C or P) s.t.  Δ_j≤ d-1, with Δ_j random connections with sites already in 𝒱.  Although we do not see any logical impediment in creating more complex virtual nodes, we confine ourselves to the case where the anti-degree of a bare site in 𝒩 is less or equal to two for any values of d, because it is much easier to handle and explain.

Until the set 𝒫 is empty, the algorithm builds virtual sites, which are set into 𝒜. 
 
Once the set 𝒫 is empty, the highest priority in being covered is placed on the virtual sites contained in 𝒜.
The rules that the algorithm follows are:




  * ∀ṽ∈𝒜  s.t.   Δ_ṽ=0 Δ_ṽ=1, the algorithm applies sequentially operation SWAP-OP(ṽ)  and the operation OP^ṽ_del(ṽ, 𝒜). (in the case Δ_ṽ=1, the algorithm before it completes the absent  connection for the site i ∈ṽ s.t. Δ_i=1, and it applies on the last added site j∈∂ i the operation OP^j_move(j, 𝒩, 𝒱). Then on the virtual site ṽ it applies OP^ṽ_del(ṽ,  𝒜)).


  * If ∃ṽ∈𝒜 s.t. Δ_ṽ= 2  ∄q̃∈𝒜 s.t. Δ_q̃ = 0 Δ_q̃=1 the algorithm chooses with the highest priority the site with Δ_ṽ=2. Then it applies operation SWAP-OP(ṽ) on ṽ, it runs ∀ i∈ṽ with Δ_i≠ 0 the Subroutine GA(i, Δ_i) and labels each neighbour(s) of i with letter C.


  * If ∃ṽ∈𝒜 s.t. Δ_ṽ> 2   ∄p̃∈𝒜 s.t. Δ_p̃≤ 2 the algorithm chooses a  a site ṽ∈𝒜 with the maximum Δ_ṽ and it applies the OP^ṽ_del(ṽ,  𝒜) with the maximum Δ_ṽ, after having run the Subroutine GA(i, Δ_i) on each i∈ṽ such that Δ_i≠ 0.


  * In the case 𝒫=∅𝒜=∅𝒩≠∅  the algorithm takes a site t ∈𝒩 with minimum Δ_t, and applies the operation OP^t_build-del(t, 𝒩, ℐ, 𝒱).




The algorithm works until the following condition is true: 𝒩= ∅𝒫=∅𝒜=∅. Then, it checks that all sites in ℐ are covered only by sites in 𝒱, and no site in ℐ connects to any other site in ℐ. 

The results obtained by the algorithm at different values of d, and at different orders N, are presented in Tab. 3, 4, and 5. The confidence intervals of the asymptotic  independent set ratio values, obtained by extrapolation described in the previous section, are presented in Tab. 1. In other words, we performed simulations for each value of d by computing the sample mean and the standard error of the independence ratio a some values of N. Then we use GLS methods for extrapolating  the values of α_∞ and building up its confidence interval.








From our analysis, we observe that ∀ d>4 our results, as far as we know, exceed the best theoretical lower bounds given by greedy algorithms. Those improvements are obtained because we 
allow the virtual nodes to increase and decrease their anti-degree. In other words, this process transforms the random  d-regular graph into a sparse random graph, where it is much easier making local rearrangements (our SWAP-OP(·) move)  to enlarge the independent set.

More precisely, the creation of virtual nodes that increase or decrease their anti-degrees allows us to deal with a graph that is not anymore d-regular but has average connectivity ⟨ d ⟩. 


However, this improvement decreases as d becomes large, ∼ 1/d, and disappears when d →∞ (see Fig. 7, bottom panel). Indeed, the number of P labeled sites decreases during the graph building process (see Fig. 7, top panel), invalidating the creation of virtual nodes that are the core of our algorithm. This means that our algorithm for d →∞ will reach the same asymptotic independent set ratio values obtained by the algorithm in <cit.>.

In conclusion, for any fixed and small d, we have that the two algorithms are distinct, and our algorithm produces better results without increasing the computational complexity.







§ CONCLUSION



This manuscript presents a new local prioritized algorithm for finding a large independent set in a random d-regular graph at fixed connectivity. This algorithm makes deferred decision in choosing which site must be set into the independent set or into the vertex cover set. This deferred strategy can be seen as a depth-first search delayed in time, without backtracking. It works, and shows very interesting results.

For all d ∈ [5, 100] we conjecture new lower bounds for this problem. All the new bounds improve upon the best previous bounds. All of them have been obtained by extrapolation on samples of random d-regular graphs of sizes up to 10^9. For random 3-regular graphs, our algorithm is able to reach, when N →∞, the asymptotic value presented in <cit.>. For 4-regular graphs, instead, we are not able to improve the existing lower bound. This discrepancy could be described by the fact that our algorithm is general and is not implemented only for a single value of d with ad hoc strategy. 

The improvements upon the best bounds are due to reducing the density of the graph, introducing regions in which virtual sites replace multiple original nodes and optimal labellings can be identified.
The creation of virtual sites allows to group together nodes of the graph to label at a different instant with respect to their creation. Those blobs of nodes transform the random d-regular graphs into a sparse graph, where the searching of a large independent set is simpler.

Undoubtedly more complex virtual nodes can be defined and additional optimizations can be identified.  This will be addressed in a future manuscript.




  
Acknowledgments. R. M. would like to thank Nicolas Macris for a first reading of the manuscript, and Endre Csóka for useful discussions. S. K. is supported by the Federman  Cyber Security Center at the Hebrew University of Jerusalem.  R.M. started this project when he was supported by the Federman  Cyber Security Center at the Hebrew University of Jerusalem, and finished it by the support of Swiss National Foundation grant No. 200021E 17554. 

unsrt  


