Degree-Greedy Algorithms on Large Random Graphs

PAOLA BERMOLEN; MATTHIEU JONCKHEERE; FEDERICO LARROCA; MANUEL SÁENZ

Toulouse

Congreso; IFIP Performance 2018; 2018

 Computing the size of maximum independent sets is a NP-hard problem for fixed graphs. Characterizing and designing efficient algorithms to compute (or approximate) this independence number for random graphs are notoriously difficult and still largely open issues. After a thorough review of the literature, we show that a low complexity degree-greedy exploration is actually asymptotically optimal on a large class of sparse random graphs, providing the first optimality result for sequential explorations algorithms in this context. Encouraged by this result, we present and study two variants of sequential exploration algorithms: static and dynamic degree-aware explorations. We derive hydrodynamic limits for both of them, which in turn allow us to compute the size of the resulting independent set. Whereas the former is simpler to compute, the latter may be used to arbitrarily approximate the degree-greedy algorithm. Both can be implemented in a distributed manner. The corresponding hydrodynamic limits constitute an efficient method to compute or bound the independence number for a large class of sparse random graphs. As an application, we then show how our method may be used to compute (or approximate) the capacity of a large 802.11-based wireless network. We also consider further indicators such as the fairness of the resulting configuration, and show how an interesting tradeoff between fairness and capacity can be achieved.