Kothapalli, Kishore ;
Pemmaraju, Sriram
SuperFast 3Ruling Sets
Abstract
A truling set of a graph G = (V, E) is a vertexsubset S that is independent and satisfies the property that every vertex v in V is at a distance of at most t from some vertex in S. A maximal independent set (MIS) is a 1ruling set. The problem of computing an MIS on a network is a fundamental problem in distributed algorithms and the fastest algorithm for this problem is the O(log n)round algorithm due to Luby (SICOMP 1986) and Alon et al. (J. Algorithms 1986) from more than 25 years ago. Since then the problem has resisted all efforts to yield to a sublogarithmic round algorithm. There has been recent progress on this problem, most importantly an O(log Delta . sqrt(log n))round algorithm on graphs with n vertices and maximum degree Delta, due to Barenboim et al. (to appear FOCS 2012). The time complexity of this algorithm is sublogarithmic for Delta =2^{o(sqrt{log n})}.
We approach the MIS problem from a different angle and ask if O(1)ruling sets can be computed faster than the currently known fastest algorithm for an MIS? As an answer to this question, we show how to compute a 2ruling set of an nvertex graph in O((log n)^{3/4}) rounds. We also show that the above result can be improved for special classes of graphs. For instance, on high girth graphs (girth 6 or more), trees, and graphs of bounded arboricity, we show how to compute 3ruling sets in exp(O({sqrt{loglog n}})) rounds, O((log log n)^2 .logloglog n) rounds, and O((loglog n)^3) rounds, respectively.
Our main technique involves randomized sparsification that rapidly reduces the graph degree while ensuring that every deleted vertex is close to some vertex that remains. This technique may have further applications in other contexts, e.g., in designing sublogarithmic distributed approximation algorithms. Our results raise intriguing questions about how quickly an MIS (or 1ruling sets) can be computed, given that 2ruling sets can be computed in sublogarithmic rounds.
BibTeX  Entry
@InProceedings{kothapalli_et_al:LIPIcs:2012:3854,
author = {Kishore Kothapalli and Sriram Pemmaraju},
title = {{SuperFast 3Ruling Sets}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {136147},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3854},
URN = {urn:nbn:de:0030drops38549},
doi = {10.4230/LIPIcs.FSTTCS.2012.136},
annote = {Keywords: MIS, ruling sets, graph sparsification, distributed algorithms}
}
2012
Keywords: 

MIS, ruling sets, graph sparsification, distributed algorithms 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Issue date: 

2012 
Date of publication: 

2012 