Focused Stochastic Local Search and the Lovász Local Lemma

Dimitris Achlioptas, Fotis Iliopoulos

Abstract

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from the algorithmization of the Lovász Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.

Introduction

In combinatorics and computer science, finding an object that satisfies a large set of constraints is a fundamental challenge. The Lovász Local Lemma (LLL) has long been a cornerstone of the probabilistic method, providing an existential proof for such objects when constraint dependencies are limited. While the LLL was originally non-constructive, the breakthrough Moser-Tardos algorithm demonstrated that for product measures, a simple "resampling" local search could efficiently find satisfying assignments.

This paper extends these ideas into a unified framework for focused stochastic local search. These algorithms identify specific "flaws" (violations) and apply local "actions" to fix them. The authors address the limitations of previous algorithmic LLL results, which often required strict "measure regeneration" properties, by introducing tools that work with complex dependencies and arbitrary probability measures.

The Flaw-Action Framework

The core of the framework is the definition of a state space $\Omega$ and a set of flaws $\mathcal{F} = \{f_1, \dots, f_m\}$. A state $\sigma \in \Omega$ is "perfect" if it contains no flaws. For each flaw $f_i$, the algorithm defines a set of actions $A(i, \sigma)$—transitions to new states intended to resolve the flaw.

To analyze the convergence of these searches, the authors utilize Causality Digraphs. These graphs track the potential for an action intended to fix flaw $f_i$ to introduce or "trigger" a new flaw $f_j$. The sparsity and structure of this digraph are primary determinants of the algorithm's efficiency.

Recursive Search and Responsibility Shifting

A key technical innovation is the analysis of a recursive search procedure. Unlike simple Markovian search, which might wander aimlessly, the recursive approach allows the algorithm to "shift responsibility" between flaws. When an action to fix $f_i$ introduces new flaws, the algorithm immediately addresses them recursively before continuing.

Algorithm 1: The Recursive Walk procedure for focused stochastic local search.

As shown in Algorithm 1, the ELIMINATE procedure drives the search, while the recursive ADDRESS procedure ensures that any collateral damage (newly introduced flaws) is handled in a structured manner. This recursive structure is central to the authors' tighter convergence bounds, as it allows for a more granular accounting of how flaws propagate through the state space.

Key Methodological Insights

  • Harmonic Walks: The authors introduce "harmonic" transition probabilities. If one has a target measure $\mu$ over the state space, a harmonic walk moves to a new state with probability proportional to its weight under $\mu$. This generalizes the search beyond simple independent variable models.
  • Flaw Charges ($\gamma_i$): To handle cases where the search does not perfectly regenerate the target measure, the authors introduce "flaw charges." This accounting method quantifies the "cost" of each flaw, allowing the analysis to succeed even in the presence of complex, non-independent constraints.
  • Atomicity: The paper highlights "atomic" action graphs, where fixing a flaw leads to a unique state. Atomicity significantly simplifies the analysis and allows the search to begin from an arbitrary initial state rather than requiring a random sample from $\mu$.

Applications: Acyclic Edge Coloring

The power of this framework is demonstrated through its application to Acyclic Edge Coloring (AEC). An acyclic edge coloring is a proper coloring where no bichromatic cycles exist. The authors prove that any $d$-degenerate graph with maximum degree $\Delta$ has an acyclic edge coloring with $\lceil (2 + \epsilon)\Delta \rceil$ colors, where $\epsilon$ depends on the degeneracy. Crucially, their framework provides a polynomial-time algorithm to find these colorings, reaching bounds that were previously difficult to achieve constructively.

Conclusion

This work provides a robust, unified theory for focused stochastic local search. By moving beyond the restrictive requirements of measure regeneration and providing tools like flaw charges and recursive analysis, the authors have created a framework capable of turning many non-constructive existential proofs into efficient, practical algorithms for hard combinatorial problems.

Summary updated

Abstract

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from the algorithmization of the Lov\'asz Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.
BibTeX
@inproceedings{achlioptas2016focused,
  author = {Dimitris Achlioptas and Fotis Iliopoulos},
  title = {{Focused Stochastic Local Search and the Lovász Local Lemma}},
  booktitle = {SODA},
  year = {2016},
  url = {https://openreview.net/forum?id=MW4ZipZ38La},
}

Loading related content...

Figure