IIIT Hyderabad Publications 


Fast Ruling SetsAuthor: Tushar Bisht Date: 20160503 Report no: IIIT/TH/2016/15 Advisor:Kishore Kothapalli AbstractComputing 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 truling set. A truling 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 truling 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 2ruling 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 [6] whenever ∆ ∈ O(2 log n ). We then use it to present another algorithm which √ can compute a 2ruling 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 truling 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 [13] and M ́etivier’s [14] 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. 