IIIT Hyderabad Publications
Fast Ruling Sets
Author: Tushar Bisht
Report no: IIIT/TH/2016/15
Computing a maximal independent set (MIS) is a fundamental problem in distributed computing for its ability to nicely capture the essential challenge of symmetry breaking and also for its myriad applications to other problems. A relaxed version of computing an MIS is the problem of computing a t-ruling set. A t-ruling set for an integer t ≥ 1 in a graph G is an independent subset S ⊆ V such that every nodes v ∈ V is either in S or has a neighbor w ∈ S at a distance at most t from v. Computing a t-ruling set also involves symmetry breaking. All the algorithms we present in this thesis are randomized and synhronous in nature. First, we √ log ∆ O( log log n) rounds with + e present an algorithm which computes a 2-ruling set in any graph in log log n high probability, where n denotes the number of vertices in the graph and ∆ denotes the maximum log ∆ 1/2+ degree of any vertex in the graph. This result is an improvement over the O (log n) + (log n) √ round algorithm from  whenever ∆ ∈ O(2 log n ). We then use it to present another algorithm which √ can compute a 2-ruling set for graphs of arboricity a = 2 O( log n) in O( (log n/ log log n) rounds with high probability. We then extend the ideas from the above algorithm and show that a (t + 1)-ruling set for any t ≥ 1 in graphs with arboricity a = O(log log n) can be computed in O(t log 1/t ∆ + t 2 (log log n) 1/t + (log log n) 2 ) rounds. Therefore, a log log ∆-ruling set for bounded arboricity graphs can be computed in O((log log n) 2 ) rounds. Our results therefore indicate that while computing an MIS in graphs of √ bounded arboricity in O( log n) rounds is still an open problem, ruling sets for small values of t can be found in much fewer rounds. Similarly, a (t + 1)-ruling set for a general graph can be computed in √ O(t log 1/t ∆ + t 2 (log log n) 1/t + e O( log log n) ) rounds. Also, a t-ruling set for graphs of girth > 6 can √ be computed in O(t log 1/t ∆ + t 2 (log log n) 1/t + e O( log log n) ) rounds. In a later section, we compare the run time of Luby’s  and M ́etivier’s  MIS algorithms, two fundamental algorithms for computing an MIS in general graphs. Also, we try to understand the effect of probability of a node getting selected by Luby’s algorithm on the number of rounds required by algorithm to finish. We run these algorithms on different types of graphs, namely Random, Regular and Bipartite Graphs.
Full thesis: pdf
Centre for Security, Theory and Algorithms
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved.