We provide a tight analysis which settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA'12]. The parallel distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS'87], and the previously best known bounds were @math rounds in expectation for Erd o s-R ' e nyi random graphs by Calkin and Frieze [Random Struc. & Alg. '90] and @math rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA'12]. We prove a high probability upper bound of @math on the round complexity of this algorithm in general graphs, and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC'85, JALG'86].
The result of Calkin, Frieze and Ku c era @cite_6 proves that this is asymptotically best possible and we also provide an alternative short proof of the lower bound in appendix:lower . In appendix:implications , we present implications of thm:MIS for maximal matching and @math -vertex-coloring as well as the correlation clustering problem.
@cite_6
2115831572 2963702702 2963885173 2006057641
For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of 1,...,k n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs. We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of Kahn's result that a disjoint union of copies of Kd;d maximizes the number of independent sets of a bipartite d-regular graph, Galvin and Tet ali's result that the independence polynomial is maximized by the same, and Zhao's extension of both results to all d-regular graphs. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of Kd;d. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom. In probabilistic language, our main theorems state that for all d-regular graphs and all �, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity � are maximized by Kd;d. Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case. Using a variant of the method we prove a lower bound on the occupancy fraction of the hard-core model on any d-regular, vertex-transitive, bipartite graph: the occupancy fraction of such a graph is strictly greater than the occupancy fraction of the unique translationinvariant hard-core measure on the infinite d-regular tree In this paper we establish a substantially improved lower bound on the k-color ability threshold of the random graph G(n, m) with n vertices and m edges. The new lower bound is ≈ 1.39 less than the 2k ln (k)-ln (k) first-moment upper bound (and approximately 0.39 less than the 2k ln (k) - ln(k) - 1 physics conjecture). By comparison, the best previous bounds left a gap of about 2+ln(k), unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments [: PNAS 2007]. Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of k-colorings of the random graph. We consider the parallel greedy algorithm of Coppersmith, Raghavan, and Tompa (Proc. of 28th Annual IEEE Symp. on Foundations of Computer Science, pp. 260–269, 1987) for finding the lexicographically first maximal independent set of a graph. We prove an Ω(log n) bound on the expected number of iterations for most edge densities. This complements the O(log n) bound proved in Calkin and Frieze (Random Structures and Algorithms, Vol. 1, pp. 39–50, 1990). © 1992 Wiley Periodicals, Inc.