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

Introduction

Computational counting is an important area of computer science where one seeks to find efficient algorithms to count certain combinatorial objects such as independent sets, proper colorings, or matchings in a graph. More generally, each combinatorial counting problem has an associated generating function, namely the independence polynomial for independent sets, the chromatic and more generally Tutte polynomial for proper graph colorings, and the matching polynomial for matchings. Such graph polynomials are studied in mathematics and computer science, but also in statistical physics where they are normally referred to as partition functions. A fundamental question asks for which graphs and at which numerical values one can approximately evaluate these polynomials efficiently. Indeed the counting problems correspond to evaluating these graph polynomials or partition functions at particular values.

Many of these counting problems are known to be computationally hard in the sense of being #P-hard, even when one restricts to graphs of maximum degree at most three . On the other hand several efficient randomized approximation algorithms exist for some of these #P-hard problems via the use of the powerful Markov chain Monte Carlo technique. In a major breakthrough, Weitz , inspired by ideas from statistical physics, developed the so-called correlation decay method allowing him to obtain the first efficient deterministic approximation algorithm for counting independent sets in graphs of maximum degree at most five. (One expects no such algorithm for graphs of maximum degree larger than five , while previously the best known (randomized) algorithm worked only for graphs of maximum degree at most four.) The correlation decay method has subsequently been refined and applied to various other problems; see e.g. and references therein.

In this paper we consider a different approach. The approach is quite robust in that it can be applied to a large class of graph polynomials and gives the first general polynomial-time method to approximate graph polynomials at complex values for bounded degree graphs. Very recently complex evaluations have also been considered by Harvey, Srivastava, and Vondrák for the special case of the independence polynomial. Complex evaluations of graph polynomials, aside from being the natural extensions of real evaluations, arise as interesting counting problems e.g. counting restricted tensions or flows can be modelled as the partition functions of a complex spin system (see ) and the number of homomorphisms into any fixed graph can be modelled as the partition function of a complex edge-coloring model (see ).

A further important aspect of our work is to highlight the explicit relation between the (absence of complex) roots of a graph polynomial and efficient algorithms to evaluate it. Indeed, in Remark 1.3 below we give the explicit connection between a conjecture of Sokal on zero-free regions of the chromatic polynomial and the notorious algorithmic problem of efficiently approximating the number of proper colorings in a bounded degree graph.

Our approach combines a number of ingredients including ideas from sparse graph limits , results on the locations of zeros of graph polynomials and partition functions and an algorithmic development due to Barvinok . The Taylor approximation technique of Barvinok has been used to construct deterministic quasi-polynomial-time approximation algorithms for evaluating a number of graph partition functions (for general graphs); see e.g. work by Barvinok , by Barvinok and Sobeŕon , and by the second author . We refer to Barvinok’s recent book for more background.

The approach can be roughly described as follows. First the problem of evaluating the partition function or graph polynomial is cast as the evaluation of a univariate polynomial. Next, a region is identified where this polynomial does not vanish; hence in this region the logarithm of the polynomial is well-approximated by a low-order Taylor approximation (of order $\log n$, where $n$ in the degree of the polynomial). Finally we must compute this Taylor approximation by efficiently computing the first $O(\log n)$ coefficients of the polynomial. So far this approach has only resulted in algorithms that run in quasi-polynomial time. The main technical contribution of the present paper is a polynomial-time algorithm for computing (essentially) the first $O(\log n)$ coefficients of a large class of graph polynomials whenever we work with bounded degree graphs cf. Theorem 3.1, and we believe it to be of independent interest.

Below we shall state and discuss some concrete results that can be obtained by combining this approach with (known) results on the location of roots of graph polynomials and partition functions. In particular, we obtain new deterministic polynomial-time algorithms (FPTAS) for evaluating the independence polynomial, the Tutte polynomial, and computing partition functions of spin and edge-coloring models in the case of bounded degree graphs. Before we state our algorithmic results, we first need a definition. Since we will approximate polynomials at complex values, we define what it means to be a good approximation.

The independence polynomial of a graph $G=(V,E)$ is denoted by $Z(G)$ and is defined as

In Weitz proved, based on the correlation decay method, that if $0\leq\lambda<\lambda_{c}$, where

then there exists a deterministic algorithm, which given a graph $G=(V,E)$ of maximum degree at most $\Delta$ and $\varepsilon>0$, computes a multiplicative $\varepsilon$-approximation to $Z(G)(\lambda)$ in time $(|V|/\varepsilon)^{O(1)}$. Sly and Sun proved this is tight by showing that, as soon as $\lambda>\lambda_{c}$, one cannot efficiently approximate $Z(G,\lambda)$ unless NP=RP.

In Section 4 we prove the following result, which has been independently obtained by Harvey, Srivastava and Vondrák using the correlation decay method.

From the proof of Theorem 1.1 it follows that the running time is in fact bounded by

for some absolute constants $D,D^{\prime}$.

Theorem 1.1 in fact also applies to the multivariate independence polynomial, as we will briefly explain in Subsection 4.2.

For positive valued $\lambda$ our result is weaker than Weitz’s result since $\lambda_{c}>\lambda^{*}$. However our result works for negativeIn an unpublished note Srivastava notes that the correlation decay method of Weitz in fact also applies to negative $\lambda$ as long as $\lambda>-\lambda^{*}$. and even complex $\lambda$. The case $\lambda<0$ is relevant due to its connection to the Lovász local lemma, cf. . We remark here that by very recent results of Peters and the second author confirming a conjecture of Sokal , and by the method from Subsection 4.3 below, we are able to obtain an alternative proof of Weitz’s result. We say more about this in Section 8.

As an extension to Theorem 1.1, we are able to efficiently approximate the independence polynomial on almost the entire complex plane for the special class of claw-free graphs. We make use of a result of Chudnovsky and Seymour stating that the independence polynomial of a claw-free graph has only negative real roots. We prove the following result in Subsection 4.3.

Note that when $G$ is the line graph of some graph $H$ we have that $Z_{G}(\lambda)$ is equal to the matching polynomial of $H$. So in particular, Theorem 1.2 implies a result of Bayati, Gamarnik, Katz, Nair, and Tetali . Our proof of it however is entirely different from the proof in .

2 The Tutte polynomial

The random cluster formulation of the Tutte polynomial of a graph $G=(V,E)$ is a two-variable polynomial, which is denoted by $Z_{T}(G)$ and is defined by

where $k(A)$ denotes the number of components of the graph $(V,A)$. In particular, if $w=-1$, $Z_{T}(G)(q,-1)$ is equal to the chromatic polynomial of $G$.

Jerrum and Sinclair showed that when $q=2$ and $w>0$ there exists a randomized polynomial-time approximation algorithm for computing evaluations of the Tutte polynomial in general. In Goldberg and Jerrum showed that approximating evaluations of the Tutte polynomial on general graphs for $q>2$ and $w>0$ is as hard as counting independent sets in bipartite graphs and in Goldberg and Jerrum showed that for several choices of real parameters $(q,w)$ it is even #P-hard to approximate the evaluation of the Tutte polynomial on general graphs. Goldberg and Guo looked at the complexity of approximately evaluating the Tutte polynomial for general graphs at complex values.

We will consider the Tutte polynomial as a univariate polynomial by considering $w$ to be constant. In Section 5 we prove the following result.

From the proof the Theorem 1.3 it follows that the running time is in fact bounded by

for some absolute constants $D,D^{\prime}$.

The constant $K$ in the theorem above comes from a paper of Jackson, Procacci and Sokal and unfortunately takes half a page to state exactly. However, when $w$ satisfies $|1+w|\leq 1$ (this includes the chromatic polynomial), the constant $K$ may be taken to be $6.91\Delta$.

Sokal [30, Conjecture 21] conjectured that $Z_{T}(G)(q,-1)\neq 0$ as long as $\Re(q)>\Delta(G)$. Combined with our results (and the technique from Section 4.3) a confirmation of the conjecture would imply an efficient approximation algorithm for computing the number of $(\Delta+1)$-colorings of any graph $G$ of maximum degree at most $\Delta$, a notorious problem in computational counting.

3 Partition functions of spin models

If $A$ is the adjacency matrix of some graph $H$, then $p(G)(H)$ is equal to the number of graph homomorphisms from $G$ to $H$. In $p(G)(A)$ is called the graph homomorphism partition function.

Building on a line of research started by Dyer and Greenhill and Bulatov and Grohe , a full dichotomy theorem has been proved for the complexity of exactly computing the partition function of a complex spin model by Cai, Chen and Lu . This dichotomy essentially says that computing the partition function of $A$ exactly is #P hard unless the matrix $A$ has some special structure.

Building on the work of Barvinok and Sobéron we prove in Section 6 the following result.

The constant $0.34$ can be replaced by $0.45$ if $\Delta\geq 3$, and by $0.54$ if $\Delta$ is large enough, cf. .

In Barvinok and Soberón introduced partition functions of graph homomorphisms of $G$ with multiplicities and gave a quasi-polynomial-time algorithm for computing them for certain matrices. In Section 6 we will show that our results also apply to these partition functions.

4 Partition functions of edge-coloring models

Just as for partition functions for spin models much work has been done to establish a complexity dichotomy result for exactly computing Holant problems; see . Not much is known about the complexity of approximating partition functions of edge-coloring models except for a few special cases. As already mentioned, Bayati, Gamarnik, Katz, Nair, and Tetali found an efficient approximation algorithm for counting matchings in bounded degree graphs and Lin, Liu and Lu found efficient approximation algorithms for counting edge covers. Both of these algorithms are based on the correlation decay method.

Building on work of the second author we will prove the following result in Section 7.

The constant $0.35$ may be replaced by $0.47$ if $\Delta\geq 3$ and by $0.56$ if $\Delta$ is large enough; see . Moreover, for readers familiar with the orthogonal group invariance of these partition functions, it is interesting to note that one can use Corollary 6b from to find a much larger family of edge-coloring models for which the partition function can be efficiently approximated.

5 Organization

In the next section we shall consider an algorithm due to Barvinok to approximate evaluations of polynomials. Section 3 contains our main technical contribution: we will introduce a class of graph polynomials and give an efficient algorithm for computing their low order coefficients on bounded degree graphs. These two algorithms (or variations of them) will then be combined in Sections 4–7 to prove the results above. These sections can be read independently of one another. Finally, we conclude in Section 8 with some remarks and questions.

Approximating evaluations of polynomials

In this section we present an algorithm due to Barvinok to approximate evaluations of polynomials. We take a slightly different approach and give full details for the sake of completeness.

This can then be transformed to give a multiplicative approximation to $p$. It will be more convenient for us to use a slightly different form of (6) which we derive below.

Thus defining the $j$th inverse power sum to be $p_{j}:=\zeta_{1}^{-j}+\cdots+\zeta_{d}^{-j}$ we see that

In the next proposition we derive a variant of the Newton identities that relate the inverse power sums and the coefficients of the polynomial.

For the polynomial $p(z)=a_{0}+\cdots+a_{d}z^{d}$ as above and its inverse power sums $p_{j}$ as defined above, we have for each $k=1,2,\ldots$ that

From (7) we know that for $z\in D$ we have $\ln(p(z))=\ln(a_{0})-\sum_{j=1}^{\infty}\frac{p_{j}z^{j}}{j}$. Differentiating both sides and multiplying by $p(z)$ we obtain

Comparing coefficients of $z^{k-1}$ on each side gives the desired identity. ∎

The next lemma shows that the quality of the approximation (6) and hence (7) depends on the location of the complex roots of $p$.

Let $q:=|t|/M$. Then, as $|t|<M$, we have $q<1$. We will first show that

By assumption we know that $|\zeta_{i}|\geq M$ for each $i=1,\ldots,d$. Hence $|p_{j}|\leq d/M^{j}$ and so $|p_{j}t^{j}|\leq dq^{j}$. Substituting this in into (9) and using that $q<1$ we obtain (8).

Take $m=C\ln(d/\varepsilon)$, where $C$ is chosen such that $C\geq(\ln 1/q)^{-1}$ and $1/m\leq 1-q$ (so it is easy to check that e.g. $C=(1-q)^{-1}$ suffices). Then the right-hand side of (8) is at most $\varepsilon$. Write $z=T_{m}(f)(t)$. Then we have $|e^{f(t)-z}|\leq e^{|f(t)-z|}\leq e^{\varepsilon}$ and similarly $|e^{z-f(t)}|\leq e^{\varepsilon}$. (This follows from the fact that for a complex number $y=a+bi$, we have $|e^{y}|=e^{a}\leq e^{|y|}$.) Moreover, the angle between $e^{z}$ and $e^{f(t)}$ is bounded by $|\Im\ln e^{z-f(t)}|\leq|\ln e^{z-f(t)}|\leq\varepsilon$. This shows that $e^{z}=\exp(T_{m}(f)(t))$ is a multiplicative $\varepsilon$-approximation to $p(t)$. ∎

From (7) and Lemma 2.2, if we have an efficient way of computing the inverse power sums $p_{j}$ from $j=1$ up to $O(\ln(\deg(p)))$ (which by Proposition 2.1 is essentially equivalent to computing the first $O(\ln(\deg(p)))$ coefficients of $p$), then we have an efficient way of approximating evaluations of $p$ at points in the disk around zero where $p$ is nonvanishing. We formalize this in the corollary below. In the next section we will show that for certain types of graph polynomials we can compute the inverse power sums efficiently.

The corollary is immediate from (6), (7) and Lemma 2.2. ∎

Computing coefficients of graph polynomials

In this section we present our main technical contribution, which is an efficient way to compute the inverse power sums (and hence the coefficients) of a large class of graph polynomials for bounded degree graphs. Throughout, we will focus on graph polynomials whose coefficients can be expressed as linear combinations of induced subgraph counts. Note that in this section we make no assumptions on the locations of the roots of polynomials. The results in this section are stated only for graphs, but are in fact valid for multigraphs. So the reader could read multigraph instead of graph everywhere in this section. (The degree of a vertex in a multigraph is the number of edges incident with the vertex, where a loop is counted twice.)

We start with some definitions after which we state the main result of this section. Two graphs $H=(V_{H},E_{H})$ and $G=(V_{G},E_{G})$ are said to be isomorphic if there exists a bijection $f:V_{H}\rightarrow V_{G}$ such that for any $u,v\in V_{H}$, we have that $f(u)f(v)\in E_{G}$ if and only if $uv\in E_{H}$. We say that $H$ is an induced subgraph of $G$ if there is a subset $S\subseteq V_{G}$ such that $H$ is isomorphic to $G[S]$, the graph induced by $S$. We write $\text{ind}(H,G)$ for the number of sets $S\subseteq V_{G}$ such that $H$ is isomorphic to $G[S]$ (i.e. the number of induced subgraphs of $G$ isomorphic to $H$). Note that if $H$ is the empty graph we have $\text{ind}(H,G)=1$ for all $G$.

Let $p$ be a multiplicative graph polynomial defined by

for every graph $G$, the coefficients $e_{i}$ satisfy

for each $H\in\mathcal{G}_{\alpha i}$, the coefficients $\lambda_{H,i}$ can be computed in time $O(\beta^{|V(H)|})$.

If, for example, for each $i$, the coefficient $e_{i}(G)$ in (10) is equal to the number of independent sets of size $i$ in $G$, then it is easy to see that $p$ (which is of course the independence polynomial) is a BIGCP. In this case the obvious brute force algorithm to compute the coefficient $e_{i}(G)$ for an $n$-vertex graph $G$ runs in time $O(n^{i})$ (by checking all $i$-subsets of $V(G)$) and if $i=O(\ln n)$ then this is quasi-polynomial time. Our main result of this section is a general algorithm for computing inverse power sums of BIGCPs (and hence the coefficients of BIGCP’s by Proposition 2.1), which when applied to this example, computes $e_{i}(G)$ in polynomial time even when $i=O(\ln n)$ as long as the maximum degree of $G$ is bounded.

The algorithm in the theorem above only has access to the polynomial $p$ via condition (ii) in the definition of BIGCP, that is, it relies only on the algorithm which computes the complex numbers $\lambda_{H,i}$.

Assuming $\Delta\geq 3$, the proof of the theorem above in fact yields a running time of $n^{C_{1}}(n/\varepsilon)^{C_{2}}=(n/\varepsilon)^{O(1)}$, where $C_{1}$ can be explicitly determined (and does not depend on $\alpha,\beta,C$ and $\Delta$) and where we can crudely take $C_{2}=10C\alpha\ln(\beta\Delta)$, where $\alpha$ and $\beta$ are the constants from the definition of BIGCP.

Before we prove Theorem 3.1 we will first gather some facts about induced subgraph counts and the number of connected induced subgraphs of fixed size that occur in a graph which we will need for the proof.

where for a graph $H$, $c^{H}_{H_{1},H_{2}}$ is the number of ordered pairs of subsets of $V(H)$, $(S,T)$, such that $S\cup T=V(H)$ and $H[S]$ is isomorphic to $H_{1}$ and $H[T]$ is isomorphic to $H_{2}$. In particular, given $H_{1}$ and $H_{2}$, $c^{H}_{H_{1},H_{2}}$ is nonzero for only a finite number of graphs $H$.

Computing the parameter $\text{ind}(H,G)$ is generally difficult, but it becomes easier if $H$ is connected (and $V(H)$ is not too large) and $G$ has bounded degree.

there is an $O(n\Delta^{k-1})$-time algorithm, which, given any $n$-vertex graph $G$ with maximum degree at most $\Delta$, checks whether $\text{ind}(H,G)\neq 0$;

there is an $O(k^{2}n^{2}\Delta^{2(k-1)})$-time algorithm, which, given any $n$-vertex graph $G$ with maximum degree at most $\Delta$, computes the number $\text{ind}(H,G)$.

Note that Lemma 3.2 (i) enables us to test for graph isomorphism between bounded degree graphs when $|V(G)|=|V(H)|$.

Let us list the vertices of $V(H)$, $v_{1},\ldots,v_{k}$ in such a way that for $i\geq 1$ vertex $v_{i}$ has a neighbour among $v_{1},\ldots,v_{i-1}$. Then to embed $H$ into $G$ we first select a target vertex for $v_{1}$ and then given that we have embedded $v_{1},\ldots,v_{i-1}$ with $i\geq 2$ there are at most $\Delta$ choices for where to embed $v_{i}$. After $k$ iterations, we have a total of at most $n\Delta^{k-1}$ potential ways to embed $H$ and each possibility is checked in the procedure above. Hence we determine if $\text{ind}(H,G)$ is zero or not in $O(n\Delta^{k-1})$ time.

The procedure above gives a list $L$ (of size at most $n\Delta^{k-1}$) of all sets $S\subseteq V(G)$ such that $G[S]$ is isomorphic to $H$, although the list may contain repetitions. It takes time $O(k^{2}|L|^{2})=O(k^{2}n^{2}\Delta^{2(k-1)})$ to eliminate repetitions (by comparing every pair of elements in $L$), and the length of the resulting list gives the value of $\text{ind}(H,G)$. ∎

Next we consider how to enumerate all possible connected induced subgraphs of fixed size in a bounded degree graph. We will need the following result of Borgs, Chayes, Kahn, and Lovász [10, Lemma 2.1]:

Let $G$ be a graph of maximum degree $\Delta$. Fix a vertex $v_{0}$ of $G$. Then the number of connected induced subgraphs of $G$ with $k$ vertices containing the vertex $v_{0}$ is at most $\frac{(e\Delta)^{k-1}}{2}$.

As a consequence we can efficiently enumerate all connected induced subgraphs of logarrithmic size that occur in a bounded degree graph $G$.

By the previous result, we know that $|\mathcal{T}_{k}|\leq nk(e\Delta)^{k-1}$ for all $k$.

We inductively construct $\mathcal{T}_{k}$. For $k=1$, $\mathcal{T}_{k}$ is clearly the set of singleton vertices and takes time $O(n)$ to output.

Given that we have found $\mathcal{T}_{k-1}$ we compute $\mathcal{T}_{k}$ as follows. We first compute the multiset

Here $|N_{G}(S)|\leq|S|\Delta\leq k\Delta$ and takes time $O(k\Delta)$ to find (assuming $G$ is given in adjacency list form). Therefore computing $\mathcal{T}_{k}^{*}$ takes time $O(|\mathcal{T}_{k-1}|k\Delta)=O(nk^{2}(e\Delta)^{k})$, which is also the size of $\mathcal{T}_{k}^{*}$. Finally we compute the set $\mathcal{T}_{k}$ by removing the repetitions in $\mathcal{T}_{k}^{*}$ (by comparing each element with all previous elements), which takes time $O(k^{2}|\mathcal{T}_{k}^{*}|^{2})=O(n^{2}k^{6}(e\Delta)^{2k})$.

Starting from $\mathcal{T}_{1}$, we perform the above iteration $k$ times, requiring a total running time of $O(n^{2}k^{7}(e\Delta)^{2k})$.

It remains only to show that $\mathcal{T}_{k}$ contains all the sets we desire. Clearly $\mathcal{T}_{k-1}\subset\mathcal{T}_{k}$ and assume by induction that $\mathcal{T}_{k-1}$ contains all $T\subset V$ of size $k-1$ with $G[T]$ connected. Given $S\subseteq V$ such that $|S|=k$ and $G[S]$ is connected, take any tree of $G[S]$, remove a leaf $v$ and call the resulting set of vertices $S^{\prime}$. Then it is clear that $S^{\prime}\in\mathcal{T}_{k-1}$ and this implies $S=S^{\prime}\cup\{v\}\in\mathcal{T}_{k}$. ∎

Let $H$ be connected. Then for $G_{1},G_{2}\in\mathcal{G}$ we have $\text{ind}(H,G_{1}\cup G_{2})=\text{ind}(H,G_{1})+\text{ind}(H,G_{2})$, as $H$ is connected. Thus $\text{ind}(H,\cdot)$ is additive. Clearly, linear combinations of additive graph parameters are again additive. This implies that if $f$ is supported on connected graphs, then $f$ is additive.

Suppose next that $f$ is additive. We need to show that $a_{H}=0$ if $H$ is disconnected. By the previous part of the proof, we may assume that $a_{H}=0$ for all connected graphs $H$. Let now $H=H_{1}\cup H_{2}$ with both $H_{1}$ and $H_{2}$ nonempty. We may assume by induction that for all graphs $H^{\prime}$ of order strictly smaller than $k:=|V(H)|$ we have $a_{H^{\prime}}=0$. Now, by additivity we have

since $|V(H_{i})|<k$ for $i=1,2$. On the other hand we have

As $\text{ind}(H,H)\neq 0$, this implies that $a_{H}=0$ and finishes the proof. ∎

2 Proof of Theorem 3.1

for each $k=1,\ldots,d$. By (11), for $i\geq 1$, the $e_{i}$ can be expressed as linear combinations of induced subgraph counts of graphs with at most $\alpha i$ vertices. Since $p_{1}=-e_{1}$, this implies that the same holds for $p_{1}$. By induction, (12), and (13) we have that for each $k$

for certain, yet unknown, coefficients $a_{H,k}$.

Since $p$ is multiplicative, the inverse power sums are additive. Thus Lemma 3.5 implies that $a_{H,k}=0$ if $H$ is not connected. Denote by $\mathcal{C}_{i}(G)$ the set of connected graphs of order at most $i$ that occur as induced subgraphs in $G$. This way we can rewrite (14) as follows:

The next lemma says that we can compute the coefficients $a_{H,k}$ efficiently for $k=1,\ldots,m$, where $m=C\ln(n/\varepsilon)$.

There is an $(n/\varepsilon)^{O(1)}$-time algorithm, which given a BIGCP $p$ and an $n$-vertex graph $G$ of bounded maximum degree, computes and lists the coefficients $a_{H,k}$ in (15) for all $H\in\mathcal{C}_{\alpha k}(G)$ and all $k=1,\ldots,m=C\ln(n/\varepsilon)$.

Using the algorithm of Lemma 3.4, we first compute the sets $\mathcal{T}_{\alpha k}$ consisting of all subsets $S$ of $V(G)$ such that $|S|\leq\alpha k$ and $G[S]$ is connected, for $k=1\ldots,m$. This takes time bounded by $(n/\varepsilon)^{O(1)}$. (Note that the algorithm in Lemma 3.4 computes and lists all the sets $\mathcal{T}_{i}$ for $i=1,\ldots,\alpha m$.) We next compute and list the graphs in $\mathcal{C}_{\alpha k}(G)$ by considering the set of graphs $\{G[S]\mid S\in\mathcal{T}_{\alpha k}\}$ and removing copies of isomorphic graphs using Lemma 3.2 (i) to test for isomorphism. This takes time at most $(n/\varepsilon)^{O(1)}$ for each $k$, so the total time to compute and list the $\mathcal{C}_{\alpha k}(G)$ is bounded by $(n/\varepsilon)^{O(1)}$.

To prove the lemma, let us fix $k\leq m$ and show how to compute the coefficients $a_{H,k}$, assuming that we have already computed and listed the coefficients $a_{H,k^{\prime}}$ for all $k^{\prime}<k$. Let us fix $H\in\mathcal{C}_{\alpha k}(G)$. By (13), it suffices to compute the coefficient of $\text{ind}(H,\cdot)$ in $p_{k-i}e_{i}$ for $i=1,\ldots,k$ (where we set $p_{0}=1)$. By (11), (12) and (14) we know that the coefficient of $\text{ind}(H,\cdot)$ in $p_{k-i}e_{i}$ is given by

As $|V(H)|\leq\alpha k=O(\ln(n/\varepsilon))$, the second sum in (16) is over at most $4^{\alpha k}=(n/\varepsilon)^{O(1)}$ pairs $(S,T)$. For each such pair, we need to compute $\lambda_{H[S],i}$ and look up $a_{H[T],(k-i)}$. We can compute $\lambda_{H[S],i}$ in time bounded by $\beta^{|S|}=(n/\varepsilon)^{O(1)}$ since $p$ is a BIGCP.

Looking up $a_{H[T],(k-i)}$ in the given list requires us to test isomorphism of $H[T]$ with each graph in $\mathcal{C}_{\alpha(k-i)}(G)$ (noting that $a_{H[T],(k-i)}=0$ if $H[T]\not\in\mathcal{C}_{\alpha(k-i)}(G)$ by Lemma 3.5). Using Lemma 3.2(i) to test for graph isomorphism, this takes time at most

Here we use Lemma 3.3 to bound $|\mathcal{C}_{\alpha(k-i)}(G)|$. Together, all this implies that the coefficient of $\text{ind}(H,\cdot)$ in $p_{k-i}e_{i}$ can be computed in time bounded by $(n/\varepsilon)^{O(1)}$, and so the coefficient $a_{H,k}$ can be computed in time $(n/\varepsilon)^{O(1)}$. Thus all coefficients $a_{H,k}$ for $H\in\mathcal{C}_{\alpha k}(G)$ can be computed and listed in time bounded by $|\mathcal{C}_{\alpha k}(G)|(n/\varepsilon)^{O(1)}=(n/\varepsilon)^{O(1)}$. This can be done for each $k=1,\ldots,m$ in time $(n/\varepsilon)^{O(1)}$. ∎

To finish the proof of the theorem, we compute $p_{k}$ for each $k=1,\ldots,m$ by adding all the numbers $a_{H,k}\text{ind}(H,G)$ over all $H\in\mathcal{C}_{\alpha k}(G)$. This can be done in time

where we use that computing $\text{ind}(H,G)$ with $H\in\mathcal{C}_{\alpha k}(G)$ takes time $O((\alpha k)^{2}n^{2}\Delta^{2(\alpha k-1)})$ by Lemma 3.2(ii).

3 Extensions to colored graphs

In this section, we treat the case of colored graphs, which we shall require later. In fact all earlier proofs go through line by line for the colored case, but we chose to avoid excessive generality for the sake of exposition. Here we restate various definitions for the colored case and restate the main theorem.

We can then extend the definitions in the natural way to their colored versions. In particular $\mathcal{G}$, $\mathcal{G}_{k}$, $\mathcal{C}_{k}(G)$ become respectively the set of all vertex (resp. edge) colored graphs, the set of all vertex (resp. edge) colored graphs of order at most $k$, and the set of all connected, vertex (resp. edge) colored induced subgraphs of $G$ of order at most $k$. Note that $\mathcal{G}_{k}$ becomes infinite in the colored setting but is finite in the uncolored setting, but this will not matter. The definition of (multiplicative) graph invariant and graph polynomial extend in the natural way to vertex (resp. edge) colored graphs and in particular a BIGCP for vertex (resp. edge) colored graphs is defined in exactly the same way. We need only note that although the sum in part (i) of the definition of BIGCP is infinite in the colored version, all but finitely many terms will be zero when evaluating for a particular choice of colored graph $G$. Now the colored version of Theorem 3.1 reads as follows.

The independence polynomial

Now fix an $n$-vertex graph $G$ of maximum degree at most $\Delta$. Let $m=C\ln(n/\varepsilon)$, where $C=C(\lambda,\lambda^{*})$ is the constant in Corollary 2.3. As the $k$th coefficient of $Z(G)$ is equal to $\text{ind}(\bullet^{k},G)$, where $\bullet^{k}$ denotes the graph consisting of $k$ isolated vertices and as $Z(G)$ is clearly multiplicative and has constant term equal to $1$, we have that $Z(G)$ is a BIGCP (taking $\alpha=\beta=1$). So by Theorem 3.1 we see that for $k=1,\ldots,m$ we can compute the first $m$ inverse power sums of $Z(G)$ in time $(n/\varepsilon)^{O(1)}$. Noting that the degree of $Z(G)$ is at most $n$, Corollary 2.3 implies we can compute a multiplicative $\varepsilon$-approximation to $Z(G)(\lambda)$ in time $(n/\varepsilon)^{O(1)}$. This concludes the proof. ∎

Evaluating the independence polynomial at negative and complex values gives us new information about the distribution of independent sets in a graph, as illustrated by the following example. We denote by $Z_{e}(G)(\lambda)$ the polynomial defined in the same way as the independence polynomial except that in the sum (1), we only allow independent sets whose cardinality is even.

We apply the algorithm of Theorem 1.1 to compute multiplicative $\varepsilon$-approximations $A(\lambda)$ and $A(-\lambda)$ to $Z(G)(\lambda)$ and $Z(G)(-\lambda)$ respectively in time $(|V|/\varepsilon)^{O(1)}$. We have

Taking half the sum of these equations and noting that $Z_{e}(G)(\lambda)=\frac{1}{2}(Z(G)(\lambda)+Z_{G}(-\lambda))$, we see that $\frac{1}{2}(A(\lambda)+A(-\lambda))$ is a multiplicative $\varepsilon$-approximation to $Z_{e}(G)(\lambda)$ provided both $Z(G)(\lambda)$ and $Z(G)(-\lambda)$ have the same sign.

Clearly $Z(G)(\lambda)>0$ since the coefficients of $Z(G)$ are nonnegative real numbers. Also $Z(G)(-\lambda)>0$ because we know by the result of Scott and Sokal that $Z(G)$ does not vanish in the interval $[-\lambda^{*},\lambda^{*}]$, and we know $Z(G)$ is positive in the interval $[0,\lambda^{*}]$ since all the coefficients of $Z(G)$ are nonnegative real numbers. Hence $Z(G)$ is positive on the whole interval $[-\lambda^{*},\lambda^{*}]$ and in particular $Z(G)(\lambda)>0$. ∎

2 The multivariate independence polynomial

Here we will briefly mention how our results apply to the multivariate independence polynomial. For a graph $G=(V,E)$ and a variable $z_{v}$ for each $v\in V$ define

Fix the complex values of $z_{v}$, $v\in V$ at which we wish to evaluate the multivariate independence polynomial. Now define a univariate graph polynomial $q(G)$ by $q(G)(\lambda)=Z(G)((\lambda z_{v})_{v\in V})$, where $q(G)(1)$ is what we wish to estimate. The coefficient of $\lambda^{k}$ in $q(G)$ is then given by the sum over all independent sets of $G$ of size $k$, where an independent set $I$ is counted with weight $\prod_{v\in I}z_{v}$. While we can no longer represent this as a linear combination of ordinary induced subgraph counts, we can view this as a linear combination of vertex-colored induced subgraph counts, as we will now explain.

Suppose now that $G$ has $n$ vertices labelled $1,\ldots,n$. We view $G$ as a vertex-colored graph by giving the vertex labeled $i$ color $i$ for $i=1,\ldots,n$. Then $q_{vc}(G)=q(G)$. So if $G$ has bounded degree, we can by Theorem 3.7 compute the logarithmic order inverse power sums of $q(G)$ efficiently, as in the previous section.

The result of Shearer , cf. Scott and Sokal [41, Corollary 5.7] also applies to the multivariate independence polynomial (i.e. $Z(G)((z_{v})_{v\in V})$ is non-zero whenever $|z_{v}|<\lambda^{*}(\Delta)$ for all $v\in V$ and $\Delta(G)\leq\Delta$). This means $q(G)(\lambda)$ is nonzero whenever $|\lambda|<M$ for some $M>1$. It then follows that we can efficiently approximate $q(G)(1)$ and hence $Z(G)((z_{v})_{v\in V})$ if $G$ has maximum degree at most $\Delta$ and if all $z_{v}$ satisfy $|z_{v}|<\lambda^{*}(\Delta)$.

3 The independence polynomial on claw-free graphs

In this subsection, we illustrate a technique of Barvinok for approximating graph polynomials on larger regions of the complex plane by making careful polynomial transformations. We use this technique to prove Theorem 1.2, which shows that we can approximate the independence polynomial of claw-free graphs on almost the entire complex plane. First we require a few preliminary results.

We also require the following lemma of Barvinok .

$\phi(0)=0$ and $\phi(1)=1$ and $\phi$ has degree $N$;

$S_{\rho}$ is a bounded strip parallel to the real axis in the complex plane, so $\lambda S_{\rho}$ is the same strip enlarged by a factor $r$ and rotated by an angle $\theta$. The proposition then follows from elementary trigonometry. ∎

Set $n:=|V(G)|$ and let $\lambda=re^{i\theta}$ with $\theta\in(-\pi,\pi)$. Set

and consider the polynomial $g(z)=Z(G)(\lambda\phi_{\rho}(z))$. Note that the degree of $g$ is $O(n)$ since the degree of $Z(G)$ is at most $n$ and the degree of $\phi_{\rho}$ is a constant $N(\rho)$.

We will use Corollary 2.3 to find a multiplicative $\varepsilon$-approximation to $g(1)=Z(G)(\lambda)$ in time $(n/\varepsilon)^{O(1)}$. In order to apply Corollary 2.3 to draw this conclusion, it is enough to check that (i) $g$ has no roots in the disk $|z|\leq\beta:=\beta(\rho)$ and that (ii) the first $m=C\ln(d/\varepsilon)$ inverse power sums of $g$ can be computed in time $(n/\varepsilon)^{O(1)}$, where $d=O(n)$ is the degree of $g$ and $C=C(\beta,1)$ is the constant in the statement of Corollary 2.3.

For (ii), we show that we can compute the first $m$ coefficients of $g$ in time $(n/\varepsilon)^{O(1)}$, which is sufficient by Proposition 2.1. Given a polynomial $p(z)=\sum_{i=0}^{d}a_{i}z^{i}$, write $p_{[m]}(z):=\sum_{i=0}^{m}a_{i}z^{i}$. Then we note that $g_{[m]}=(Z(G)\circ(\lambda\phi))_{[m]}=(Z(G)_{[m]}\circ(\lambda\phi_{[m]}))_{[m]}$, where we crucially use the fact that $\phi$ has no constant term since $\phi(0)=0$. In words, to obtain $g_{[m]}(z)$ we substitute $\lambda\phi_{[m]}(z)$ into $Z(G)_{[m]}(z)$ and keep the first $m$ terms. Thus, in $O(m^{3})$-time we can obtain the first $m$ coefficients of $g$ if we know the first $m$ coefficients of $Z(G)$. As $Z(G)$ is a BIGCP, we can compute its first $m$ inverse power sums in time $(n/\varepsilon)^{O(1)}$ (as in the proof of Theorem 1.1), from which we can find its first $m$ coefficients in time $O(m^{2})$ by Proposition 2.1. This finishes the proof. ∎

We remark that, for the $(n/\varepsilon)^{O(1)}$ running time in the algorithm above, the $O(1)$ in the exponent depends on $\lambda$ and grows exponentially fast in $r=|\lambda|$. However, this dependence can be brought down to $O(|\lambda|^{1/2})$ by adapting Lemma 4.3 as described by Barvinok .

The Tutte polynomial

By a result of Jackson, Procacci and Sokal, cf. [31, Theorem 1.2] (which is valid for loopless multigraphs) we know that there exists a constant $K>0$ depending on $\Delta$ and $w$ such that for all $q$ with $|q|>K$ we have $Z_{T}(G)(q,w)\neq 0$ for all graphs $G$ of maximum degree at most $\Delta$. This is exactly opposite to what we need to apply Corollary 2.3, so let us define the graph polynomial $p_{T}$ by

for any graph $G=(V,E)$. Note that $p_{T}(G)$ has degree $n:=|V|$ and that if $x$ is a multiplicative $\varepsilon$-approximation to $p_{T}(G)(1/q,w)$, then $q^{n}x$ is a multiplicative $\varepsilon$-approximation to $Z_{T}(G)(q,w)$, so it is sufficient to find the former.

We will show that for any $n$-vertex graph $G$ of maximum degree at most $\Delta$, we can compute the first $m$ inverse power sums of $p_{T}(G)$ in time $(n/\varepsilon)^{O(1)}$, where $m=C\ln(n/\varepsilon)$ and $C=C(1/q,1/K)$ is the constant in Corollary 2.3. Corollary 2.3 then implies we can compute a multiplicative $\varepsilon$-approximation to $p_{T}(G)(1/q)$ and hence to $Z_{T}(G)(q,w)$ in time $(n/\varepsilon)^{O(1)}$.

We will show that $p_{T}(G)$ is a BIGCP so that by Theorem 3.1 we can conclude that we can compute the first $m$ inverse power sums in time $(n/\varepsilon)^{O(1)}$.

Since the Tutte polynomial $Z_{T}(G)(z,w)$ (as a polynomial in $z$) is a monic and multiplicative graph polynomial (of degree $n=|V(G)|$), we know that the constant term of $p_{T}$ equals $1$ and that $p_{T}$ is multiplicative. So it suffices to show conditions (i) and (ii) in Definition 3.1. The coefficient of $z^{k}$ in $p_{T}(G)$ equals the coefficient of $z^{n-k}$ in $Z_{T}(G)(z,w)$ and is by definition equal to the sum over all subsets $A$ of $E$ such that $A$ induces a graph with exactly $n-k$ components, where each subset is counted with weight $w^{|A|}$. Let us call a component of a graph nontrivial if it consists of more than one vertex. Suppose some subset of the edges $A\subseteq E$ induces $n-k$ components of which $c$ are nontrivial. Then we have $n-k-c$ isolated vertices and so the graph $F$, consisting of the union of these nontrivial components, has $n-(n-k-c)=k+c$ vertices and $k(F)=c$ components. Thus we have a correspondence between subsets $A$ of $E$ that induce a graph with exactly $n-k$ components and subgraphs $F$ of $G$ with no isolated vertices satisfying $k(F)=V(F)-k$. Therefore, writing $\delta(F)$ for the minimum degree of the subgraph $F$, the coefficient of $z^{n-k}$ in $Z_{T}(G)$ can be expressed as

In fact the first sum can be taken over graphs $H$ with at most $2k$ vertices. This is because $V(H)=V(F)$ and

From (18), we can compute the coefficient of $\text{ind}(H,G)$ by checking all subsets of $E(H)$ in time $O(2^{E(H)})=O(2^{\Delta|V(H)|})$. This implies that $p_{T}$ is a BIGCP (taking $\alpha=2$ and $\beta=2^{\Delta}$). ∎

Csikvári and Frenkel introduced graph polynomials of bounded exponential type and showed that these polynomials have bounded roots on bounded degree graphs. This was utilized in to give quasi-polynomial-time approximation algorithm for evaluations of these polynomials. The Tutte polynomial with the second argument fixed is an example of such a polynomial. We remark here that the proof given above for the Tutte polynomial also easily extends to graph polynomial of bounded exponential type. So the algorithm in can be adapted to run in polynomial time on bounded degree graphs.

Partition functions of spin models

In this section we will state and prove a generalization of Theorem 1.4 and we will indicate how our method applies to partition functions of graph homomorphisms with multiplicities.

Let $G=(V,E)$ be a graph. Suppose also that for each $e\in E$ we have a symmetric $k\times k$-matrix $A^{e}$. Let us write $\mathcal{A}=(A^{e})_{e\in E}$. Then we can extend the definition of the partition function of a spin model as follows:

We will refer to $p(G)(\mathcal{A})$ as the partition function of $\mathcal{A}$. In this is called a Markov random field (if the $A^{e}$ are nonnegative) and in this is called a multi spin system. Clearly, if all $A^{e}$ are the same, this just reduces to the partition function of a spin model. We have the following result, which implies Theorem 1.4.

The constant $0.34$ may be replaced by $0.45$ if $\Delta\geq 3$ and by $0.54$ if $\Delta$ is large enough; see .

Then $q(G)(0)=1$ and $q(G)(1)=k^{-|V|}p(G)(\mathcal{A})$. Barvinok and Soberón [8, Theorem 1.6] showed that there exists a constant $\delta>0$ such that $q(G)(z)\neq 0$ for all $z$ satisfying $|z|\leq 1+\delta$.

We will show that for any $n$-vertex graph $G$ of maximum degree at most $\Delta$, we can compute the first $m$ inverse power sums of $q(G)$ in time $(n/\varepsilon)^{O(1)}$, where $m=C\ln(n/\varepsilon)$ and $C=C(1,1+\delta)$ is the constant in Corollary 2.3. Noting that the degree of $q(G)$ is at most $|E|\leq n\Delta/2$, Corollary 2.3 implies we can compute a multiplicative $\varepsilon$-approximation to $q(G)(1)$ in time $(n/\varepsilon)^{O(1)}$. So it remains to show that we can compute the first $m$ inverse power sums of $q(G)$ in time $(n/\varepsilon)^{O(1)}$.

For a subset $F$ of $E$, define $G[F]$ to be the edge-colored graph induced by the edges in $F$. The vertex set of $G[F]$ consists of those vertices incident with edges in $F$ and hence has size at most $2|F|$. Then we see that the coefficient of $z^{i}$ in (21) can be written as follows:

where we interpret $\mathcal{G}_{2i}$ as the collection of edge-colored graphs on at most $2i$ vertices. This shows how to extend $q$ to edge-colored graphs. The inner sum in (22) can be computed in time $O(k^{|V(H)|})$, and clearly $q$ has constant term equal to $1$ and it is multiplicative. This implies that the extension of $q$ to edge-colored graphs is a BIGCP (with constant $\alpha=2$ and $\beta=k$) and so Theorem 3.7 implies that we can compute the first $m$ inverse power sums of $q$ in time bounded by $O(n/\varepsilon)^{O(1)}$. This finishes the proof. ∎

2 Partition functions of graph homomorphisms with multiplicities

We refer to for more details and background on this type of partition function.

Building on a result from Barvinok and Soberón [9, Section 2] and using exactly the same proof as above we directly establish the following:

Partition functions of edge-coloring models

In this section we state and prove a generalization of Theorem 1.5. It is along the same lines as the generalization of Theorem 1.4 in the previous section. The proof also goes along the same line, but as we will see below there are some details that are different.

Let $G=(V,E)$ be a graph. Suppose that we have $k$-color edge-coloring models $h^{v}$ for each $v\in V$. Let us write $\mathcal{H}=(h^{v})_{v\in V}$. Often the pair $(G,\mathcal{H})$ is called a signature grid, cf. . Then we can extend the definition of the partition function of an edge-coloring model as follows:

We will refer to $p(G)(\mathcal{H})$ as the partition function of $\mathcal{H}$. Clearly, if all $h^{v}$ are equal we obtain the ordinary partition function of an edge-coloring model. It is also called the Holant problem of the signature grid $(G,\mathcal{H})$ cf. . We have the following result, which implies Theorem 1.5.

The constant $0.35$ may be replaced by $0.47$ if $\Delta\geq 3$ and by $0.56$ if $\Delta$ is large enough; see . Moreover, for readers familiar with the orthogonal group invariance of these partition functions one can use Corollary 6b from to find a larger family of edge-coloring models for which the partition function can be efficiently approximated.

Observe that $q(G)(1)=k^{-|E|}p(G)(\mathcal{H})$ and that $q(G)$ is a polynomial of degree at most $n:=|V|$. So, just as in the previous section, the problem of approximating the partition function $p(G)(\mathcal{H})$ is replaced by approximating an evaluation of a univariate polynomial.

By Corollary 6a from (which is valid for multigraphs) there exists $\delta>0$ such that $q(G)(z)\neq 0$ whenever $|z|\leq 1+\delta$. We will show (in Theorem 7.2) that for any $n$-vertex graph $G$ of maximum degree at most $\Delta$, we can compute the first $m$ inverse power sums of $q(G)$ in time $(n/\varepsilon)^{O(1)}$, where $m=C\ln(n/\varepsilon)$ and $C=C(1,1+\delta)$ is the constant in Corollary 2.3. Noting that the degree of $q(G)$ is at most $n$, Corollary 2.3 implies we can compute a multiplicative $\varepsilon$-approximation to $q(G)(1)$ in time $(n/\varepsilon)^{O(1)}$.