Source-linked AI summary
A constructive proof of the general Lovasz Local Lemma
Robin A. Moser, Gábor Tardos
TL;DR
The paper addresses the gap between the Lovasz Local Lemma’s non-constructive existence proof and the need to efficiently find a satisfying evaluation. It gives an algorithmic resampling proof and establishes expected resampling bounds, with deterministic search possible under additional conditions.
Problem
The original Local Lemma proof establishes existence but does not provide an efficient procedure for finding a point that avoids all events.
Method
The algorithm repeatedly resamples the variables of an arbitrarily chosen violated event while leaving all other variable values unchanged.
Results
Each event A is resampled at most an expected x(A)/(1−x(A)) times before the algorithm finds an evaluation violating no events.
Takeaways & Limitations
The method directly supports efficient implementations for almost all known Local Lemma applications and can become deterministic when the dependency graph has constant maximum degree.
Takeaways & Limitations
Efficiency requires efficiently sampling variable values and checking them against events; deterministic search additionally requires polynomial-time conditional probabilities and constant dependency-graph degree.
Abstract
from arXiv · showhide
The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alo91, MR98, CS00, Mos06, Sri08, Mos08]. In [Mos09], a constructive proof was presented that works under negligible restrictions, formulated in terms of the Bounded Occurrence Satisfiability problem. In the present paper, we reformulate and improve upon these findings so as to directly apply to almost all known applications of the general Local Lemma.
1 Introduction
The paper gives an algorithmic proof of the general Lovász Local Lemma [EL75], replacing its non-constructive existence argument with efficient sequential and parallel resampling procedures. Under stronger conditions, it also provides a deterministic polynomial-time algorithm, extending the constructive direction initiated by Beck.
- Contribution: The paper’s main contribution is an algorithmic Local Lemma proof that efficiently finds an evaluation violating none of the events, rather than merely proving existence.The approach applies when variables can be sampled and event violations checked efficiently, without requiring conditional probabilities or expectations for the randomized solvers.
- Dependency model: The framework models events through the mutually shared variables in their minimal determining sets, yielding a dependency graph that certifies the Local Lemma’s required independence condition.Events are adjacent exactly when their determining variable sets intersect.
- Sequential solver: The sequential solver repeatedly resamples an arbitrarily chosen violated event and, under Theorem 1.2’s conditions, terminates with bounded expected resampling counts.Each event A is resampled at most an expected x(A)/(1 −x(A)) times.
- Parallel solver: The parallel solver simultaneously resamples a maximal independent set of currently violated events, requiring an expected O(1/(1−x(A))) number of parallel steps under Theorem 1.3’s conditions.Independence in the dependency graph ensures that the selected events can be resampled concurrently.
- Derandomization: With efficiently computable conditional probabilities and constant-bounded dependency degree, the randomized method can be derandomized into a deterministic polynomial-time algorithm.The deterministic result assumes finite variable domains and a constant ε satisfying the theorem’s Local Lemma condition.
2 Execution logs and witness trees
The algorithm’s execution is recorded as a resampling log, from which each correction step is reconstructed as a witness tree. Witness trees are proper when they occur, their occurrence probability is bounded by Q, and event resampling counts correspond to rooted witness trees.
- Execution logs: The execution log C records the events selected for resampling at each step and becomes a random variable once the selection discipline is fixed.The violated event chosen for correction may follow any fixed deterministic or randomized procedure; the analysis does not depend on that choice.
- Witness-tree construction: Each resampling step yields a witness tree by scanning the preceding log backward and attaching compatible events to the deepest eligible vertex, while skipping incompatible steps.Children receive labels from the inclusive dependency neighborhood Γ+; ties among deepest eligible vertices may be broken arbitrarily.
- Witness-tree properties: Any witness tree occurring in the log is proper, and its probability of appearing is at most Q.The proof uses independence of labels at each tree level and a τ-check coupled to the algorithm’s random source, which passes whenever the tree occurs.
- Resampling counts: For each event A, the resampling count N_A equals both its occurrences in C and the number of distinct occurring proper witness trees rooted at A.The correspondence follows by indexing the successive steps at which A is selected for resampling.
3 Random generation of witness trees
This section generates proper witness trees with a prescribed root through a multitype Galton–Watson process. It computes the probability of each tree and uses the resulting bound to complete the proof of Theorem 1.2.
- Random generation of witness trees: The process starts with a root labelled A and independently adds children labelled by inclusive neighbors with probability x(B) in successive rounds.Each vertex independently tests every identical or adjacent event in the dependency graph for possible child generation.
- Random generation of witness trees: Lemma 3.1 expresses the probability of generating any fixed proper witness tree as a product over vertices, accounting for absent child labels and the always-born root.The proof rewrites the expression using the sets of inclusive neighbors absent from each vertex’s children, then simplifies it with exclusive neighborhoods.
4 Analyzing the parallel algorithm
The analysis converts each parallel execution into an ordered sequential execution and relates parallel step indices to witness-tree depths. This correspondence yields a witness-tree tail bound that implies Theorem 1.3.
- Execution correspondence: An arbitrary ordering of the violated events resampled in each parallel step produces a corresponding sequential execution whose log is partitioned into step segments S_j.The segment S_j contains the resamplings performed during parallel step j.
- Execution correspondence: Every resampling t in segment S_j has a witness tree τ_C(t) of depth j − 1.This follows because the j-th parallel step contains mutually independent events, while earlier steps can increase witness-tree depth by exactly one each.
- Tail bound: If the parallel algorithm runs for at least k steps, its log must contain a witness tree of depth k − 1 and therefore at least k vertices.Bounding the probability of such trees reduces the runtime analysis to the set T_A(k) of witness trees with at least k vertices.
- Tail bound: The resulting bound, using the assumption of Theorem 1.3, implies Theorem 1.3.The final probability estimate is obtained after applying the theorem’s assumption to the witness-tree bound.
5 A deterministic variant
Under Theorem 1.4’s additional assumptions, the randomized algorithm can be derandomized by selecting finite variable-value sequences that eliminate all sufficiently large consistent witness trees. Enumerating a polynomial-size witness-tree list and using conditional expectations then yields a tailored random source guaranteeing polynomial termination.
- Deterministic variant: The derandomization replaces the random source with finite evaluation sequences chosen to ensure that no large witness tree is consistent.The sequences need only cover samples through index c log m once sufficiently large consistent trees are excluded.
- Deterministic variant: Enumerating all witness trees of sizes [c log m, (k + 1)c log m] produces a polynomial-size list when dependency degrees are bounded.The deterministic procedure processes variable-sample index pairs incrementally and evaluates candidate assignments against this list.
- Deterministic variant: A consistent witness tree of size at least u implies one of size in [u, (k + 1)u], reducing the search to a bounded size range.The reduction uses the dependency graph’s maximum degree bound k and the tree’s branching structure.
- Deterministic variant: Conditional expectations select each variable sample so the expected number of consistent listed trees never exceeds 1/2, forcing the final number to be zero.Once all values are fixed, the conditional expectation equals the actual count of consistent trees.
- Deterministic variant: After polynomial preprocessing, running the original parallel or sequential algorithm with the tailored values guarantees termination after polynomially many steps.Tree probabilities are computed by bottom-up traversal while accounting for which sample each variable uses.
6 The Lopsided Local Lemma
The section extends the Local Lemma to lopsidependence, yielding a stronger criterion because the lopsided neighborhood is contained in the ordinary dependency neighborhood. Theorem 6.1 guarantees a satisfying assignment and bounds randomized resampling, with applications including CNF satisfiability.
- 6 The Lopsided Local Lemma: Lopsidependence compares evaluations differing only on shared variables, and defines a graph whose neighborhood Γ′(A) replaces Γ(A) in the Local Lemma.Events with disjoint variable sets cannot be lopsidependent, so Γ′(A) ⊆ Γ(A), making the assumption weaker and the theorem stronger.
- 6 The Lopsided Local Lemma: For elementary events, lopsidependence is mutual exclusivity; decomposing finite-domain events into elementary events can eliminate dependencies and make Theorem 6.1 applicable.This decomposition preserves the relevant condition when a suitable assignment to the elementary events exists.
- 6 The Lopsided Local Lemma: In CNF satisfiability, violated clauses are lopsidependent when they contain complementary literals, while mere variable overlap does not necessarily create lopsidependence.This makes lopsidependence particularly effective for satisfiability applications.
- 6 The Lopsided Local Lemma: Theorem 6.1 gives a satisfying assignment whenever reals x(A) satisfy its lopsided criterion, and bounds event A's expected resamplings by x(A)/(1 − x(A)).The expected total number of resampling steps is bounded by the corresponding sum over events.
- 6 The Lopsided Local Lemma: The proof adapts witness trees by restricting children to Γ′+(A), requiring distinct child labels, and modifying the branching process accordingly.Lemma 6.2 bounds the probability that a fixed proper lopsided witness tree occurs, allowing the original Local Lemma proof to carry over.
7 Conclusion
Theorem 1.2’s resampling bound is tight only in the uninteresting case of independent events, while implementation requires variable sampling and violated-event detection. Derandomization for dependency graphs with unbounded degree remains open.
- Conclusion: The bound x(A)/(1−x(A)) is tight only when A is isolated and x(A) = Pr[A], so the total resampling bound requires all events to be independent.For an event A, equality in its expected-resampling bound likewise requires A to be isolated in the dependency graph.
- Conclusion: The sequential algorithm requires samplers for variables in P and an algorithm identifying violated events; the parallel version additionally requires a maximal independent set of violated dependency-graph vertices.Luby’s randomized algorithm provides such a maximal independent set in logarithmic expected time with one processor per vertex.
- Conclusion: Derandomizing the algorithm for dependency graphs with unbounded degree remains an open question.