On the Satisfiability Threshold of Random Community-Structured SAT

Dina Barak-Pelleg, Daniel BerendIJCAI 2018 · DOI

TL;DR

This paper introduces and analyzes a new model for "community-structured" random SAT instances, which better reflects real-world industrial SAT problems. The key finding is that this community structure tends to lower the satisfiability threshold compared to standard random SAT, and can even cause it to vanish under certain conditions.

What Problem Does This Paper Address?

The Boolean Satisfiability Problem (SAT) is a fundamental problem in computer science, asking whether a given Boolean formula can be satisfied by assigning truth values to its variables. A major area of research is understanding the "satisfiability threshold" for random SAT instances. This threshold is a critical point: below it, random instances are likely satisfiable (SAT), and above it, they are likely unsatisfiable (UNSAT).

While the threshold is well-understood for 2-SAT (where it's exactly 1), it remains a conjecture for higher clause lengths (k-SAT). Crucially, standard random SAT models, where clauses are chosen uniformly and independently, are often criticized for not accurately representing real-world "industrial" SAT instances. Industrial instances often exhibit a "community structure" where variables are grouped, and clauses tend to involve variables from the same community. This paper aims to bridge this gap by studying the satisfiability threshold in a random SAT model that explicitly incorporates this community structure.

Methods

The authors define a "community-structured SAT" model where the set of $n$ variables is partitioned into $B$ disjoint communities, each of size $h$. Clauses are then generated based on these communities. Specifically, clauses can be formed by selecting variables from a single community or from multiple distinct communities. The paper uses a probabilistic framework to analyze the satisfiability of instances generated by this model.

Key techniques include:

  • Probabilistic Analysis: Analyzing the probability of satisfiability as the number of variables $n$ grows.
  • Threshold Analysis: Identifying critical values of the "density" (ratio of clauses to variables) where the problem transitions from likely SAT to likely UNSAT.
  • Balls and Bins Analogy: Using the classic balls and bins problem to analyze the distribution of clauses across communities, particularly for analyzing the "maximum load" (maximum number of clauses within a single community).
  • Asymptotic Analysis: Examining the behavior of the satisfiability threshold as $n \to \infty$.

The paper builds upon existing results for random k-SAT, particularly concerning the threshold $\gamma_k$ and $\gamma_k^*$, and extends them to the community-structured setting.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of a generative model rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Community Structure Lowers the Threshold: The most significant finding is that the presence of community structure, especially when communities are small and clauses tend to stay within communities, generally lowers the satisfiability threshold compared to standard random SAT. This means that community-structured instances become unsatisfiable at lower densities.
  • Vanishing Threshold: Under specific conditions (e.g., very small communities and a certain clause generation probability), the satisfiability threshold can effectively vanish, meaning instances become unsatisfiable even at very low densities.
  • Divergence from Standard SAT: The paper highlights how community structure can lead to fundamentally different satisfiability behavior than predicted by standard random SAT models. This underscores the importance of modeling real-world instance characteristics.
  • Role of Community Size: The size of the communities ($h(n)$) plays a crucial role. Smaller communities tend to decrease the threshold, while larger communities can lead to behavior closer to standard random SAT.

Key Results

The paper presents several theorems and propositions detailing the asymptotic satisfiability of community-structured SAT instances under various conditions on community size ($h(n)$), number of communities ($B$), and clause generation probabilities ($P$).

  • Proposition 3.1: Confirms that for clauses of length at most $k$, if the density $\alpha > 2^k \ln 2$, the instance is UNSAT w.h.p. This aligns with standard random SAT results. It also shows that if clauses are restricted to a single community ($P=P(k)$), the threshold $\alpha$ is $r_k$ (the standard k-SAT threshold), but if $h(n)=O(n)$ and $\alpha < r_k$, it's SAT w.h.p.
  • Theorem 3.2: This is the core result, showing that under certain conditions (e.g., $h(n)=o(1)$ and specific clause densities), the threshold can be significantly lower than $r_k^*$, and in some cases, can even vanish (effectively becoming 0). For instance, if $h(n)=o(\ln n)$ and the density is sufficiently high, the instance is UNSAT w.h.p.
  • Theorem 3.6: Focuses on the 2-SAT case with community structure. It provides a detailed analysis showing how the threshold depends on both density ($\alpha$) and community size ($h(n)$), demonstrating that smaller communities lead to lower thresholds. For example, if $h(n) = o(\sqrt{n})$ and $\alpha > 1 - \epsilon_0$, the instance is UNSAT w.h.p.

Limitations and Future Work

  • Simplified Community Model: The authors acknowledge that their model assumes communities are of the same size ($h(n)$) for analytical simplicity. They suggest future work should explore models with varying community sizes.
  • Other Industrial Features: The paper mentions other characteristics of industrial SAT instances, such as scale-free structures (variables selected according to power-law distributions), which are not included in this model. Future work could incorporate these.
  • Probability of Variable Selection: The paper assumes a uniform probability for selecting variables within communities. Investigating how different probabilities of variable selection from communities affect the threshold is a natural extension.
  • Experimental Validation: While the paper provides theoretical results, empirical validation of these findings on generated or real-world industrial SAT instances would be valuable.

Summary updated

BibTeX
@inproceedings{barakpelleg2018satisfiability,
  author = {Dina Barak-Pelleg and Daniel Berend},
  title = {{On the Satisfiability Threshold of Random Community-Structured SAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/174},
}
Figure