PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Viresh Patel, Guus Regts

arXiv:1607.01167v3math.COcs.CCcs.DMcs.DS

TL;DR

The paper asks how to deterministically approximate complex-valued graph-polynomial evaluations on bounded-degree graphs. It combines zero-free regions with Taylor approximation and efficient coefficient computation, yielding polynomial-time algorithms for several graph polynomials and partition functions, with some results limited relative to existing methods.

  • Problem

    Efficient approximation is sought for graph-polynomial evaluations arising from counting problems, including complex-valued evaluations on bounded-degree graphs.

  • Method

    The paper casts evaluation as univariate polynomial approximation, uses zero-free regions to truncate the logarithm’s Taylor series, and computes the required coefficients efficiently.

  • Results

    The approach gives deterministic polynomial-time approximation algorithms for the independence and Tutte polynomials and partition functions of spin and edge-coloring models on bounded-degree graphs.

  • Takeaways & Limitations

    The work establishes an explicit connection between absence of complex roots and efficient approximation, including a connection to conjectures about zero-free regions and coloring counts.

  • Takeaways & Limitations

    Theorem 1.1 does not cover λ in the interval λ* ≤ λ < λc, although correlation decay can approximate the independence polynomial there.

Abstract

from arXiv · show

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials $\mathcal C$ and show that if $p\in \cal C$ and there is a disk $D$ centered at zero in the complex plane such that $p(G)$ does not vanish on $D$ for all bounded degree graphs $G$, then for each $z$ in the interior of $D$ there exists a deterministic polynomial-time approximation algorithm for evaluating $p(G)$ at $z$. This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated by. Barvinok, which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems.

1 Introduction

The paper develops a robust deterministic polynomial-time approach for approximating complex evaluations of graph polynomials on bounded-degree graphs. Its central connection is that zero-free regions yield efficient approximation algorithms, including results for independence and Tutte polynomials and spin and edge-coloring partition functions.

  • Motivation: The paper targets efficient approximation of graph polynomials and partition functions associated with counting independent sets, colorings, and matchings.These evaluations arise in computational counting and statistical physics.
  • Contribution: The approach provides a general deterministic polynomial-time method for complex-valued evaluations on bounded-degree graphs, complementing randomized and correlation-decay methods.It applies to a large class of graph polynomials and partition functions.
  • Zero-free regions: Absence of complex roots is explicitly connected to efficient evaluation, including a link between Sokal’s chromatic-polynomial conjecture and approximating proper colorings.The connection relates zero-free regions to a notorious bounded-degree counting problem.
  • Method: The method reduces evaluation to a univariate polynomial, approximates its logarithm with an O(log n)-order Taylor expansion, and computes the needed coefficients in polynomial time.The main technical contribution is efficient computation of essentially the first O(log n) coefficients for bounded-degree graphs.
  • Results: The paper obtains deterministic FPTAS results for the independence polynomial, Tutte polynomial, and partition functions of spin and edge-coloring models.These results concern bounded-degree graphs.
  • Independence polynomial: For claw-free graphs, every non-real-negative λ admits a deterministic multiplicative ε-approximation in time (|V|/ε)O(1).For general maximum-degree-∆ graphs, Theorem 1.1 gives the same form of approximation when |λ| < λ*(∆), while the positive-λ range can be weaker than Weitz’s result.
  • Other models: The framework also yields deterministic polynomial-time approximations for Tutte evaluations and complex spin and edge-coloring models under stated bounded-degree conditions.Examples include sufficiently large |q| for the Tutte polynomial and interaction weights close to 1 for the model partition functions.

2 Approximating evaluations of polynomials

The section explains how zero-free disks enable multiplicative approximation through Taylor approximation of the logarithm. The required Taylor data can be obtained from inverse power sums, reducing polynomial evaluation to computing only O(log(d/ε)) coefficients or power sums.

  • Taylor approximation: Barvinok’s method approximates a polynomial by truncating the Taylor series of its logarithm around zero.The logarithm is defined on a zero-free disk after fixing a branch at p(0).
  • Inverse power sums: The logarithmic derivatives are expressed through the roots of the polynomial, producing inverse power sums that encode the needed Taylor coefficients.For roots ζ_i, the derivatives involve sums of powers of (−ζ_i)^−1.
  • Approximation guarantee: If a degree-d polynomial has no roots in the disk of radius M, truncating its logarithm at m = C ln(d/ε) yields a multiplicative ε-approximation at any |t| < M.The constant satisfies C = C(t,M) ≤ (1 − |t|/M)^−1.
  • Algorithmic reduction: Efficient computation of the first O(ln(deg(p))) inverse power sums is essentially equivalent to efficient computation of the first O(ln(deg(p))) coefficients.This is the bridge from analytic approximation to algorithmic computation.
  • Complexity: Given a0 and inverse power sums computable in time τ(r), the polynomial can be multiplicatively approximated in time O(τ(m)), with m = C ln(d/ε).The guarantee assumes that p has no roots in the open disk of radius M and |t| < M.

3 Computing coefficients of graph polynomials

This section develops a deterministic polynomial-time method for computing low-order inverse power sums and coefficients of bounded induced graph counting polynomials on bounded-degree graphs. The method reduces coefficient computation to efficiently enumerating and counting small connected induced subgraphs.

  • The main technical contribution computes inverse power sums, and hence coefficients, for a large class of graph polynomials on bounded-degree graphs.The results do not require assumptions about polynomial root locations in this section.
  • A bounded induced graph counting polynomial is multiplicative, has bounded induced-subgraph coefficient representations, and permits efficient computation of the associated coefficients.The defining conditions include bounds on coefficient structure and an algorithm for computing λ_H,i.
  • The independence polynomial is a BIGCP, so the framework applies to its coefficients.For bounded-degree graphs, the resulting method computes coefficients for i = O(ln n) in polynomial time rather than quasi-polynomial brute force time.
  • 3.1 Induced subgraph counts: For a connected k-vertex graph H, induced-subgraph detection takes O(n∆^k−1) time and counting takes O(k^2n^2∆^2(k−1)) time.These procedures exploit bounded maximum degree to enumerate candidate embeddings and remove repetitions.
  • 3.1 Induced subgraph counts: Connected induced subgraphs of size at most k can be enumerated in O(n^2k^7(e∆)^2k) time.The enumeration supports the coefficient algorithm by generating the small connected induced subgraphs occurring in the input graph.
  • For m = C ln(n/ε), all inverse power sums and the coefficients a_H,k can be computed deterministically in (n/ε)^O(1) time.The algorithm lists the relevant coefficients for all k = 1, …, m and then computes the inverse power sums for bounded-degree inputs.

4 The independence polynomial

The section develops deterministic approximation algorithms for the independence polynomial on bounded-degree graphs, including complex evaluations and extensions to claw-free and multivariate settings. The method combines zero-free regions with efficient computation of low-order coefficients or inverse power sums.

  • 4.1 The independence polynomial on bounded degree graphs: A zero-free disk for the independence polynomial yields a deterministic multiplicative ε-approximation algorithm on bounded-degree graphs.The algorithm computes the first O(log(n/ε)) inverse power sums and runs in time (n/ε)O(1).
  • 4.1 The independence polynomial on bounded degree graphs: The approach evaluates a univariate polynomial, approximates its logarithm by a low-order Taylor expansion, and computes the required coefficients efficiently.The Taylor approximation has order log n, while the first O(log n) coefficients are obtained through inverse power sums.
  • 4.2 The even independence polynomial: The even independence polynomial Ze(G)(λ) also admits a deterministic multiplicative ε-approximation in time (|V|/ε)O(1).The proof combines approximations to Z(G)(λ) and Z(G)(−λ), using their common positivity on the relevant interval.
  • 4.3 Multivariate and claw-free extensions: For multivariate evaluations, a univariate substitution and vertex-colored BIGCP representation enable efficient approximation when every |zv| is below λ∗(∆).The resulting polynomial is nonzero on a disk containing the target point, allowing q(G)(1), and hence the multivariate independence polynomial, to be approximated efficiently.
  • 4.3 The independence polynomial on claw-free graphs: For claw-free graphs, the independence polynomial can be approximated deterministically at every complex λ that is not a negative real number.This uses the fact that all roots are negative real and a polynomial transformation that preserves a suitable zero-free disk.
  • 4.3 The independence polynomial on claw-free graphs: The running-time exponent depends on |λ| and initially grows exponentially with it, although the dependence can be reduced to O(|λ|1/2).The improvement follows by adapting the polynomial-transformation lemma described by Barvinok.

5 The Tutte polynomial

The section applies the zero-free-region framework to the Tutte polynomial by transforming evaluations near large q into evaluations near zero. This yields deterministic polynomial-time approximation algorithms on bounded-degree graphs.

  • 5 The Tutte polynomial: For every fixed degree bound ∆ and complex w, sufficiently large |q| admit deterministic multiplicative ε-approximation of ZT(G)(q,w) in time (|V|/ε)O(1).The threshold K depends on ∆ and w, and the result applies to loopless multigraphs.
  • 5 The Tutte polynomial: The proof defines a transformed degree-n polynomial pT whose evaluation at 1/q can be converted into an approximation of ZT(G)(q,w).If x approximates pT(G)(1/q), then q^n x approximates the Tutte evaluation with the same multiplicative accuracy.
  • 5 The Tutte polynomial: The transformed Tutte polynomial is shown to be a BIGCP, enabling efficient computation of its first m inverse power sums.The required number is m = C ln(n/ε), after which Corollary 2.3 supplies the approximation.
  • 5 The Tutte polynomial: The BIGCP property follows because coefficients of the transformed polynomial can be expressed through induced subgraph counts computable by enumerating edge subsets.For a graph H, the relevant coefficient computation takes time O(2^{|E(H)|}) = O(2^{∆|V(H)|}).

6 Partition functions of spin models

The section extends the framework to partition functions of spin models and graph homomorphisms with multiplicities. Near the all-ones interaction matrix, deterministic polynomial-time approximation follows from a univariate interpolation and zero-free region.

  • 6.1 Partition functions of spin models: The spin-model formulation includes ordinary spin systems as the special case in which all edge matrices are identical.The general formulation allows edge-dependent symmetric matrices.
  • 6.1 Partition functions of spin models: The proof replaces the original partition function by a univariate polynomial q with q(G)(0)=1 and q(G)(1)=k^−|V|p(G)(A).A zero-free disk |z| ≤ 1+δ then permits approximation of q(G)(1) through low-order inverse power sums.
  • 6.1 Partition functions of spin models: The coefficient computation treats q as an edge-colored BIGCP, using induced edge-colored subgraphs of at most 2i vertices for the coefficient of zi.The resulting computation is polynomial-time for fixed k and bounded degree.
  • 6.2 Partition functions of graph homomorphisms with multiplicities: For graph homomorphisms with multiplicities, the same strategy gives a deterministic algorithm when |Ae_i,j−1| ≤ 0.1/∆.The input includes a composition µ of |V| into k parts and symmetric edge matrices.

7 Partition functions of edge-coloring models

The section handles edge-coloring partition functions with vertex-dependent signatures by introducing fragments and extending the BIGCP coefficient machinery. This yields deterministic approximation algorithms under a zero-free condition near the all-ones signature.

  • 7.1 Partition functions for vertex-colored graphs: The partition-function problem is transformed into evaluating a degree-at-most-|V| univariate polynomial q at 1, with q(G)(1)=k^−|E|p(G)(H).A zero-free disk |z| ≤ 1+δ supports the Barvinok approximation step.
  • 7.1 Partition functions for vertex-colored graphs: Direct application of the earlier BIGCP theorem is insufficient because efficient computation of the coefficients λH,i is unclear when signatures vary by vertex.The proof therefore introduces additional fragment-based machinery.
  • 7.2 Computing coefficients of q(G)(z): A fragment records a vertex-colored graph together with the number of half edges incident to each vertex, capturing edges that leave a selected vertex set.Fragment isomorphism preserves both vertex colors and half-edge counts.
  • 7.2 Computing coefficients of q(G)(z): The coefficients of q(G) can be expressed using ind∗ counts of fragments, allowing the inverse-power-sum algorithm to be extended from graphs to fragments.Theorem 7.2 computes the first m = C ln(n/ε) inverse power sums deterministically in (n/ε)O(1) time.
  • 7.2 Computing coefficients of q(G)(z): Fragment isomorphism and induced-fragment counts are computable in polynomial time for bounded-degree inputs.For connected fragments on k vertices, the stated algorithm runs in O(k^2n^2∆^{2(k−1)}) time.

8 Concluding remarks and open questions

The paper connects zero-free regions of graph polynomials with deterministic approximation algorithms, while identifying scope limits and open extensions. Its results also sharpen the relationship between approximation thresholds, complex roots, and computational hardness.

  • The paper gives deterministic polynomial-time approximation algorithms for the Tutte, independence, spin-model, and edge-coloring graph polynomials on bounded-degree graphs.
  • Combining the paper’s methods with a later zero-free result yields efficient approximation of the independence polynomial for λ < λc, providing a different proof of Weitz’s result.
  • The approach would imply efficient approximate counting of (∆ + 1)-colorings on maximum-degree-∆ graphs if Sokal’s stated zero-free conjecture holds.
  • Approximation becomes NP-hard for the independence polynomial when λ < −λ∗(∆), near a sequence of bounded-degree trees whose evaluations vanish.
  • The authors note that their bounded-degree inverse-power-sum method does not appear to apply to permanents of general matrices.
  • The method’s graph-polynomial coefficient restriction leaves extension to all graphs H as a separate question, although later work reportedly extends the algorithm beyond that restriction.
  • An open problem asks whether the number of independent sets of size k in bounded-genus graphs can be computed in time 2^O(k)|V(G)|^O(1), while another asks for a zero-free region for the Tutte polynomial.
Loading 1607.01167v3…