Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma
Artur Czumaj, Christian Scheideler · 2000
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 finding these structures. Beck was the first who gave a method of converting some of these existence proofs into efficient algorithmic procedures, at the cost of loosing a little in the estimates. He applied his technique to the symmetric 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 non-uniform hypergraphs that runs in expected linear time. Even for uniform hypergraphs no algorithm with such a runtime bound was previously known, and no polynomial-time algorithm was known at all for the class of non-uniform hypergraphs we will consider in this paper. Our algorithm and its analysis provi...