Random MAX SAT, random MAX CUT, and their phase transitions

Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. SorkinRandom Struct. Algorithms 2003 · OpenReview

TL;DR

This paper investigates the behavior of optimization problems like MAX 2-SAT and MAX CUT when given random inputs. It reveals a "phase transition" phenomenon, similar to what's observed in decision problems, where the problem's solvability or the quality of the optimal solution dramatically changes around a critical parameter value. The authors provide precise mathematical characterizations of this transition and its surrounding "scaling window."

What Problem Does This Paper Address?

The paper tackles the question of how well we can solve optimization problems on randomly generated instances. Specifically, it focuses on MAX 2-SAT (finding the maximum number of satisfiable clauses in a 2-SAT formula) and MAX CUT (finding the maximum number of edges that can be "cut" by partitioning graph vertices). The core challenge is to understand how the "density" of the random input (e.g., the ratio of clauses to variables in MAX 2-SAT, or edges to vertices in MAX CUT) affects the performance of the optimization. This is analogous to the well-studied "phase transition" in decision problems like 2-SAT, where satisfiability drastically shifts from likely to unlikely as density crosses a critical point. The authors aim to characterize this transition for the optimization versions of these problems.

Methods

The authors employ a combination of established and sophisticated techniques:

  • First-moment method: Used for deriving upper bounds on the expected number of unsatisfied clauses or edges.
  • Algorithmic analysis: Specifically, the "differential equation method" is used for lower bounds, analyzing the behavior of heuristics.
  • Second moment method: Used to establish lower bounds on the probability of certain structures appearing.
  • Coupling arguments: Used to relate the behavior of different random variables or algorithms.
  • Analysis of random walks and branching processes: Crucial for understanding the "scaling window" and the behavior of the system near the phase transition.
  • Leveraging existing results: The paper builds upon and reproduces results from prior work, particularly on the 2-SAT scaling window ([BBC+01]).

Datasets

Not discussed in the paper. The paper deals with theoretical analysis of random instances of combinatorial problems, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Optimization problems exhibit phase transitions: Just like decision problems, MAX 2-SAT and MAX CUT show a sharp change in behavior (e.g., the number of satisfiable clauses or cut edges) as a parameter like "density" crosses a critical value.
  • The "scaling window" is crucial: The region around the phase transition (e.g., density 1 ± Θ(n⁻¹/³)) is particularly interesting and requires more advanced analysis, revealing subtle behavior.
  • MAX CUT and MAX 2-SAT share structural similarities: Despite being different problems, their random instances exhibit analogous phase transition phenomena, suggesting deeper connections.
  • Optimization problems might be easier to analyze than decision problems: The authors suggest that the smoother nature of optimization quantities could make them more amenable to analysis.
  • A connection between optimization and decision thresholds: The paper conjectures a link between the threshold for satisfiability and the limit of the expected fraction of satisfiable clauses.

Key Results

  • MAX 2-SAT:
    • For density $c < 1$, the expected number of unsatisfied clauses is $O(1/n)$.
  • In the "scaling window" $c = 1 \pm \Theta(n^{-1/3})$, the number of unsatisfied clauses is $\Theta(1)$.
  • For density $c > 1$, the number of unsatisfied clauses is $\Theta(n)$.
  • Precise bounds are given for various regimes, including $c \to \infty$ and $c = 1 + \epsilon$.
  • MAX CUT:
    • Analogous phase transition behavior is observed around $c = 1/2$ (for edge density).
  • Results are presented for subcritical ($c < 1/2$), high-density ($c > 1/2$), and scaling window regimes.
  • For large $c$, the expected number of cut edges is approximately $(c + \sqrt{c})n$.

Limitations and Future Work

  • Logarithmic gaps: For some regimes (e.g., low-density MAX 2-SAT and MAX CUT), there's a logarithmic gap between the derived lower and upper bounds, suggesting room for improvement.
  • Conjectures: The paper poses several conjectures, including a "MAX SAT limiting function conjecture" (whether the expected fraction of satisfiable clauses converges to a limit) and a connection between optimization and decision thresholds. These remain open problems.
  • MAX k-SAT and MAX CSP: Results are more limited for $k > 2$, reflecting a general lack of understanding for these problems.
  • ONLINE MAX 2-SAT: While an optimal algorithm for one version is found, the analysis for another version (ONLINE II) is left as an open problem.
  • Exact asymptotics: The authors express a desire to obtain exact asymptotic formulas for quantities like $f(n, cn)/(cn)$, which would be a significant achievement.

Summary updated

Abstract

With random inputs, certain decision problems undergo a “phase transition.” We prove similar behavior in an optimization context. Given a conjunctive normal form (CNF) formula F on n variables and wi...
BibTeX
@inproceedings{coppersmith2003random,
  author = {Don Coppersmith and David Gamarnik and Mohammad Taghi Hajiaghayi and Gregory B. Sorkin},
  title = {{Random MAX SAT, random MAX CUT, and their phase transitions}},
  booktitle = {Random Struct. Algorithms},
  year = {2003},
  url = {https://openreview.net/forum?id=NvFi6DNK3Tgs},
}
Figure