On the hardness of sampling independent sets beyond the tree threshold

Elchanan Mossel, Dror Weitz, Nicholas Wormald

TL;DR

This paper provides a rigorous proof that local sampling algorithms, such as Markov Chain Monte Carlo (MCMC), fail to be efficient once a specific physical phase transition is crossed. Specifically, for random bipartite $d$-regular graphs, the authors show that sampling independent sets becomes exponentially slow the moment the activity parameter $\lambda$ exceeds the critical threshold for "uniqueness" on an infinite tree.

What Problem Does This Paper Address?

The paper investigates the computational complexity of sampling from the hard-core model. In this model, we look at independent sets of a graph—collections of vertices where no two are connected by an edge. Each set $I$ is assigned a weight proportional to $\lambda^{|I|}$, where $\lambda$ is an "activity" parameter.

In statistical physics and computer science, a central question is: When can we efficiently sample an independent set from this weighted distribution?

Earlier work established that if $\lambda$ is small (below a critical value $\lambda_c$), we can sample efficiently using local algorithms like Glauber dynamics (a type of MCMC). However, it was long conjectured that once $\lambda$ crosses $\lambda_c$—the point where a phase transition occurs on an infinite tree—sampling on finite graphs would become computationally "hard." This paper aims to prove that this physical threshold is indeed a fundamental barrier for local sampling algorithms.

Methods

The authors employ a combination of probabilistic and combinatorial techniques to analyze the mixing time (the time it takes for an algorithm to reach its stationary distribution) of local MCMC algorithms.

  1. Conductance and Bottlenecks: To prove slow mixing, the authors show the existence of a "bottleneck" in the state space. They demonstrate that the probability distribution becomes "bimodal" above $\lambda_c$, concentrating on independent sets that are heavily biased toward one side of the bipartite partition or the other.
  2. First and Second Moment Methods: They calculate the expected weight of independent sets with specific densities (the first moment) and the variance of these weights (the second moment) across the space of random graphs.
  3. Small Graph Conditioning: A sophisticated technique used to handle the variance introduced by short cycles in random regular graphs, ensuring that the "bottleneck" exists with high probability rather than just on average.
  4. Tree-Graph Comparison: They bridge the gap between the behavior of Gibbs measures on infinite trees and the behavior on "locally tree-like" random graphs.

Datasets

As a theoretical computer science and probability paper, it does not use empirical datasets. Instead, it uses a mathematical model: Random bipartite $d$-regular graphs (where every node has exactly $d$ neighbors). The results are proven to hold "asymptotically almost surely," meaning the probability of the result being true approaches 1 as the number of vertices $n$ goes to infinity.

Key Insights and Ideas

  • The "Aha" Moment: The critical threshold for the infinite tree ($\lambda_c$) is exactly where the global structure of a random graph starts to matter. While the graph looks like a tree locally, its "expander" properties create a massive barrier between different types of independent sets.
  • Phase Transition as a Computational Barrier: The paper reinforces the deep link between statistical physics (phase transitions) and computer science (computational hardness). It suggests that the "uniqueness" of a measure on a tree is the "right" way to think about the limits of efficient sampling.
  • Rigorous "Replica" Justification: In physics, the "replica method" is a heuristic used to predict graph behavior based on tree models. This paper provides a rigorous mathematical foundation for those heuristics in the context of the hard-core model.

Key Results

  • Exponential Mixing Time: For any $d \ge 3$, if $\lambda$ is just above the critical threshold $\lambda_c(d)$, the mixing time for Glauber dynamics (and any other local MCMC algorithm) on a random bipartite $d$-regular graph is exponential in the number of vertices $n$.
  • Formal Bound: The mixing time is $\Omega(a^n)$ for some constant $a > 1$.
  • Universality: This result applies to any local dynamics that updates only a small fraction ($o(n)$) of the nodes at each step.

Limitations and Future Work

  • Range of $\lambda$: The proof specifically covers the region where $\lambda$ is "just above" $\lambda_c$. While the authors conjecture that the result holds for all $\lambda > \lambda_c$, the current second-moment calculations are most tractable near the threshold.
  • NP-Hardness Conjecture: The authors prove that local MCMC is slow, but they conjecture a much stronger result: that for $\lambda > \lambda_c$, it is NP-hard to even approximately count independent sets (i.e., no efficient algorithm of any kind exists, not just MCMC).
  • Graph Structure: The results are specific to random bipartite $d$-regular graphs. Extending these proofs to more general graph classes remains an open challenge.

Summary updated

Abstract

We consider local Markov chain Monte-Carlo algorithms for sampling from the weighted distribution of independent sets with activity $ł$, where the weight of an independent set $I$ is $ł^{|I|}$. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree $d$ and $łł_c$ it is NP-hard to approximate the above weighted sum overindependent sets to within a factor polynomial in the size of the graph.
BibTeX
@inproceedings{mossel2008hardness,
  author = {Elchanan Mossel and Dror Weitz and Nicholas Wormald},
  title = {{On the hardness of sampling independent sets beyond the tree threshold}},
  booktitle = {Probability},
  year = {2008},
  doi = {10.1007/s00440-007-0131-9},
}
Figure