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

arXiv:1607.01167v3 [math.CO] 18 Jul 2017

Viresh Patel†

Guus Regts‡.

July 19, 2017

Abstract
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 C and show that if
p ∈ 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 [2, 3, 4, 5], which
provides a new algorithmic approach besides the existing Markov chain Monte Carlo
method and the correlation decay method for these types of problems.
Keywords: approximation algorithms, Tutte polynomial, independence polynomial, partition
function, graph homomorphism, Holant problem.
MSC: 68W25 (Primary) 05C31, (Secondary).

1

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
∗ An

extended abstract of this work has been accepted in Eurocomb 2017.
de Vries Institute for Mathematics, University of Amsterdam. Email: vpatel@uva.nl. Supported
by the Netherlands Organisation for Scientific Research (NWO) through the Gravitation Programme Networks
(024.002.003).
‡ Korteweg de Vries Institute for Mathematics, University of Amsterdam. Email: guusregts@gmail.com.
Supported by a personal NWO Veni grant
† Korteweg

1

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
[11, 20]. 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 [50], 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 [44], 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. [1, 24, 36, 43] 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 [29] 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 [25]) and the number of homomorphisms into any fixed graph can be modelled as
the partition function of a complex edge-coloring model (see [47, 48]).
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 [18], results on the locations of zeros of graph polynomials and partition functions
[42, 41, 31, 8, 9, 40] and an algorithmic development due to Barvinok [2]. The Taylor
approximation technique of Barvinok has been used to construct deterministic quasipolynomial-time approximation algorithms for evaluating a number of graph partition
functions (for general graphs); see e.g. work by Barvinok [2, 3, 4, 5], by Barvinok and
Sobeŕon [8, 9], and by the second author [40]. We refer to Barvinok’s recent book [7] 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,

2

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.
Definition 1.1. Let q and ξ be a non-zero complex numbers. We call ξ a multiplicative
ε-approximation to q if e−ε ≤ |q|/|ξ | ≤ eε and if the angle between ξ and q (as seen as
vectors in C = R2 ) is at most ε.

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

λ| I | .

∑

(1)

I ⊆V
I independent

In [50] Weitz proved, based on the correlation decay method, that if 0 ≤ λ < λc , where
λc =

( ∆ − 1 ) ∆ −1
,
( ∆ − 2) ∆

then there exists a deterministic algorithm, which given a graph G = (V, E) of maximum degree at most ∆ and ε > 0, computes a multiplicative ε-approximation to
Z ( G )(λ) in time (|V |/ε)O(1) . Sly and Sun [44] proved this is tight by showing that,
as soon as λ > λc , one cannot efficiently approximate Z ( G, λ) unless NP=RP.
In Section 4 we prove the following result, which has been independently obtained
by Harvey, Srivastava and Vondrák [29] using the correlation decay method.
( ∆ − 1 ) ∆ −1

Theorem 1.1. Let ∆ ∈ N and let λ ∈ C be such that |λ| < λ∗ (∆) :=
. Then there
∆∆
exists a deterministic algorithm, which, given a graph G = (V, E) of maximum degree at most
∆ and ε > 0, computes a multiplicative ε-approximation to Z ( G )(λ) in time (|V |/ε)O(1) .

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

(|V |/ε) 1−|λ|/λ∗ (∆)

for some absolute constants D, D ′ .

ln( ∆ )

|V | D

′

Theorem 1.1 in fact also applies to the multivariate independence polynomial, as we
will briefly explain in Subsection 4.2.
For positive valued λ our result is weaker than Weitz’s result since λc > λ∗ . However
our result works for negative1 and even complex λ. The case λ < 0 is relevant due to
its connection to the Lovász local lemma, cf. [41]. We remark here that by very recent
results of Peters and the second author [38] confirming a conjecture of Sokal [45], 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.
The value λ∗ in Theorem 1.1 originates from a paper of Shearer [42] (see also Scott
and Sokal [41]) where it is shown that for graphs of maximum degree ∆, the independence polynomial does not vanish at any λ ∈ C satisfying |λ| ≤ λ∗ . Also the value
of λ∗ is tight, as there exists a sequence of trees Tn of maximum degree at most ∆ and
λn < −λ∗ with λn → −λ∗ such that Z ( Tn , λn ) = 0, cf. [41, Example 3.6]. Theorem 1.1 is
also tight, as very recently, Galanis, Goldberg and Štefankovič showed that it is NP-hard
to approximate ZG (λ) when λ < −λ∗ .
1 In an unpublished note [46] Srivastava notes that the correlation decay method of Weitz in fact also applies
to negative λ as long as λ > − λ∗ .

3

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 [17] stating that the
independence polynomial of a claw-free graph has only negative real roots. We prove
the following result in Subsection 4.3.
Theorem 1.2. Let ∆ ∈ N and let λ ∈ C be such that λ is not a real negative number. Then
there exists a deterministic algorithm, which, given a claw-free graph G = (V, E) of maximum
degree at most ∆ and ε > 0, computes a multiplicative ε-approximation to Z ( G )(λ) in time
(|V |/ε)O(1) .

Note that when G is the line graph of some graph H we have that ZG (λ) is equal to
the matching polynomial of H. So in particular, Theorem 1.2 implies a result of Bayati,
Gamarnik, Katz, Nair, and Tetali [1]. Our proof of it however is entirely different from
the proof in [1].

1.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 ZT ( G ) and is defined by
ZT ( G )(q, w) :=

∑

qk( A ) w | A | ,

(2)

A⊆E

where k( A) denotes the number of components of the graph (V, A). In particular, if
w = −1, ZT ( G )(q, −1) is equal to the chromatic polynomial of G.
Jerrum and Sinclair [33] 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 [27] 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 [28] 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 [26] looked
at the complexity of approximately evaluating the Tutte polynomial for general graphs
at complex values.
When w = −1 and q ∈ N, ZT ( G )(q, w) gives the number of q-colorings of G. Lu
and Yin [36] showed that when q > 2.58∆ there exists a deterministic polynomial-time
algorithm for approximating the Tutte polynomial at (q, −1) on graphs of maximum
degree at most ∆. There are many randomized algorithms of the sort above with sharper
bounds on q; see e.g. Jerrum [32] and Vigoda [49]. As far as we know there are no
general results known for the Tutte polynomial on bounded degree graphs.
We will consider the Tutte polynomial as a univariate polynomial by considering w
to be constant. In Section 5 we prove the following result.
Theorem 1.3. Let ∆ ∈ N and let w ∈ C. Then there exists a constant K (depending on ∆ and
w) such that if q ∈ C is such that |q| > K, then there exists a deterministic algorithm, which,
given a loopless multigraph G = (V, E) of maximum degree at most ∆ and ε > 0, computes a
multiplicative ε-approximation to Z ( G )(q, w) in time (|V |/ε)O(1) .

Remark 1.2. From the proof the Theorem 1.3 it follows that the running time is in fact
bounded by
D

(|V |/ε) 1−K/|q|

for some absolute constants D, D ′ .

4

∆ ln( ∆ )

|V | D

′

The constant K in the theorem above comes from a paper of Jackson, Procacci and
Sokal [31] and unfortunately takes half a page to state exactly. However, when w satisfies |1 + w| ≤ 1 (this includes the chromatic polynomial), the constant K may be taken
to be 6.91∆.
Remark 1.3. Sokal [30, Conjecture 21] conjectured that ZT ( G )(q, −1) 6= 0 as long as
ℜ(q) > ∆( 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 (∆ + 1)-colorings of any graph G of maximum degree at most ∆,
a notorious problem in computational counting.

1.3 Partition functions of spin models
Let A ∈ C k×k be a symmetric matrix. In the context of statistical physics A is often
called a spin model cf. [19]. For a graph G = (V, E), the partition function of A is
defined as
(3)
p( G )( A) = ∑
∏ Aφ(u),φ(v).
φ:V →[k ] { u,v }∈ E

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 [8] p( G )( A) is called the graph homomorphism
partition function.
Building on a line of research started by Dyer and Greenhill [21] and Bulatov and
Grohe [12], 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 [13].
This dichotomy essentially says that computing the partition function of A exactly is #P
hard unless the matrix A has some special structure.
Lu and Yin [36] proved, using the correlation decay approach, that for fixed ∆ ∈ N,
if a real matrix A is sufficiently close to the all ones matrix (i.e. | Ai,j − 1| ≤ O(1)/∆ for
all i, j = 1, . . . k), then there exists a (|V ( G )|/ε)O(1) -time algorithm for computing a multiplicative ε-approximation to P( G )( A) on graphs of maximum degree at most ∆. Barvinok and Sobéron [8] showed that there exists a (|V ( G )|/ε)O(ln |V ( G)|)-time algorithm for
complex-valued matrices A that satisfy | Ai,j − 1| ≤ O(1)/∆ for all i, j = 1, . . . , k.
Building on the work of Barvinok and Sobéron we prove in Section 6 the following
result.
Theorem 1.4. Let ∆, k ∈ N. Then there exists a deterministic algorithm, which, given a graph
G = (V, E) of maximum degree at most ∆, a (complex-valued) symmetric k × k matrix A
such that | Ai,j − 1| ≤ 0.34/∆ for all i, j = 1, . . . , k, and ε > 0, computes a multiplicative
ε-approximation to p( G )( A) in time (|V |/ε)O(1) .

Remark 1.4. The constant 0.34 can be replaced by 0.45 if ∆ ≥ 3, and by 0.54 if ∆ is large
enough, cf. [8].

In [9] 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.

1.4 Partition functions of edge-coloring models
Edge-coloring models originate in statistical physics and their partition functions have
been introduced to the graph theory community by de la Harpe and Jones [19] (where
they are called vertex models). We call any map h : N k → C a k-color edge-coloring model.

5

For a graph G = (V, E), the partition function of h is defined by
p( G )(h) :=

∑ ∏ h(φ(δ(v))),

(4)

φ:E →[k ] v ∈V

where δ(v) denotes the set of edges incident with the vertex v and φ(δ(v)) denotes the
multiset of colors that the vertex v ‘sees’, which we identify with its incidence vector
in N k so that we can apply h to it. Explicitly, φ(δ(v)) is identified with the vector
( a1 , . . . , ak ) ∈ N k if for each i there are ai occurrences of the color i amongst the edges
incident with v.
Partition functions of edge-coloring models form a rich class of graph parameters
including the number of matchings (take h : N2 → C defined by h(α) = 1 if α1 ≤ 1
and 0 otherwise), as well as partition functions of spin models, as has been proved by
Szegedy [47, 48]. These partition functions can be seen as Holant problems; see e.g.
[15, 16, 14]. They can also be seen as tensor network contractions. We refer the reader
to [39] for more background.
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 [15, 16,
14]. 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 [1] found an efficient approximation algorithm for
counting matchings in bounded degree graphs and Lin, Liu and Lu [35] 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 [40] we will prove the following result in
Section 7.
Theorem 1.5. Let ∆, k ∈ N. Then there exists a deterministic algorithm, which, given a
multigraph G = (V, E) of maximum degree at most ∆, a k-color edge-coloring model h such
that |h(φ) − 1| ≤ 0.35/(∆ + 1) for all φ ∈ N k , and ε > 0, computes a multiplicative εapproximation to p( G )(h) in time (|V |/ε)O(1) .
Remark 1.5. The constant 0.35 may be replaced by 0.47 if ∆ ≥ 3 and by 0.56 if ∆ is large
enough; see [40]. 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 [40]
to find a much larger family of edge-coloring models for which the partition function
can be efficiently approximated.

1.5 Organization
In the next section we shall consider an algorithm due to Barvinok [2] 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.

2

Approximating evaluations of polynomials

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

6

Let p ∈ C [z] be a polynomial p(z) = a0 + a1 z + · · · + ad zd of degree d and suppose
that p(z) 6= 0 for all z in an open disk D of radius M. Define the function f on this disk
by
f (z) := ln p(z),
(5)
(where we fix a branch of the logarithm by fixing the principal value of the logarithm at
t j ( j)
p(0)). Recall by Taylor’s Theorem that for each t ∈ D, f (t) = ∑∞
j =0 j! f (0). In order to
approximate p at t ∈ D, we will find an additive approximation to f at t by truncating
the Taylor expansion around z = 0. For each m ∈ N, let
Tm ( f )(t) := f (0) +

m

t j ( j)
∑ j! f (0).
j =1

(6)

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.
Let ζ 1 , . . . , ζ d ∈ C be the roots of p. Then we can write p(z) = ad (z − ζ 1 ) · · · (z − ζ d )
and f (z) = ln( ad ) + ln(z − ζ 1 ) + · · · + ln(z − ζ d ). From this we see that f ′ (z) = (z −
ζ 1 )−1 + · · · + (z − ζ d )−1 and hence for j ≥ 1,
d

−j

f ( j) (0) = −( j − 1)! ∑ ζ i .
i =1

−j

−j

Thus defining the jth inverse power sum to be p j := ζ 1 + · · · + ζ d we see that
m

Tm ( f )(t) = f (0) − ∑

j =1

m p tj
pjtj
j
= ln( a0 ) − ∑
.
j
j
j =1

(7)

In the next proposition we derive a variant of the Newton identities that relate the
inverse power sums and the coefficients of the polynomial.
Proposition 2.1. For the polynomial p(z) = a0 + · · · + ad zd as above and its inverse power
sums p j as defined above, we have for each k = 1, 2, . . . that
kak = −

k −1

∑ ai pk−i .

i =0

(Here we take ai = 0 if i > d.)
Proof. From (7) we know that for z ∈ D we have ln( p(z)) = ln( a0 ) − ∑∞
j =1
entiating both sides and multiplying by p(z) we obtain

pjzj
j .

Differ-

∞

p ′ ( z ) = − p ( z ) ∑ p j z j −1
j =1

and so

d

∑
k =1

d

kak zk−1 = − ∑ ai zi
i =0

∞

∑ p j z j −1 .

j =1

Comparing coefficients of zk−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.

7

Lemma 2.2. Given M > 0 and t ∈ C satisfying |t| < M, there exists a constant C =
C (t, M ) ≤ (1 − |t|/M )−1 such that the following holds. Suppose p is a polynomial of degree
d with no roots in the open disk D of radius M. Then for every ε > 0, exp( Tm ( f )(t)) is a
multiplicative ε-approximation to p(t), where m = C ln(d/ε).
Proof. Let q := |t|/M. Then, as |t| < M, we have q < 1. We will first show that

| f (t) − Tm ( f )(t)| ≤

dqm+1
.
(m + 1)(1 − q)

(8)

By (7) we have
∞

| f (t) − Tm ( f )(t)| ≤

∑
j = m +1

pjtj
1
≤
j
m+1

∞

∑
j = m +1

| p j t j |.

(9)

By assumption we know that |ζ i | ≥ M for each i = 1, . . . , d. Hence | p j | ≤ d/M j and so
| p j t j | ≤ dq j . Substituting this in into (9) and using that q < 1 we obtain (8).
Take m = C ln(d/ε), where C is chosen such that C ≥ (ln 1/q)−1 and 1/m ≤ 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 ε. Write z = Tm ( f )(t). Then we have |e f ( t)−z | ≤ e| f ( t)−z| ≤ eε and
similarly |ez− f ( t) | ≤ eε . (This follows from the fact that for a complex number y = a + bi,
we have |ey | = e a ≤ e|y| .) Moreover, the angle between ez and e f ( t) is bounded by
|ℑ ln ez− f (t)| ≤ | ln ez− f (t) | ≤ ε. This shows that ez = exp( Tm ( f )(t)) is a multiplicative
ε-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.
Corollary 2.3. Given M > 0 and t ∈ C satisfying |t| < M, there exists a constant C =
C (t, M ) ≤ (1 − |t|/M )−1 such that the following holds. Suppose p is a polynomial given by
p(z) = a0 + a1 z + · · · + ad zd with no roots in the open disk D of radius M. Suppose further
that we are able to compute a0 and the inverse power sums p1 , . . . , pr in time τ (r ) for each
r = 1, . . . , d. Then we can compute a multiplicative ε-approximation to p(t) in time O(τ (m)),
where m = C ln(d/ε).
Proof. The corollary is immediate from (6), (7) and Lemma 2.2.

3

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.)

8

We start with some definitions after which we state the main result of this section.
Two graphs H = (VH , EH ) and G = (VG , EG ) are said to be isomorphic if there exists
a bijection f : VH → VG such that for any u, v ∈ VH , we have that f (u) f (v) ∈ EG if
and only if uv ∈ EH . We say that H is an induced subgraph of G if there is a subset
S ⊆ VG such that H is isomorphic to G [S], the graph induced by S. We write ind( H, G )
for the number of sets S ⊆ VG 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
ind( H, G ) = 1 for all G.
By G we denote the collection of all graphs and by Gk for k ∈ N we denote the
collection of graphs with at most k vertices. A graph invariant is a function f : G → S
for some set S that takes the same value on isomorphic graphs. A graph polynomial is a
graph invariant p : G → C [z], where C [z] denotes the ring of polynomials in the variable
z over the field of complex numbers. Call a graph invariant f multiplicative if f (∅) = 1
and f ( G1 ∪ G2 ) = f ( G1 ) f ( G2 ) for all graphs G1 , G2 (here G1 ∪ G2 denotes the disjoint
union of the graphs G1 and G2 ).
Definition 3.1. Let p be a multiplicative graph polynomial defined by
d( G)

p( G )(z) :=

∑
i =0

ei ( G ) zi

(10)

for each G ∈ G with e0 ( G ) = 1. We call p a bounded induced graph counting polynomial
(BIGCP) if there exists constants α, β ∈ N such that the following two conditions are
satisfied:
(i) for every graph G, the coefficients ei satisfy
ei ( G ) : =
for certain λ H,i ∈ C;

∑

λ H,i ind( H, G )

(11)

H ∈G αi

(ii) for each H ∈ Gαi , the coefficients λ H,i can be computed in time O( β|V ( H )| ).

If, for example, for each i, the coefficient ei ( 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 ei ( G ) for an n-vertex graph G runs in time O(ni ) (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 ei ( G ) in polynomial time even when i = O(ln n) as long as the
maximum degree of G is bounded.
Theorem 3.1. Let C > 0 and ∆ ∈ N and let p(·) be a bounded induced graph counting
polynomial. Then there is a deterministic (n/ε)O(1) -time algorithm, which, given any n-vertex
graph G of maximum degree at most ∆ and any ε > 0, computes the inverse power sums
p1 , . . . , p m ( G ) of p( G ) for m = C ln(n/ε).
Remark 3.1. 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 λ H,i .
Remark 3.2. Assuming ∆ ≥ 3, the proof of the theorem above in fact yields a running
time of nC1 (n/ε)C2 = (n/ε)O(1) , where C1 can be explicitly determined (and does not
depend on α, β, C and ∆) and where we can crudely take C2 = 10Cα ln( β∆), where α
and β 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.

9

3.1 Induced subgraph counts
Define ind( H, ·) : G → C by G 7→ ind( H, G ). So we view ind( H, ·) as a graph invariant.
We can take linear combinations and products of these invariants. In particular, for two
graphs H1 , H2 we have
ind( H1 , ·) · ind( H2 , ·) =

∑
H ∈G

cH
H1 ,H2 ind( H, ·),

(12)

where for a graph H, c H
H1 ,H2 is the number of ordered pairs of subsets of V ( H ), ( S, T ),
such that S ∪ T = V ( H ) and H [S] is isomorphic to H1 and H [ T ] is isomorphic to H2 . In
particular, given H1 and H2 , c H
H1 ,H2 is nonzero for only a finite number of graphs H.
Computing the parameter 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.
Lemma 3.2. Let H be a connected graph on k vertices and let ∆ ∈ N. Then

(i) there is an O(n∆k−1 )-time algorithm, which, given any n-vertex graph G with maximum
degree at most ∆, checks whether ind( H, G ) 6= 0;

(ii) there is an O(k2 n2 ∆2( k−1) )-time algorithm, which, given any n-vertex graph G with maximum degree at most ∆, computes the number 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 )|.
Proof. Let us list the vertices of V ( H ), v1 , . . . , v k in such a way that for i ≥ 1 vertex vi has
a neighbour among v1 , . . . , v i−1. Then to embed H into G we first select a target vertex
for v1 and then given that we have embedded v1 , . . . , v i−1 with i ≥ 2 there are at most
∆ choices for where to embed v i . After k iterations, we have a total of at most n∆k−1
potential ways to embed H and each possibility is checked in the procedure above.
Hence we determine if ind( H, G ) is zero or not in O(n∆k−1 ) time.
The procedure above gives a list L (of size at most n∆k−1 ) of all sets S ⊆ V ( G )
such that G [S] is isomorphic to H, although the list may contain repetitions. It takes
time O(k2 | L|2 ) = O(k2 n2 ∆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 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]:
Lemma 3.3. Let G be a graph of maximum degree ∆. Fix a vertex v0 of G. Then the number of
connected induced subgraphs of G with k vertices containing the vertex v0 is at most

( e∆ ) 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.
Lemma 3.4. There is a O(n2 k7 (e∆)2k )-time algorithm which, given k ∈ N and an n-vertex
graph G = (V, E) of maximum degree ∆, outputs Tk , the set of all S ⊆ V satisfying |S| ≤ k
and G [S] connected.
Proof. By the previous result, we know that |Tk | ≤ nk(e∆)k−1 for all k.
We inductively construct Tk . For k = 1, Tk is clearly the set of singleton vertices and
takes time O(n) to output.
Given that we have found Tk−1 we compute Tk as follows. We first compute the
multiset
Tk∗ = {S ∪ {v} : S ∈ Tk−1 and v ∈ NG (S)}.

10

Here | NG (S)| ≤ |S|∆ ≤ k∆ and takes time O(k∆) to find (assuming G is given in adjacency list form). Therefore computing Tk∗ takes time O(|Tk−1 |k∆) = O(nk2 (e∆)k ),
which is also the size of Tk∗ . Finally we compute the set Tk by removing the repetitions in Tk∗ (by comparing each element with all previous elements), which takes time
O(k2 |Tk∗ |2 ) = O(n2 k6 (e∆)2k ).
Starting from T1 , we perform the above iteration k times, requiring a total running
time of O(n2 k7 (e∆)2k ).
It remains only to show that Tk contains all the sets we desire. Clearly Tk−1 ⊂ Tk
and assume by induction that Tk−1 contains all T ⊂ V of size k − 1 with G [ T ] connected.
Given S ⊆ 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′ . Then it is clear that S′ ∈ Tk−1 and this
implies S = S′ ∪ {v} ∈ Tk .
We call a graph invariant f : G → C additive if for each G1 , G2 ∈ G we have f ( G1 ∪
G2 ) = f ( G1 ) + f ( G2 ). The following lemma is a variation of a lemma due to Csikvári
and Frenkel [18]; it is fundamental to our approach.
Lemma 3.5. Let f : G → C be a graph invariant given by f (·) := ∑ H ∈G a H ind( H, ·). Then f
is additive if and only if a H = 0 for all graphs H that are disconnected.
Proof. Let H be connected. Then for G1 , G2 ∈ G we have ind( H, G1 ∪ G2 ) = ind( H, G1 ) +
ind( H, G2 ), as H is connected. Thus ind( H, ·) 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 = H1 ∪ H2 with both H1 and H2 nonempty. We may assume by induction
that for all graphs H ′ of order strictly smaller than k := |V ( H )| we have a H ′ = 0. Now,
by additivity we have

∑

f ( H ) = f ( H1 ) + f ( H2 ) =

H ′ : |V ( H ′ )|≥ k

a H ′ (ind( H ′ , H1 ) + ind( H ′ , H2 )) = 0,

since |V ( Hi )| < k for i = 1, 2. On the other hand we have
f (H) =

∑
H ′ : |V ( H ′ )|≥ k

a H ′ ind( H ′ , H ) = a H ind( H, H ).

As ind( H, H ) 6= 0, this implies that a H = 0 and finishes the proof.

3.2 Proof of Theorem 3.1
Recall that p(·) is a bounded induced graph counting polynomial (BIGCP). Given an
n-vertex graph G with maximum degree at most ∆, we must show how to compute the
first m inverse power sums p1, . . . , p m of p( G ) in time (n/ε)O(1) , where m = C ln(n/ε).
To reduce notation, let us write p = p( G ), d = d( G ) for the degree of p, and ei = ei ( G )
for i = 0, . . . , d for the coefficients of p (from (10)). Recall that pk := ζ 1−k + · · · + ζ d−k ,
where ζ 1 , . . . , ζ d ∈ C are the roots of the polynomial p( G ).
Noting e0 = 1, Proposition 2.1 gives
pk = −kek −

k −1

∑ ei p k−i ,

(13)

i =1

for each k = 1, . . . , d. By (11), for i ≥ 1, the ei can be expressed as linear combinations
of induced subgraph counts of graphs with at most αi vertices. Since p1 = −e1 , this

11

implies that the same holds for p1 . By induction, (12), and (13) we have that for each k
pk =

∑

a H,k ind( H, G ),

(14)

H ∈G α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 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:
pk =
(15)
∑ a H,k ind( H, G).
H ∈C αk ( G )

The next lemma says that we can compute the coefficients a H,k efficiently for k =
1, . . . , m, where m = C ln(n/ε).
Lemma 3.6. There is an (n/ε)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 ∈ C αk ( G ) and all k = 1, . . . , m = C ln(n/ε).
Proof. Using the algorithm of Lemma 3.4, we first compute the sets Tαk consisting of
all subsets S of V ( G ) such that |S| ≤ αk and G [S] is connected, for k = 1 . . . , m. This
takes time bounded by (n/ε)O(1) . (Note that the algorithm in Lemma 3.4 computes and
lists all the sets Ti for i = 1, . . . , αm.) We next compute and list the graphs in C αk ( G )
by considering the set of graphs { G [S] | S ∈ Tαk } and removing copies of isomorphic
graphs using Lemma 3.2 (i) to test for isomorphism. This takes time at most (n/ε)O(1)
for each k, so the total time to compute and list the C αk ( G ) is bounded by (n/ε)O(1) .
To prove the lemma, let us fix k ≤ m and show how to compute the coefficients a H,k ,
assuming that we have already computed and listed the coefficients a H,k′ for all k′ < k.
Let us fix H ∈ C αk ( G ). By (13), it suffices to compute the coefficient of ind( H, ·) in pk−i ei
for i = 1, . . . , k (where we set p0 = 1). By (11), (12) and (14) we know that the coefficient
of ind( H, ·) in pk−i ei is given by

∑
H1 ,H2

cH
H1 ,H2 a H2 ,( k − i ) λ H1 ,i =

∑
( S,T ) :S∪ T =V ( H )

a H [ T ],( k−i) λ H [S],i .

(16)

As |V ( H )| ≤ αk = O(ln(n/ε)), the second sum in (16) is over at most 4αk = (n/ε)O(1)
pairs (S, T ). For each such pair, we need to compute λ H [S],i and look up a H [ T ],( k−i) . We
can compute λ H [S],i in time bounded by β|S| = (n/ε)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 C α( k−i)( G ) (noting that a H [ T ],( k−i) = 0 if H [ T ] 6∈ C α( k−i) ( G ) by Lemma 3.5).
Using Lemma 3.2(i) to test for graph isomorphism, this takes time at most
O(|C α( k−i)( G )|α(k − i )∆α( k−i)−1) = O(n/ε)O(1) .
Here we use Lemma 3.3 to bound |C α( k−i)( G )|. Together, all this implies that the coeffi-

cient of ind( H, ·) in pk−i ei can be computed in time bounded by (n/ε)O(1) , and so the
coefficient a H,k can be computed in time (n/ε)O(1) . Thus all coefficients a H,k for H ∈
Cαk ( G ) can be computed and listed in time bounded by |Cαk ( G )|(n/ε)O(1) = (n/ε)O(1) .
This can be done for each k = 1, . . . , m in time (n/ε)O(1) .

To finish the proof of the theorem, we compute pk for each k = 1, . . . , m by adding
all the numbers a H,k ind( H, G ) over all H ∈ C αk ( G ). This can be done in time
O(m|C αm ( G )|(αm)2n2 ∆2( αm−1) ) = (n/ε)O(1) ,

where we use that computing ind( H, G ) with H ∈ C αk ( G ) takes time O((αk)2 n2 ∆2( αk−1) )
by Lemma 3.2(ii).

12

3.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.
Let us fix N, the natural numbers, as a set of colors. Let H = (VH , EH ) and
G = (VG , EG ) be graphs whose vertices (resp. edges) are colored from the set T (not
necessarily properly). For vertex-colored graphs H = (VH , EH ) and G = (VG , EG ) we
define H and G to be color-isomorphic if there is a color isomorphism between H and
G, that is, a graph isomorphism f : VH → VG such that u and f (u) have the same
color for every u ∈ V ( H ). For edge-colored graphs H = (VH , EH ) and G = (VG , EG )
we define H and G to be color-isomorphic if there is a color isomorphism between H
and G, that is, a graph isomorphism f : VH → VG such that uv and f (uv) have the
same color for every edge uv ∈ V ( H ). In both the vertex and edge colored cases, we
say that H is an induced colored-subgraph of G if there is a subset S ⊆ VG such that
H is color-isomorphic to G [S], the graph induced by S (which inherits colors from the
coloring of G). We write indvc ( H, G ) (resp. indec ( H, G )) for the number of sets S ⊆ VG
such that H is color-isomorphic to G [S] (i.e. the number of induced colored-subgraphs
of G isomorphic to H).
We can then extend the definitions in the natural way to their colored versions. In
particular G , Gk , 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 Gk 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.
Theorem 3.7. Let C > 0 and ∆ ∈ N and let p(·) be a bounded induced graph counting
polynomial for vertex (resp. edge) colored graphs. Then there is a deterministic (n/ε)O(1) time algorithm, which, given any n-vertex vertex (resp. edge) colored graph G of maximum
degree at most ∆ and any ε > 0, computes the inverse power sums p1, . . . , p m ( G ) of p( G ) for
m = C ln(n/ε).

4

The independence polynomial

4.1 The independence polynomial on bounded degree graphs
Proof of Theorem 1.1. First note that by a result of Shearer [42], cf. Scott and Sokal [41,
Corollary 5.7], we know that Z ( G )(z) 6= 0 for all all graphs G of maximum degree at
( ∆ − 1 ) ∆ −1

.
most ∆ and all z ∈ C that satisfy |z| ≤ λ∗ =
∆∆
Now fix an n-vertex graph G of maximum degree at most ∆. Let m = C ln(n/ε),
where C = C (λ, λ∗ ) is the constant in Corollary 2.3. As the kth coefficient of Z ( G ) is
equal to ind(•k , G ), where •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 α = β = 1). So by Theorem 3.1 we see that for k = 1, . . . , m we
can compute the first m inverse power sums of Z ( G ) in time (n/ε)O(1) . Noting that

13

the degree of Z ( G ) is at most n, Corollary 2.3 implies we can compute a multiplicative
ε-approximation to Z ( G )(λ) in time (n/ε)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 Ze ( G )(λ) 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.
( ∆ − 1 ) ∆ −1

. Then there exists a deterTheorem 4.1. Let ∆ ∈ N and let 0 ≤ λ < λ∗ (∆) :=
∆∆
ministic algorithm, which, given a graph G = (V, E) of maximum degree at most ∆ and ε > 0,
computes a multiplicative ε-approximation to Ze ( G )(λ) in time (|V |/ε)O(1) .
Proof. We apply the algorithm of Theorem 1.1 to compute multiplicative ε-approximations
A(λ) and A(−λ) to Z ( G )(λ) and Z ( G )(−λ) respectively in time (|V |/ε)O(1) . We have
e−ε Z ( G )(λ) ≤ A(λ) ≤ eε Z ( G )(λ) and e−ε Z ( G )(−λ) ≤ A(−λ) ≤ eε Z ( G )(−λ).
Taking half the sum of these equations and noting that Ze ( G )(λ) = 12 ( Z ( G )(λ) +
ZG (−λ)), we see that 12 ( A(λ) + A(−λ)) is a multiplicative ε-approximation to Ze ( G )(λ)
provided both Z ( G )(λ) and Z ( G )(−λ) have the same sign.
Clearly Z ( G )(λ) > 0 since the coefficients of Z ( G ) are nonnegative real numbers.
Also Z ( G )(−λ) > 0 because we know by the result of Scott and Sokal [41] that Z ( G )
does not vanish in the interval [−λ∗ , λ∗ ], and we know Z ( G ) is positive in the interval
[0, λ∗ ] since all the coefficients of Z ( G ) are nonnegative real numbers. Hence Z ( G ) is
positive on the whole interval [−λ∗ , λ∗ ] and in particular Z ( G )(λ) > 0.

4.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 zv for each v ∈ V define
Z ( G )((zv )v∈V ) =

∑

∏ zv .

v∈ I
I ⊆V
independent

Fix the complex values of zv , v ∈ V at which we wish to evaluate the multivariate independence polynomial. Now define a univariate graph polynomial q( G ) by
q( G )(λ) = Z ( G )((λzv )v∈V ), where q( G )(1) is what we wish to estimate. The coefficient
of λ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 ∏v∈ I zv . 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.
We extend q to vertex-colored graphs and denote this extension by qvc . Associate
a variable zi to each color i = 1, 2, . . .. The coefficient of λk of the polynomial qvc is
expressed as ∑ H α H indvc ( H, ·), where the sum is over all vertex-colored graphs H =
(VH , EH ) with coloring c : VH → N on k vertices and where α H = ∏u∈VH zc(u) if H is an
independent set and zero otherwise. Then qvc is a BIGCP in the vertex-colored setting,
cf. Subsection 3.3.
Suppose now that G has n vertices labelled 1, . . . , n. We view G as a vertex-colored
graph by giving the vertex labeled i color i for i = 1, . . . , n. Then qvc ( 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 [42], cf. Scott and Sokal [41, Corollary 5.7] also applies to
the multivariate independence polynomial (i.e. Z ( G )((zv )v∈V ) is non-zero whenever

14

|zv | < λ∗ (∆) for all v ∈ V and ∆( G ) ≤ ∆). This means q( G )(λ) is nonzero whenever
|λ| < M for some M > 1. It then follows that we can efficiently approximate q( G )(1)
and hence Z ( G )((zv )v∈V ) if G has maximum degree at most ∆ and if all zv satisfy
| z v | < λ∗ ( ∆ ).

4.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.
Proposition 4.2. If G is a claw-free graph of maximum degree ∆ and ζ is a root of the independence polynomial Z ( G ) of G then ζ ∈ R with ζ < − e( ∆1−1) .
Proof. The fact that ζ ∈ R is a result of Chudnovsky and Seymour [17]. The fact that
ζ must be negative follows because all the coefficients of Z ( G ) are positive. Now the
result of Shearer [42] states that

|ζ | ≥ λ∗ ( ∆) =

( ∆ − 1 ) ∆ −1
1
,
>
e( ∆ − 1)
∆∆

from which the proposition follows.
We also require the following lemma of Barvinok [5].
Lemma 4.3. For ρ ∈ (0, 1) we define
α = α(ρ) = 1 − exp(−ρ−1 ),

β = β(ρ) =

N = N (ρ) = ⌊(1 + ρ−1 ) exp(1 + ρ−1 )⌋,

σ = σ (ρ) =

1 − exp(−1 − ρ−1 )
> 1,
1 − exp(−ρ−1 )
N

αi
.
i
i =1

∑

The polynomial
φ ( z ) = φρ ( z ) =

1
σ

N

(αz)i
∑ i
i =1

has the following properties:
(i) φ(0) = 0 and φ(1) = 1 and φ has degree N;
(ii) If z ∈ C with |z| ≤ β then φρ (z) ∈ Sρ , where
Sρ := {z ∈ C | −ρ ≤ ℜ(z) ≤ 1 + 2ρ and

− 2ρ ≤ ℑ(z) ≤ 2ρ}.

Proposition 4.4. Fix λ = reiθ ∈ C with θ ∈ (−π, π ). Let Sρ be as in the previous lemma,
and let R − denote the negative real line. Then
( √
if θ ∈ [− π2 , π2 ];
[− 5ρr, 0]
λSρ ∩ R − ⊆
[−2ρr/| sin θ |, 0] otherwise.
Proof. Sρ is a bounded strip parallel to the real axis in the complex plane, so λSρ is
the same strip enlarged by a factor r and rotated by an angle θ. The proposition then
follows from elementary trigonometry.

15

Proof of Theorem 1.2. Recall that we are given a claw-free graph G of maximum degree
∆ and λ ∈ C that is not a negative real number and we wish to find a multiplicative
ε-approximation to Z ( G )(λ).
Set n := |V ( G )| and let λ = reiθ with θ ∈ (−π, π ). Set
(
1/9r (∆ − 1)
if θ ∈ [− π2 , π2 ];
ρ=
| sin θ |/6r (∆ − 1) otherwise,
and consider the polynomial g(z) = Z ( G )(λφρ (z)). Note that the degree of g is O(n)
since the degree of Z ( G ) is at most n and the degree of φρ is a constant N (ρ).
We will use Corollary 2.3 to find a multiplicative ε-approximation to g(1) = Z ( G )(λ)
in time (n/ε)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| ≤ β := β(ρ) and that (ii) the first m =
C ln(d/ε) inverse power sums of g can be computed in time (n/ε)O(1) , where d = O(n)
is the degree of g and C = C ( β, 1) is the constant in the statement of Corollary 2.3.
It remains to check (i) and (ii). To see (i), note first that by Lemma 4.3, φρ maps the
disk D = {z ∈ C | |z| ≤ β} into Sρ . By Proposition 4.4 and our choice of ρ, we have
λφρ ( D ) ∩ R − ⊆ (− 3( ∆1−1) , 0]. By Proposition 4.2 we know that if Z ( G )(ζ ) = 0 then

ζ ∈ R with ζ < − e( ∆1−1) . In particular this implies g(·) = Z ( G )(λφρ (·)) has no root in
the disk D.
For (ii), we show that we can compute the first m coefficients of g in time (n/ε)O(1) ,
which is sufficient by Proposition 2.1. Given a polynomial p(z) = ∑di=0 ai zi , write
i
p [m] ( z) := ∑m
i =0 a i z . Then we note that g[m ] = ( Z ( G ) ◦ ( λφ )) [m ] = ( Z ( G ) [m ] ◦ ( λφ[m ] )) [m ] ,
where we crucially use the fact that φ has no constant term since φ(0) = 0. In words,
to obtain g[m] (z) we substitute λφ[m] (z) into Z ( G )[m] (z) and keep the first m terms.
Thus, in O(m3 )-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/ε)O(1) (as in the proof of Theorem 1.1), from which we can find its first
m coefficients in time O(m2 ) by Proposition 2.1. This finishes the proof.
We remark that, for the (n/ε)O(1) running time in the algorithm above, the O(1)
in the exponent depends on λ and grows exponentially fast in r = |λ|. However, this
dependence can be brought down to O(|λ|1/2 ) by adapting Lemma 4.3 as described by
Barvinok [6].

5

The Tutte polynomial

Here we give a proof of Theorem 1.3.
Proof of Theorem 1.3. 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 ∆ and w such that for all q with |q| > K we have ZT ( G )(q, w) 6= 0 for all
graphs G of maximum degree at most ∆. This is exactly opposite to what we need to
apply Corollary 2.3, so let us define the graph polynomial p T by
p T ( G )(z) := z|V | ZT ( G )(1/z, w),

(17)

for any graph G = (V, E). Note that p T ( G ) has degree n := |V | and that if x is a multiplicative ε-approximation to p T ( G )(1/q, w), then qn x is a multiplicative ε-approximation
to ZT ( 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 ∆, we
can compute the first m inverse power sums of p T ( G ) in time (n/ε)O(1) , where m =
C ln(n/ε) and C = C (1/q, 1/K ) is the constant in Corollary 2.3. Corollary 2.3 then

16

implies we can compute a multiplicative ε-approximation to p T ( G )(1/q) and hence to
ZT ( G )(q, w) in time (n/ε)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/ε)O(1) .
Since the Tutte polynomial ZT ( 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 zk in p T ( G ) equals the coefficient of zn−k in
ZT ( 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 ⊆ 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 δ( F ) for the minimum degree of
the subgraph F, the coefficient of zn−k in ZT ( G ) can be expressed as

∑
F ⊆ G : δ ( F )≥1
|k ( F )|=|V ( F)|−k

w| E( F )| =

∑

∑

H

F ⊆ H : δ ( F )≥1
V ( F )=V ( H )
|k ( F )|=|V ( F)|−k

w| E( F )|ind( H, G ).

(18)

In fact the first sum can be taken over graphs H with at most 2k vertices. This is because
V ( H ) = V ( F ) and
V ( F )|
+ k.
|V ( F )| = k( F ) + k ≤
2
as F has no isolated vertices.
From (18), we can compute the coefficient of ind( H, G ) by checking all subsets of
E( H ) in time O(2E( H ) ) = O(2∆|V ( H )|). This implies that p T is a BIGCP (taking α = 2
and β = 2∆ ).
Remark 5.1. Csikvári and Frenkel [18] introduced graph polynomials of bounded exponential
type and showed that these polynomials have bounded roots on bounded degree graphs.
This was utilized in [40] 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 [40] can be adapted to run in polynomial time on bounded degree
graphs.

6

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.

6.1 Partition functions for edge-colored graphs
Let G = (V, E) be a graph. Suppose also that for each e ∈ E we have a symmetric
k × k-matrix Ae . Let us write A = ( Ae )e∈ E. Then we can extend the definition of the

17

partition function of a spin model as follows:

∑

p( G )(A) =

∏

φ:V →[k ] e ={ u,v }∈ E

Aeφ( u),φ( v).

(19)

We will refer to p( G )(A) as the partition function of A. In [24] this is called a Markov
random field (if the Ae are nonnegative) and in [36] this is called a multi spin system.
Clearly, if all Ae are the same, this just reduces to the partition function of a spin model.
We have the following result, which implies Theorem 1.4.
Theorem 6.1. Let ∆, k ∈ N. Then there exists a deterministic algorithm, which, given a graph
G = (V, E) of maximum degree at most ∆, symmetric k × k matrices Ae , e ∈ E, such that
| Aei,j − 1| ≤ 0.34/∆ for all i, j = 1, . . . , k and e ∈ E, and ε > 0, computes a multiplicative
ε-approximation to p( G )(A) in time (|V |/ε)O(1) .

Remark 6.1. The constant 0.34 may be replaced by 0.45 if ∆ ≥ 3 and by 0.54 if ∆ is large
enough; see [8].
Proof. Let J be the all ones matrix. For z ∈ C, let Be (z) := J + z( Ae − J ) and let
A′ (z) := ( Be (z))e∈ E. Define a univariate polynomial q by
q( G )(z) = k−|V | p( G )(A′ (z)).

(20)

Then q( G )(0) = 1 and q( G )(1) = k−|V | p( G )(A). Barvinok and Soberón [8, Theorem
1.6] showed that there exists a constant δ > 0 such that q( G )(z) 6= 0 for all z satisfying
|z| ≤ 1 + δ.
We will show that for any n-vertex graph G of maximum degree at most ∆, we
can compute the first m inverse power sums of q( G ) in time (n/ε)O(1) , where m =
C ln(n/ε) and C = C (1, 1 + δ) is the constant in Corollary 2.3. Noting that the degree
of q( G ) is at most | E| ≤ n∆/2, Corollary 2.3 implies we can compute a multiplicative εapproximation to q( G )(1) in time (n/ε)O(1) . So it remains to show that we can compute
the first m inverse power sums of q( G ) in time (n/ε)O(1) .
We will show that we can interpret q as an edge-colored BIGCP, cf. Subsection 3.3.
Suppose G has ℓ edges, labeled 1, . . . , ℓ. Color the edge labeled i with color i for i =
1, . . . , ℓ. By definition, q( G )(z) satisfies
q( G )(z) = k−n

∑

∏

( J + (z( Ae − J )))φ(u),φ(v)

φ:V →[k ] e ={ u,v }∈ E

=k

−n

|E|

∑z
i =0

i



∑

∑



e

( A − J )φ(u),φ(v) .

∏

F ⊆ E φ:V →[k ] e ={ u,v }∈ F
| F |=i

(21)

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 zi in (21) can be written as
follows:


e
k−n ∑ kn−|V ( H )|
(
A
−
J
)
∑
∏
φ( u ),φ( v ) indec ( H, G )
H ∈G2i
| E ( H )|=i

=

∑
H ∈G2i
| E ( H )|=i

φ:V ( H )→[k ] e ={ u,v }∈ E ( H )



k

−|V ( H )|

∑

∏

e



( A − J )φ(u),φ(v) indec ( H, G ),

φ:V ( H )→[k ] e ={ u,v }∈ E ( H )

(22)

where we interpret G2i 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

18

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 α = 2 and β = 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/ε)O(1). This finishes the proof.

6.2 Partition functions of graph homomorphisms with multiplicities
Let G = (V, E) be graph. Suppose that for each e ∈ E we have a symmetric k × k-matrix
Ae . Let us write A = ( Ae )e∈ E. Let n = |V | and let µ = (µ1 , . . . , µk ) with µi ∈ Z ≥1 for
each i be such that that ∑ki=1 µi = n. We call such µ a composition of n in k parts. Barvinok
and Soberón [9] define the partition function of graph homomorphisms with multiplicities µ
as
(23)
pµ ( G )(A) =
∏ Aeφ(u),φ(v).
∑
φ:V →[k ] e ={ u,v }∈ E
|φ−1 ( i )|=µ i

We refer to [9] 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:
Theorem 6.2. Let ∆, k ∈ N. Then there exists a deterministic algorithm, which, given a graph
G = (V, E) of maximum degree at most ∆, a composition µ of |V | in k parts, symmetric k × k
matrices Ae , e ∈ E such that | Aei,j − 1| ≤ 0.1/∆ for all i, j = 1, . . . , k and e ∈ E, and ε > 0,

computes an ε-approximation to pµ ( G )(A) in time (|V |/ε)O(1) .

7

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.

7.1 Partition functions for vertex-colored graphs
Let G = (V, E) be a graph. Suppose that we have k-color edge-coloring models hv for
each v ∈ V. Let us write H = (hv )v∈V . Often the pair ( G, H) is called a signature
grid, cf. [15, 16, 14]. Then we can extend the definition of the partition function of an
edge-coloring model as follows:
p( G )(H) =

∑ ∏ hv (φ(δ(v))).

(24)

φ:E →[k ] v ∈V

We will refer to p( G )(H) as the partition function of 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, H) cf. [15, 16, 14]. We have the following result,
which implies Theorem 1.5.
Theorem 7.1. Let ∆, k ∈ N. Then there exists a deterministic algorithm, which, given a graph
G = (V, E) of maximum degree at most ∆, k-color edge-coloring models hv , v ∈ V, that satisfy
|hv (φ) − 1| ≤ 0.35/(∆ + 1) for all φ ∈ N k and v ∈ V, and ε > 0, computes a multiplicative
ε-approximation to p( G )(H) in time (|V |/ε)O(1) .
Remark 7.1. The constant 0.35 may be replaced by 0.47 if ∆ ≥ 3 and by 0.56 if ∆ is large
enough; see [40]. Moreover, for readers familiar with the orthogonal group invariance
of these partition functions one can use Corollary 6b from [40] to find a larger family of
edge-coloring models for which the partition function can be efficiently approximated.

19

Proof. Let J denote the constant ones function J : N k → C (defined by J (φ) = 1 for all
φ ∈ N k ). Let for z ∈ C, gv (z) := J + z(hv − J ) and let H(z) := ( gv (z))v∈V . Consider the
following univariate polynomial:
q( G )(z) := k−| E| p( G )(H(z)).

(25)

Observe that q( G )(1) = k−| E| p( G )(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 )(H) is replaced by approximating an evaluation of a univariate polynomial.
By Corollary 6a from [40] (which is valid for multigraphs) there exists δ > 0 such
that q( G )(z) 6= 0 whenever |z| ≤ 1 + δ. We will show (in Theorem 7.2) that for any
n-vertex graph G of maximum degree at most ∆, we can compute the first m inverse
power sums of q( G ) in time (n/ε)O(1) , where m = C ln(n/ε) and C = C (1, 1 + δ) 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 ε-approximation to q( G )(1) in time (n/ε)O(1) .
Ideally we would like to do this using Theorem 3.1 just as in the proof of Theorem
6.1. Since partition functions of edge-coloring models are multiplicative, the polynomial
q is also multiplicative and it has constant term equal to 1. So to be able to apply
Theorem 3.1 we need only check that the coefficients of q can be expressed as linear
combinations of (colored) induced graph counts. This is in fact proved in [40] if all hv
are equal, but there it is not clear whether the coefficients λ H,i in (11) can be computed
efficiently. So instead of directly applying Theorem 3.1 we will have to do a little more
work, which we postpone to the next section.

7.2 Computing coefficients of q(G )(z)
By definition,
q( G )(z) = k−| E|

∑ ∏ ( J + z(hv − J ))(φ(δ(v)))

φ:E →[k ] v ∈V
n

= k−| E| ∑ zi
i =0
n

= k−| E| ∑ zi
i =0




∑

∑

∏ (hu − J )(φ(δ(u)))

U ⊆V φ:E →[k ] u ∈U
|U |=i

∑

k| E\ E(U )|

∑




u
(
h
−
J
)(
φ
(
δ
(
u
)))
,
∏

(26)

φ:E (U )→[k ] u ∈U

U ⊆V
|U |=i

where for U ⊆ V, E(U ) denotes the set of edges of G that are incident with at least one
vertex of U.
The second sum inside the brackets of the third line of (26) is almost the partition
function of (h u − J )u∈U , except that the pair (U, E(U )) may not actually be a graph as
some of the edges of E(U ) are not spanned by U. We will refer to such a graph-like
structure as a fragment and the edges in E(U ) that are ‘sticking out’ (i.e. not spanned
by U) as half edges. Formally, a fragment, is a pair ( H, κ ), where H is a vertex-colored
graph and where κ is a map κ : V ( H ) → {0, 1, . . . , ∆}, which records the number of half
edges incident with each vertex. Suppose G has n vertices labeled 1, . . . , n. From now
on we will consider the graph G as a vertex-colored graph, where vertex i gets color i
for i = 1, . . . , n. For U ⊆ V we let G (U ) be the fragment ( G [U ], κ ) where κ (u) is equal
to the number of edges that connect u with V \ U. Note that the graph G itself can be
thought of as a fragment by taking the map κ : V ( G ) → {0, . . . , ∆} to be κ (v) = 0 for
all v ∈ V ( G ).
Clearly, for each U of size i the expression inside the second sum of the third line
of (26) only depends on the isomorphism class of the fragment G (U ). (An isomorphism

20

from a fragment ( H, κ ) to a fragment ( H ′ , κ ′ ) is an isomorphism α of the underlying
vertex-colored graphs and such that for each u ∈ V ( H ), κ (u) = κ ′ (α(u)).) For a fragment F = ( H, κ ) let E( F ) denote the set of edges of F including half edges and let V ( F )
denote the vertex set of the underlying graph H. Assume that for each i = 1, 2, . . . we
have a k-color edge coloring-model hi and let H = (hi )i≥1 Then define,
p( F )(H) :=

∑

∏

hv (φ(δ(v))).

(27)

φ:E ( F )→[k] v ∈V ( F )

Here we implicitly identify the the color of a vertex of H with the vertex itself. Define
for a fragment F = ( H, κ ), ind∗ ( F, G ) to be the number of sets U of size |V ( F )| such
that G (U ) is isomorphic to F. Writing H − J = (h i − J )i≥1, we can rewrite (26) as
n

q( G )(z) = k−| E| ∑ zi
i =0
n

=

∑z
i =0

i





∑
F =( H,κ )
|V ( H )|=i

∑
F =( H,κ )
|V ( H )|=i

k

k| E|−| E( F )| p( F )(H − J )ind∗ ( F, G )

−| E ( F )|


p( F )(H − J )ind ( F, G ) ,
∗


(28)

where the sum runs over fragments. This shows how to extend q to vertex-colored
graphs. Let us denote the coefficient of zi in (28) by ei . In [40] it is proved that in case
all hi are equal, ind∗ ( F, G ) can be expressed as a linear combination of the parameters
ind( H, G ) for certain graphs H. As mentioned above, the coefficients in this expression
may not be easy to compute (at least we do not know how to do this). So we will
have to work with the parameters ind∗ ( F, ·) instead. This is not a severe problem, since
essentially if we replace ind in (11) by ind∗ , then Theorem 3.1 remains valid. Indeed,
we have the following theorem.
Theorem 7.2. Let C > 0 and ∆ ∈ N. Then there is a deterministic (n/ε)O(1) -time algorithm,
which, given any n-vertex graph G of maximum degree at most ∆ and any ε > 0, computes the
inverse power sums p1 , . . . , p m of q( G ) for m = C ln(n/ε).
The proof of Theorem 7.2 follows the same line as the proof of Theorem 3.1. Essentially we need to replace graphs by fragments in the proof and check that everything
remains valid. For completeness we will give the proof.
We first need to note that for a fragment F1 = ( H1 , κ1 ) the graph parameter ind∗ ( F1 , ·)
can be extended to the collection of all fragments as follows: for a fragment F2 =
( H2 , κ2 ) we let ind∗ ( F1 , F2 ) denote the number of sets S ⊆ V ( H2 ) such that H1 is isomorphic to H2 [S] as vertex-colored graphs and such that for each vertex v of H1 we
have that the number of neighbours of v in V ( H2 ) \ S is equal to κ1 (v) − κ2 (v). Then
for two fragments F1 and F2 we have
ind∗ ( F1 , ·) · ind∗ ( F2 , ·) =

∑ c FF1,F2 ind∗ ( F, ·),

(29)

F

where the sum runs over all fragments F and where for a fragment F, c FF1 ,F2 denotes
the number of pairs of subsets (S, T ) of V ( F ) such that S ∪ T = V ( F ) and F1 = F (S)
and F2 = F ( T ). (Here F (S) is the fragment induced by S, i.e., if F = ( H, κ ), then
F (S) = ( H [S], α) where for s ∈ S we set α(s) = deg H (s) − degH [S] (s) + κ (s).) We call a
fragment F = ( H, κ ) connected if the graph H is connected. We now adapt some of the
statements and proofs of the results in Section 3 to include fragments.
We start with some definitions. By F we denote the collection of all fragments and
by Fk for k ∈ N we denote the collection of fragments with at most k vertices. For two
fragments F1 = ( H1 , κ1 ) and F2 = ( H2 , κ2 ), F1 ∪ F2 := ( H, κ ), where H = H1 ∪ H2 and

21

κ : V ( H1 ∪ V ( H2 ) → {0, 1, . . . , ∆} is the map whose restriction to V ( H1 ) is κ1 and whose
restriction to V ( H2 ) is κ2 . An invariant of fragments is a function f : F → S for some set
S that takes the same value on isomorphic fragments. Call an invariant of fragments
f multiplicative if f (∅) = 1 and f ( F1 ∪ F2 ) = f ( F1 ) f ( F2 ) for all fragments F1 , F2 . The
maximum degree of a fragment F = ( H, κ ) is equal to the maximum of deg(v) + κ (v)
over v ∈ V ( G ).
Lemma 7.3. Let F = ( H, κ ) be a connected fragment on k vertices and let ∆ ∈ N. Then there
is an O(k2 n2 ∆2( k−1) )-time algorithm, which, given any n-vertex fragment F̂ with maximum
degree at most ∆, computes the number ind∗ ( F, F̂ ).
Note that Lemma 7.3 enables us to test for isomorphism of fragments between
bounded degree fragments when |V ( F )| = |V ( F̂ )|.
Proof. This follows immediately from the proof of Lemma 3.2. We apply the proof of
Lemma 3.2 to the underlying graphs and then remove any potential embedding that
either violates the vertex coloring constraints or the constraints that κ imposes.
We call an invariant of fragment f : F → C additive if for each F1 , F2 ∈ F we have
f ( F1 ∪ F2 ) = f ( F1 ) + f ( F2 ). The following variation of a lemma due to Csikvári and
Frenkel [18] has exactly the same proof as Lemma 3.5; one just needs to replace graph
by fragment everywhere in the proof.
Lemma 7.4. Let f : F → C be an invariant of fragments given by f (·) := ∑ F ∈F a F ind∗ ( F, ·).
Then f is additive if and only if a F = 0 for all fragments F that are disconnected.
We now sketch the proof of Theorem 7.2.

7.2.1

Proof of Theorem 7.2

Let ζ 1 , . . . , ζ d ∈ C be the roots of the polynomial q( G ) and recall that for ℓ ∈ N, pℓ is
the ℓth inverse power sum of the ζ i . Here d denotes the degree of q( G ) = ∑di=0 ei zi ,
which is at most n. By (28), for i ≥ 1, the ei can be expressed as linear combinations
of induced fragments counts of fragments with at most ℓ vertices. Since e1 = − p1 , this
implies that the same holds for p1 . By induction, (29) and (13) (using that e0 = 1) we
have that for each ℓ
pℓ = ∑ a F,ℓ ind∗ ( F, G ),
(30)
F ∈Fℓ

for certain, yet unknown, coefficients a F,ℓ .
Since q is multiplicative, the inverse power sums are additive. Thus Lemma 7.4
implies that a F,ℓ = 0 if F is not connected. Denote by C ′ ℓ ( G ) the set of connected
fragments F of order at most ℓ such that ind∗ ( F, G ) 6= 0. This way we can rewrite (30)
as follows:
pℓ = ∑ a F,ℓ ind∗ ( F, G ).
(31)
F ∈C ′ ℓ ( G )

The next lemma says that we can compute the coefficients a F,ℓ efficiently for ℓ =
1, . . . , m, where m = C ln(n/ε).
Lemma 7.5. There is an O(n/ε)O(1) -time algorithm, which given an n-vertex graph G and
ε > 0, computes and lists the coefficients a F,ℓ in (31) for all F ∈ C ′ ℓ ( G ) and all ℓ = 1, . . . , m =
C ln(n/ε).
Proof. Using the algorithm of Lemma 3.4, we first compute the sets Tℓ consisting of all
subsets S of V ( G ) such that |S| ≤ ℓ and G [S] is connected, for ℓ = 1 . . . , m. This takes
time bounded by (n/ε)O(1) . The collection C ′ ℓ ( G ) can be obtained from Tℓ by looking

22

for each S ∈ Tℓ and each v ∈ S how many neighbours v has in G \ S. So the total time
to compute and list the C ′ ℓ ( G ) is bounded by (n/ε)O(1) .
To prove the lemma, let us fix ℓ ≤ m and show how to compute the coefficients a F,ℓ ,
assuming that we have already computed and listed the coefficients a F,ℓ′ for all ℓ′ < ℓ.
Let us fix F ∈ C ′ ℓ ( G ). By the identities (13), it suffices to compute the coefficient of
ind∗ ( F, ·) in ei pℓ−i for i = 1, . . . , ℓ (where we set p0 = 1). By (28), (29) and (30) we know
that the coefficient of ind∗ ( F, ·) in ei pℓ−i is given by

∑

∑

F1 ∈Fi F2 ∈Fℓ−i
|V ( F1 )|=i

=

∑
S,T ⊆V ( F )
S ∪ T =V ( F )
|S|=i,| T |≤ℓ−i

c FF1,F2 a F2 ,(ℓ−i) ·

a F ( T ),(ℓ−i) ·

p( F1 )(H − J )
k| E( F1)|

p( F (S))(H − J )
.
k| E( F ( S))|

For each such pair (S, T ), we need to compute p( F (S))( J − H)k−| E( F ( S))| and look up
a F ( T ),(ℓ−i). We can compute p( F (S))( J − H)k−| E( F ( S))| in time bounded by O(k∆ℓ ) =

(n/ε)O(1) .
Looking up a F ( T ),(ℓ−i) in the given list requires us to test isomorphism of F ( T )
with each fragment in C ′ ℓ−i ( G ) (noting that a F ( T ),(ℓ−i) = 0 if F ( T ) 6∈ C ′ (ℓ−i) ( G ) by
Lemma 7.4). Using Lemma 7.3 to test for isomorphism, this takes time at most
O(|C ′ (ℓ−i) ( G )|(ℓ − i )2 ∆2(ℓ−i−1)) = O(n/ε)O(1) .

Here we use Lemma 3.3 to bound |C ′ (ℓ−i) ( G )| ≤ |T(ℓ−i) ( G )|. Together, all this implies

that the coefficient of ind∗ ( F, ·) in pℓ−i ei can be computed in time bounded by (n/ε)O(1) ,
and so the coefficient a F,ℓ can be computed in time (n/ε)O(1) . Thus all coefficients a F,ℓ
for F ∈ C ′ ℓ ( G ) can be computed and listed in time bounded by |C ′ ℓ ( G )|(n/ε)O(1) =
(n/ε)O(1) . This can be done for each ℓ = 1, . . . , m in time (n/ε)O(1) .
To finish the proof of the theorem, we compute p ℓ for each ℓ = 1, . . . , m by adding
all the numbers a F,ℓ ind∗ ( F, G ) over all F ∈ C ′ ℓ ( G ). This can be done in time
O(m|C ′ m ( G )|n2 ∆2( m−1) ) = (n/ε)O(1) ,
where we have used that computing ind∗ ( F, G ) with F ∈ C ′ ℓ ( G ) takes time bounded by
O(n2 ∆2( m−1) ) by Lemma 7.3. This finishes the proof.

8

Concluding remarks and open questions

In this paper we have presented a direct connection between the absence of complex
roots for a large class of graph polynomials (BIGCPs) and the existence of (deterministic) algorithms to efficiently approximate evaluations of these polynomials. We have
illustrated its use by giving deterministic polynomial-time approximation algorithms
for evaluations of the Tutte polynomial, the independence polynomial and graph polynomials obtained from spin and edge-coloring models at complex numbers on bounded
degree graphs.
As is noted in the introduction Theorem 1.1 does not allow us to efficiently approximate the independence polynomial at λ for λ∗ ≤ λ < λc , while this can be done with
the correlation decay approach cf. Weitz [50]. However, confirming a conjecture of
Sokal [45], Peters and the second author [38] proved the following:

23

Theorem 8.1. Let ε > 0 and ∆ ∈ N. Then there exists δ > 0 such that for any graph
G = (V, E) of maximum degree at most ∆, and λv ∈ C for v ∈ V that satisfy

|ℑ(λv )| ≤ δ, and 0 ≤ ℜ(λ) ≤ (1 − ε)

( ∆ − 1 ) ∆ −1
( ∆ − 2) ∆

(32)

for all v ∈ V, we have Z ( G )((λv )v∈V ) 6= 0.

Now combining this result with the approach in Section 4.3, it follows that with the
methods in this paper we can efficiently approximate the independence polynomial at
λ for λ < λc , thereby giving a different proof of Weitz’s result.
Let us restate another conjecture of Sokal [30, Conjecture 21], which, if true, would
by the methods of the present paper imply that we have an efficient algorithm for
approximately counting the number of (∆ + 1)-colorings in any graph of maximum
degree at most ∆.
Question 8.1. Let ∆ ∈ N. Is it true that ZT ( G )(−1, q) 6= 0 for every q ∈ C satisfying
ℜ(q) > ∆ and every graph G of maximum degree at most ∆?

This connection between absence of complex roots and efficient approximation algorithms naturally leads to the question of how hard it is to approximate evaluations of
these graph polynomials close to (complex) roots. In light of this we remark that some
progress on this question has been made. As mentioned in the introduction, there exists
a sequence of trees Tn of maximum degree at most ∆ and λn < −λ∗ with λn → −λ∗
such that Z ( Tn , λn ) = 0. This was utilized by Galanis, Goldberg and Štefankovič, to
show that it is NP hard to approximate ZG (λ) when λ < −λ∗ (∆).
Another question that arises naturally is the following. Barvinok [2, 5] found quasipolynomial-time approximation algorithms for computing the permanent of certain matrices, based on absence of zeros. Our method for computing inverse power sums of
BIGCPs on bounded degree graphs presented in Section 3 does not seem to apply to
permanents of general matrices. It would be very interesting to find a more general
method that also applies to permanents.
Our algorithmic results in Section 3 can be interpreted as giving a fixed parameter
tractability result for determining ind( H, G ) for certain graphs H. If G has bounded
degree, the algorithm runs in time 2O(|V ( H )||V ( G )|O(1) . However, the algorithm only
works for graphs H for which ind( H, ·) are coefficients of a multiplicative graph polynomial. Very recently, we were able to extend the algorithm to all graphs H; see [37].
A natural question is whether our approach can be extended to other classes of graphs
such as planar graphs for example. More concretely, let us state the following question.
Question 8.2. Is there an algorithm, which given a planar (or more generally, bounded
genus) graph G and k ∈ N, returns the number of independent sets of size k of G in
time bounded by 2O( k) |V ( G )|O(1) ?

Acknowledgements
We thank Alexander Barvinok for stimulating discussions, useful remarks and for sharing the results in [6] with us. We thank Andreas Galanis for informing us about [46].
We are grateful to Pinyan Lu for some useful remarks on an earlier version of this paper.
We moreover thank the anonymous referees for helpful comments and suggestions,
improving the presentation of the paper.

24

References
[1] M. Bayati, D. Gamarnik, D. Katz, C. Nair and P. Tetali, Simple deterministic approximation algorithms for counting matchings. In Proceedings of the thirty-ninth
annual ACM symposium on Theory of computing (pp. 122–127), ACM, 2007.
[2] A. Barvinok, Computing the permanent of (some) complex matrices, Foundations
of Computational Mathematics (2014) 1–14.
[3] A. Barvinok, Computing the partition function for cliques in a graph, Theory of
Computing 11 (2015), Article 13 pp. 339–355
[4] A. Barvinok, Computing the partition function of a polynomial on the Boolean
cube, arXiv preprint, arXiv:1503.07463 (2015).
[5] A. Barvinok, Approximating permanents and hafnians, Discrete Analysis, 2017:2,
34 pp.
[6] A. Barvinok, Personal communication (2016).
[7] A. Barvinok, Combinatorics and Complexity of Partition Functions Vol. 30 of Algorithms and Combinatorics, Springer, 2017.
[8] A. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms, Combinatorica (2016). doi:10.1007/s00493-016-3357-2.
[9] A. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms with multiplicities, Journal of Combinatorial Theory, Series A 137 (2016)
1–26.
[10] C. Borgs, J. Chayes, J. Kahn and L. Lovász, Left and right convergence of graphs
with bounded degree, Random Structures and Algorithms 42 (2013) 1–28.
[11] R. Bubley, M. Dyer, C. Greenhill and M. Jerrum: On approximately counting colorings of small degree graphs, SIAM Journal on Computing 29 (1999) 387–400.
[12] A. Bulatov and M. Grohe, The complexity of partition functions, Theoretical Computer Science 348 (2005) 148–186.
[13] J. Cai, X. Chen and P. Lu, Graph homomorphisms with complex values: A dichotomy theorem, SIAM Journal on Computing 42 (2013) 924–1029.
[14] J. Cai, H. Guo and T. Williams, A complete dichotomy rises from the capture
of vanishing signatures, In: Proceedings of the forty-fifth annual ACM symposium on
Theory of computing, pp. 635–644. ACM, 2013.
[15] J. Cai, S. Huang and P. Lu, From Holant to #CSP and Back: Dichotomy for Holantc
Problems. In ISAAC, pages 253–265, 2010.
[16] J. Cai, P. Lu and M. Xia, Computational complexity of Holant problems, SIAM
Journal on Computing 40 (2011) 1101–1132.
[17] M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a
clawfree graph, Journal of Combinatorial Theory, Series B 97 (2007) 350–357.
[18] P. Csikvári and P. E. Frenkel, Benjamini–Schramm continuity of root moments of
graph polynomials, European Journal of Combinatorics 52 (2016) 302–320.
[19] P. de la Harpe, and V.F.R. Jones, Graph invariants related to statistical mechanical
models: examples and problems, Journal of Combinatorial Theory, Series B 57 (1993)
207–227.
[20] M. Dyer and C. Greenhill, On Markov chains for independent sets, Journal of Algorithms 35 (2000) 17–49.
[21] M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms,
Random Structures and Algorithms 17 (2000) 260–289.

25

[22] A. Galanis, L.A. Goldberg, D. Štefankovič, Inapproximability of the independent set polynomial below the Shearer threshold, arXiv preprint, arXiv:1612.05832
[cs.CC], 2016.
[23] A. Galanis, D. Štefankovič, E. Vigoda and L. Yang: Ferromagnetic Potts model,
Refined #BIS-hardness and related results. In RANDOM 2014, LNCS 6845, pp.
677–691 2014. Full version available at http://arxiv.orgabs/1311.4839.
[24] D. Gamarnik and D. Katz, Correlation decay and deterministic FPTAS for counting
list-colorings of a graph, Journal of Discrete Algorithms 12 (2012) 29–47.
[25] D. Garijo, A. Goodall and J. Nešetřil, Jaroslav, On the number of B-flows of a graph,
European Journal of Combinatorics 35 (2014) 273–285.
[26] L.A. Goldberg and H. Guo, The complexity of approximating complex-valued
Ising and Tutte partition functions, arXiv preprint arXiv:1409.5627 (2014).
[27] L.A. Goldberg and M. Jerrum, Approximating the partition function of the ferromagnetic Potts model, Journal of the ACM 59 (2012) 1–25.
[28] L.A. Goldberg, and M. Jerrum, The complexity of computing the sign of the Tutte
polynomial (and consequent #P-hardness of approximation) In Automata, Languages, and Programming, pp. 399–410, Springer Berlin Heidelberg, 2012.
[29] N.J. Harvey, P. Srivastava and J. Vondrák, Computing the independence polynomial in Shearer’s region for the LLL, arXiv preprint, arXiv:1608.02282, 2016.
[30] B. Jackson, Zeros of chromatic and flow polynomials of graphs, Journal of Geometry 76 (2003) 76–95.
[31] B. Jackson, A. Procacci and A.D. Sokal, Complex zero-free regions at large |q| for
multivariate Tutte polynomials (alias Potts-model partition functions) with general
complex edge weights, Journal of Combinatorial Theory, Series B 103 (2013) 21–45.
[32] M. Jerrum, A very simple algorithm for estimating the number of k-colorings of a
low-degree graph, Random Structures and Algorithms 7 (1995) 157–165.
[33] M. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the Ising
model, SIAM Journal on computing 22 (1993) 1087–1116.
[34] T. Lee and T. Yang, Statistical theory of equations of state and phase transitions. I.
Theory of condensation, Physical Review 87 (1952): 404.
[35] C. Lin, J. Liu and P. Lu, A simple FPTAS for counting edge covers, in: Proceedings of
the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp341–348,
SIAM, 2014.
[36] P. Lu and Y. Yin, Improved FPTAS for multi-spin systems, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp 639–654,
Springer Berlin Heidelberg, 2013.
[37] V. Patel, G. Regts, Computing the number of induced copies of a fixed graph in a
bounded degree graph, arXiv preprint, arXiv:1707.05186 [cs.DS], 2017.
[38] H. Peters, G. Regts, On a conjecture of Sokal concerning roots of the independence
polynomial, arXiv preprint, arXiv:1701.08049[math.CO], 2017.
[39] G. Regts, Graph Parameters and Invariants of the Orthogonal Group, PhD thesis, University of Amsterdam, 2013.
[40] G. Regts, Zero-free regions of partition functions with applications to algorithms
and graph limits, Combinatorica (2017). doi:10.1007/s00493-016-3506-7.
[41] A.D. Scott and A.D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics 118 (2005) 1151–1261.
[42] J.B. Shearer, On a problem of Spencer, Combinatorica 5 (1998) 241–245.

26

[43] A. Sinclair, P. Srivastava and M. Thurley, Approximation algorithms for two-state
anti-ferromagnetic spin systems on bounded degree graphs, Journal of Statistical
Physics 155 (2014) 666–686.
[44] A. Sly and N. Sun, The computational hardness of counting in two-spin models
on d-regular graphs, in Proceedings of the 53rd Annual Symposium on Foundations of
Computer Science (FOCS), 2012 IEEE, pp. 361–369. IEEE, 2012.
[45] A. Sokal, A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models, Markov Processes And Related Fields 7 (2001) 21–38.
[46] P. Srivastava, Approximating the hard core partition function with negative activities. Available at http://www.its.caltech.edu/ piyushs/docs/approx.pdf
[47] B. Szegedy, Edge-coloring models and reflection positivity, Journal of the American
Mathematical Society 20 (2007) 969–988.
[48] B. Szegedy, Edge coloring models as singular vertex-coloring models, in: Fete of
Combinatorics and Computer Science (G.O.H. Katona, A. Schrijver, T.Szönyi, editors),
Springer, Heidelberg and János Bolyai Mathematical Society, Budapest (2010) 327–
336.
[49] E. Vigoda, Improved bounds for sampling colorings, Journal of Mathematical Physics
41 (2000), 1555–1569.
[50] D. Weitz, Counting independent sets up to the tree threshold, in Proceedings of the
thirty-eighth annual ACM symposium on Theory of computing, STOC 06, pages 140–
149, New York, NY, USA, 2006. ACM.

27

