Distributed Maximal Independent Set on Scale-Free Networks
share
The problem of distributed maximal independent set (MIS) is investigated on inhomogeneous random graphs with power-law weights by which the scale-free networks can be produced. Such a particular problem has been solved on graphs with n vertices by state-of-the-art algorithms with the time complexity of O(n). We prove that for a scale-free network with power-law exponent β > 3, the induced subgraph is constructed by vertices with degrees larger than n^*n is a scale-free network with β' = 2, almost surely (a.s.). Then, we propose a new algorithm that computes an MIS on scale-free networks with the time complexity of O(n/n) a.s., which is better than O(n). Furthermore, we prove that on scale-free networks with β≥ 3, the arboricity and degeneracy are less than 2^log^1/3n with high probability (w.h.p.). Finally, we prove that the time complexity of finding an MIS on scale-free networks with β≥ 3 is O(log^2/3n) w.h.p.
READ FULL TEXT