Computing the Independence Polynomial: from the Tree Threshold down to\n the Roots

Nicholas J. A. Harvey, Piyush Srivastava, J. Vondrák

This paper explores the computational boundaries of the independence polynomial, a central object in both combinatorics and statistical physics. The authors provide a deterministic algorithm to approximate this polynomial even when its variables are negative or complex—a regime that is notoriously difficult but deeply connected to the Lovász Local Lemma (LLL).

TL;DR

The authors present a deterministic FPTAS (Fully Polynomial Time Approximation Scheme) for the multivariate independence polynomial in the "Shearer region," where the polynomial is guaranteed to be root-free. This result provides a unifying algorithmic framework for the Lovász Local Lemma and establishes that the computational complexity of the polynomial undergoes a phase transition exactly at the boundary of this region.

What Problem Does This Paper Address?

The independence polynomial $Z(G, \mathbf{z})$ of a graph $G$ is the generating function of its independent sets. In statistical physics, it is known as the partition function of the "hard-core lattice gas" model.

While approximating this polynomial for positive real activities is well-understood (thanks to Weitz’s 2006 work on correlation decay), the case for negative or complex activities remained a major challenge. This isn't just a theoretical curiosity:

  1. Combinatorics: The region where the polynomial has no roots (the Shearer region) defines the maximum possible range of probabilities for which the Lovász Local Lemma—a tool used to prove the existence of rare combinatorial objects—can be applied.
  2. Physics: Complex zeros of partition functions are directly related to phase transitions (Lee-Yang theory).

The authors tackle the problem of efficiently approximating $Z(\mathbf{z})$ when $\mathbf{z}$ lies within this Shearer region, and they investigate the computational hardness of the problem as one approaches the region's boundary.

Methods

The paper builds on Weitz’s correlation decay technique, which uses a recursive tree-like structure to compute "occupation ratios" (the likelihood of a vertex being in an independent set).

The key methodological innovations include:

  • Multivariate Correlation Decay: Unlike previous work that focused on univariate settings (where all vertices have the same activity), this paper handles non-uniform complex parameters.
  • Error Sensitivity Parameter: The authors introduce a novel "error sensitivity parameter" ($\beta$) to track how errors propagate through the recursion. This allows for a direct amortization argument to control errors even when vertex activities are not uniform.
  • Rounding for LLL: To apply their results to the LLL, the authors develop a "rounding" algorithm. It starts with a fractional solution (probabilities) and iteratively fixes variables to 0 or 1 while ensuring the system stays within the Shearer region.
  • Hardness Reductions: They use reductions from counting perfect matchings in regular bipartite graphs to prove #P-hardness for exact evaluation and membership testing.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The results are proven for general graphs $G$ with maximum degree $d$ or bounded connective constants.

Key Insights and Ideas

  • The "Slack" Matters: The running time depends heavily on the "slack" $\alpha$—the distance of the input vector from the boundary of the Shearer region. The authors found that the dependence on $1/\alpha$ in the exponent is $1/\sqrt{\alpha}$, which they prove is optimal for correlation-decay-based methods.
  • Phase Transition in Complexity: The paper shows a beautiful alignment between physics and CS: the point where the polynomial starts having roots (a phase transition in physics) is exactly where the problem of approximating it becomes NP-hard.
  • A New Path to LLL: Traditionally, the LLL is solved via "resampling" (Moser-Tardos). This paper provides a completely different approach based on polynomial evaluation and rounding, viewing the independence polynomial as a "pessimistic estimator" for the probability of avoiding bad events.

Key Results

  • Deterministic FPTAS: For an $n$-vertex graph with max degree $d$, if the activities have slack $\alpha$, $Z(\mathbf{z})$ can be $(1+\epsilon)$-approximated in $(n/\alpha)^{O(\log(d)/\sqrt{\alpha})}$ time.
  • Sub-exponential LLL Algorithm: They provide a deterministic algorithm for the LLL in the "variable model" that runs in sub-exponential time.
  • Membership Testing: They provide an algorithm to test if a vector of probabilities is in the Shearer region within a multiplicative error of $1+\alpha$ in $(n/\alpha)^{O(\sqrt{n/\alpha} \log d)}$ time.
  • Hardness: They prove that exactly evaluating the polynomial at a point in the Shearer region is #P-hard, as is testing exact membership in the region.

Limitations and Future Work

  • Sub-exponential vs. Polynomial: While the algorithm is an FPTAS for fixed slack, the dependence on $1/\alpha$ leads to sub-exponential time in applications like the LLL where $\alpha$ might be $O(1/n)$. A major open question is whether a truly polynomial-time algorithm exists for these cases.
  • The Gibbs Distribution Gap: In the positive activity setting, Markov Chain Monte Carlo (MCMC) methods are very effective because they can sample from the Gibbs distribution. No natural analogue of the Gibbs distribution exists for negative activities, leaving a gap that MCMC currently cannot fill.
  • Connective Constant: While the paper extends results to graphs with bounded connective constants, the constants involved in the runtime are currently quite large.

Summary updated

Abstract

We study an algorithm for approximating the multivariate independence\npolynomial $Z(\\mathbf{z})$, with negative and complex arguments, an object that\nhas strong connections to combinatorics and to statistical physics. In\nparticular, the independence polynomial with negative arguments,\n$Z(-\\mathbf{p})$, determines the Shearer region, the maximal region of\nprobabilities to which the Lovasz Local Lemma (LLL) can be extended (Shearer\n1985). In statistical physics, complex zeros of the independence polynomial\nrelate to existence of phase transitions.\n Our main result is a deterministic algorithm to compute approximately the\nindependence polynomial in any root-free complex polydisc centered at the\norigin. Our algorithm is essentially the same as Weitz's algorithm for positive\nparameters up to the tree uniqueness threshold, and the core of our analysis is\na novel multivariate form of the correlation decay technique, which can handle\nnon-uniform complex parameters. In particular, in the univariate real setting\nour work implies that Weitz's algorithm works in an interval between two\ncritical points $(\\lambda'_c(d), \\lambda_c(d))$, and outside of this interval\nan approximation of $Z(\\mathbf{z})$ is known to be NP-hard.\n As an application, we give a sub-exponential time algorithm for testing\napproximate membership in the Shearer region. We also give a new rounding based\ndeterministic algorithm for Shearer's lemma (an extension of the LLL), which,\nhowever, runs in sub-exponential time. On the hardness side, we prove that\nevaluating $Z(\\mathbf{z})$ at an arbitrary point in Shearer's region, and\ntesting membership in Shearer's region, are #P-hard problems. We also establish\nthe best possible dependence of the exponent of the run time of Weitz's\ncorrelation decay technique in the negative regime on the distance to the\nboundary of the Shearer region.\n
BibTeX
@misc{harvey2016computing,
  author = {Nicholas J. A. Harvey and Piyush Srivastava and J. Vondrák},
  title = {{Computing the Independence Polynomial: from the Tree Threshold down to\textbackslash\{\}n the Roots}},
  year = {2016},
  eprint = {1608.02282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.02282},
}
Figure