On the hardness of sampling independent sets beyond the tree threshold

Elchanan Mossel, Dror Weitz, Nicholas Wormald

Abstract

We consider local Markov chain Monte-Carlo (MCMC) algorithms for sampling from the weighted distribution of independent sets with activity $\lambda$, where the weight of an independent set $I$ is $\lambda^{|I|}$. Recent results have established that Gibbs sampling is rapidly mixing for graphs of maximum degree $d$ when $\lambda < \lambda_c(d)$. This paper investigates the regime where $\lambda > \lambda_c(d)$, establishing that for random $d$-regular bipartite graphs, local MCMC algorithms require exponential time to converge. This provides a fundamental link between the "tree threshold" of statistical physics and the computational complexity of sampling.

Introduction

In the study of combinatorial optimization and statistical physics, the hard-core model serves as a benchmark for understanding the limits of local search and sampling algorithms. The model assigns a weight to every independent set $I$ in a graph proportional to $\lambda^{|I|}$, where $\lambda > 0$ is the activity parameter. As $\lambda$ increases, the distribution places more weight on larger independent sets, eventually making the problem equivalent to finding the maximum independent set—a known NP-hard problem.

The central question in this field is identifying the exact "computational phase transition": the point at which sampling from this distribution shifts from being computationally efficient to being intractable. This paper demonstrates that this transition occurs precisely at the "tree threshold" $\lambda_c(d)$, the point where correlations in the model stop decaying on an infinite $d$-regular tree.

The Tree Threshold and Computational Hardness

Previous research established that for any graph with maximum degree $d$, sampling is efficient if $\lambda < \lambda_c(d)$, where: $$\lambda_c(d) = \frac{(d-1)^{d-1}}{(d-2)^d}$$ This value is derived from the behavior of the hard-core model on an infinite $d$-regular tree. When $\lambda$ is below this threshold, the influence of a vertex's state on distant parts of the tree decays quickly (uniqueness of the Gibbs measure). When $\lambda$ exceeds this threshold, long-range correlations persist.

This paper proves that this physical phase transition is the exact boundary for the efficiency of local MCMC algorithms, such as Glauber dynamics. By analyzing random $d$-regular bipartite graphs, the authors show that as soon as $\lambda > \lambda_c(d)$, these algorithms fail to reach the target distribution in any polynomial time.

Methodology: The Conductance Argument

To prove the exponential slowdown, the authors employ a conductance-based argument. Conductance measures how easily a Markov chain can move between different regions of its state space. If a state space has a "bottleneck"—two large regions connected only by a set of states with very low probability—the Markov chain will take a long time to cross from one region to the other.

The authors demonstrate that for random $d$-regular bipartite graphs (denoted $\mathcal{G}(n, d)$), such a bottleneck emerges when $\lambda > \lambda_c$. These graphs are "locally tree-like," meaning they lack short cycles, but they possess global expansion properties that make them ideal for testing the limits of local algorithms.

Mathematical Techniques

  • First and Second Moment Methods: These are used to estimate the expected weight of independent sets with specific densities on the two partitions of the bipartite graph.
  • Small Subgraph Conditioning: This sophisticated probabilistic technique allows the authors to show that the bottleneck property holds "almost surely" (with probability tending to 1) for random graphs, rather than just in expectation.
  • Gibbs Measures on Trees: The authors explicitly link the occupancy probabilities on infinite trees to the "saddle points" of the weight functions on finite random graphs, providing a rigorous basis for heuristics previously suggested by the "replica method" in physics.

Key Insights: The Bipartite Bottleneck

On a bipartite graph with vertex sets $V_1$ and $V_2$, a high $\lambda$ value forces the Gibbs distribution to concentrate its weight on independent sets that are "unbalanced." Specifically, the distribution favors sets that are dense on $V_1$ and sparse on $V_2$, or vice versa.

For a local algorithm to move from a "$V_1$-heavy" state to a "$V_2$-heavy" state, it must pass through "balanced" independent sets that have roughly equal density on both sides. The authors prove that these balanced sets have exponentially small total probability relative to the unbalanced ones. This creates a massive bottleneck in the state space, leading to a mixing time of $\Omega(a^n)$ for some constant $a > 1$, where $n$ is the number of vertices.

Conclusion and Future Work

This work provides strong evidence for the conjecture that approximating the partition function (the sum of weights of all independent sets) is NP-hard for all $\lambda > \lambda_c(d)$. While the paper rigorously proves that local MCMC algorithms are slow, it does not yet rule out the existence of a non-local, sophisticated algorithm that could bypass the bottleneck.

Furthermore, while the proof currently covers a range of $\lambda$ just above the threshold, extending this to all $\lambda > \lambda_c$ remains a technical challenge due to the complexity of second-moment calculations at higher activities. Future research will likely focus on generalizing these results to other models, such as the Ising model or graph colorings, to further map the landscape of computational phase transitions.

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