We present improved results for approximating Maximum Independent Set ( @math ) in the standard LOCAL and CONGEST models of distributed computing. Let @math and @math be the number of nodes and maximum degree in the input graph, respectively. Bar- [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a @math -approximation to @math in @math rounds, where @math is the running time for finding a independent set, and @math is the maximum weight of a node in the network. Whether their algorithm is randomized or deterministic depends on the @math algorithm that they use as a black-box. Our results: (1) A deterministic @math rounds algorithm for @math -approximation to @math in the CONGEST model. (2) A randomized @math rounds algorithm that finds, with high probability, an @math -approximation to @math in the CONGEST model. (3) An @math lower bound for any randomized algorithm that finds an independent set of size @math that succeeds with probability at least @math , even for the LOCAL model. This hardness result applies for graphs of maximum degree @math . One might wonder whether the same hardness result applies for low degree graphs. We rule out this possibility with our next result. (4) An @math rounds algorithm that finds an independent set of size @math in graphs with maximum degree @math , with high probability. Due to a lower bound of @math that was given by Kuhn, Moscibroda and Wattenhofer [JACM, 2016] on the number of rounds for finding a maximal independent set ( @math ) in the LOCAL model, even for randomized algorithms, our second result implies that finding an @math -approximation to @math is strictly easier than @math .
For computing an MIS, for many years, the only known algorithms were the classic ones by @cite_34 @cite_1 that take @math rounds, even for the CONGEST model. In recent breakthroughs, @cite_25 presented a LOCAL algorithm that takes @math rounds, which was then improved by Ghaffari @cite_7 to an @math rounds. More recently, Ghaffari @cite_16 presented a CONGEST algorithm that takes @math rounds.
@cite_7 @cite_1 @cite_16 @cite_34 @cite_25
1666479227 2100061495 2902010279 1964089073 2467514673
The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity. Classical MIS algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability1, all nodes terminate after O(log n) rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node v terminates after O(log deg(v) + log 1 e) rounds, with probability at least 1 -- e. The degree-dependency in this bound is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12; arXiv: 1202.1983v3], we2 get an MIS algorithm with a high probability global complexity of O(log Δ) + 2O([EQUATION]), where Δ denotes the maximum degree. This improves over the O(log2 Δ) + 2O([EQUATION]) result of , and gets close to the Ω(min log Δ, [EQUATION] ) lower bound of Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation Algorithms (LCA) model, and a faster distributed algorithm for the Lovasz Local Lemma. Two basic design strategies are used to develop a very simple and fast parallel algorithms for the maximal independent set (MIS) problem. The first strategy consists of assigning identical copies of a simple algorithm to small local portions of the problem input. The algorithm is designed so that when the copies are executed in parallel the correct problem output is produced very quickly. A very simple Monte Carlo algorithm for the MIS problem is presented which is based upon this strategy. The second strategy is a general and powerful technique for removing randomization from algorithms. This strategy is used to convert the Monte Carlo algorithm for this MIS problem into a simple deterministic algorithm with the same parallel running time. Abstract A simple parallel randomized algorithm to find a maximal independent set in a graph G = ( V , E ) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O (| E | d max ) processors is O (log n ), where d max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O (| E |) processors the algorithm runs in O (log 2 n ). Previously, an O (log 4 n ) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O (log 2 n ) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d -wise rather than fully independent random choices (for some constant d ) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments. Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: —An MIS algorithm running in O(log2D Δ L 2√log n, and comes close to the Ω(flog Δ log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in O(log Δ + log 4log n) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on Δ is nearly optimal. —A (Δ + 1)-coloring algorithm requiring O(log Δ + 2o(√log log n) time, improving on an O(log Δ + √log n)-time algorithm of Schneider and Wattenhofer. —A method for reducing symmetry-breaking problems in low arboricity degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O(√log n)-time maximal matching algorithm for graphs with arboricity up to 2√log n and an O(log 2 3n)-time MIS algorithm for graphs with arboricity up to 2(log n)1 3. Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n)-size graph.