Coloring nonunifoum hypergraphs: A new algorithmic approach to the generalLovasz local lemma

The Lovasz local lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz local lemma does not supply a polynomial-time algorithm for find ing these structures. Beck was the first who gave a method of converting so me of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. He applied his technique to the s ymmetric form of the Lovasz local lemma and, in particular, to the problem of 2-coloring uniform hypergraphs. In this paper we investigate the general form of the Lovasz local lemma. Our main result is a randomized algorithm for 2-coloring nonuniform hypergraphs that runs in expected lineal time. Ev en for uniform hypergraphs no algorithm with such a runtime bound was previ ously known, and no polynomial-time algorithm was known at all for the clas s of nonuniform hypergraphs we will consider in this paper. Our algorithm a nd its analysis provide a novel approach to the general Lovasz local lemma that may be of independent interest. We also show how to extend our result to the c-coloring problem. (C) 2000 John Wiley & Sons, Inc.