Computing the number of induced copies of a fixed
graph in a bounded degree graph

arXiv:1707.05186v2 [cs.DS] 20 Sep 2017

Viresh Patel∗

Guus Regts†.

September 21, 2017

Abstract
In this paper we show that for any graph H of order m and any graph G of order
n and maximum degree ∆ one can compute the number of subsets S of V ( G ) that
induces a graph isomorphic to H in time O(cm · n) for some constant c = c(∆) > 0. This
is essentially best possible.
Keywords: induced graph, computational counting, fixed parameter tractability.

1

Introduction

For two graphs H and G we denote by ind( H, G ) the number of subsets of the vertex
set of G that induce a graph that is isomorphic to H. (We recall that 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 .)
Throughout we take G and H to have n and m vertices respectively.
Understanding the numbers ind( H, G ) for different choices of H gives us much
important information about G. Determining these induced subgraph counts is closely
related to determining subgraph counts and homomorphism counts; these parameters
play a central role in the theory of graph limits [11], and frequently appear in statistical
physics see e.g. Section 2.2 in [14] and the references therein.
When H and G are both part of the input, computing ind( H, G ) is clearly an NPhard problem because it includes the problem of determining the size of a maximum
clique in G. When the graph H is fixed, the brute-force algorithm takes time O(nm ) and
improvements have been made for certain choices of the pattern graph H [9, 12].
It is natural to consider this problem from a fixed parameter tractability (FPT) perspective. In general computing ind( H, G ) when parameterizing by m = | H | is W [1]hard because even deciding whether G contains an independent set of size m is W [1]hard [7]. Curticapean, Dell and Marx [6] prove a number of interesting dichotomy
results for W [1]-hardness using the treewidth of H (and of a certain class of graphs
obtained from H) as an additional parameter.
However, when the graph G is of bounded degree, which is often of interest in statistical physics, the problem is no longer W [1]-hard. Indeed, Curticapean, Dell, Fomin,
∗ Korteweg

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

1

Goldberg, and Lapinskas [5, Theorem 13] showed that for a graph H on m vertices and a
bounded degree graph G on n vertices, ind( H, G ) can be computed in time O(nmO( m) ),
thus giving an FPT algorithm in terms of m. In the present paper we go further and
give an algorithm with essentially optimal running time. We assume the standard
word-RAM machine model with logarithmic-sized words.
Theorem 1.1. There is an algorithm which, given an n-vertex graph G of maximum degree at
most ∆, and an m-vertex graph H computes ind( H, G ) in time Õ(n(4∆)2m + 210m ). (Here the
Õ-notation means that we suppress polynomial factors in m.)
Remark 1.1. Theorem 13 in [5] in fact concerns vertex-coloured graphs H and G. Our
proof of Theorem 1.1 also easily extends to the coloured setting. We discuss this in
Section 4.
The running time here is essentially optimal under the exponential time hypothesis.
Indeed, if we could find an algorithm with an improved running time O(co ( m) poly(n))
(for some constant c possibly dependent on ∆), we could use it to determine the size of
a maximum independent set in time O(nco ( n) poly(n)) = O(co ( n) poly(n)), which is not
possible (even in graphs of maximum degree 3) under the exponential time hypothesis;
see [8, Lemma 2.1].
Note that our algorithm allows us to compute ind( H, G ) in polynomial time in | G |,
even when | H | is logarithmic in | G | (and G has bounded degree). The special case of this
when H is an independent set was a crucial ingredient in our recent paper [13], which
uses the Taylor approximation method of Barvinok [2] to give (amongst others) a fully
polynomial time approximation algorithm for evaluating the independence polynomial
for bounded degree graphs. Our present paper completes the running time complexity
picture for computing ind( H, G ) on bounded degree graphs G.
We add a few remarks to give further perspective on the problem. Note that computing ind( H, G ) in time Õ(∆m n) is relatively straightforward for G of bounded degree
∆ when H is connected (see Lemma 2.2). Thus the difficulty lies in graphs H that have
many components. Note also that Curticapean et al. [5] use the fact that induced graph
counts can be expressed in terms of homomorphism counts (see e.g. [11]) and that
homomorphism counts from H to G can be computed in time Õ(∆m n) in their FPT
algorithm. However the limiting factor is the time cost of expressing induced graph
counts in terms of homomorphism graph counts, which is significantly larger than the
running time of our algorithm.
Both our approach and the approach in [5] crucially use the bounded degree assumption. It would be very interesting to know if Theorem 1.1 could be extended to
graphs of average bounded degree such as for example planar graphs.
Question 1. For which class of graphs C does there exist a constant c = c(C) and an
algorithm such that given an n-vertex graph G ∈ C and an m-vertex graph H, the
algorithm computes ind( H, G ) in time O(cm poly(n))?
Organization The remainder of the paper is devoted to proving Theorem 1.1. The main
idea in our proof is to define a multivariate graph polynomial where the coefficients
are certain induced graph counts; in particular ind( H, G ) will be the coefficient of a
monomial. We then want to use machinery from [13] to compute coefficients of univariate evaluations of this polynomial. However, we need to slightly modify the result
from [13]. This will be done in the next section, and in Section 3, we combine certain
univariate evaluations to compute the coefficients of the multivariate polynomial.

2

2

Computing coefficients of graph polynomials

An efficient way to compute the coefficients of a large class of (univariate) graph polynomials for bounded degree graphs was given in [13]. We will need a small modification
of this result, for which we will provide the details here. We start with some definitions
after which we state the main result of this section.
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 (univariate) 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 ). We can now give the key definition and
tool we need from [13].
Definition 2.1. Let p be a multiplicative graph polynomial defined by
d( G)

p( G )(z) :=

∑

ei ( G ) zi

(1)

i =0

for each G ∈ G with e0 ( G ) = 1, where d( G ) is the degree of the polynomial p( G ). We
call p a bounded induced graph counting polynomial (BIGCP) if there exists α ∈ N and a
non-decreasing sequence β ∈ NN such that the following two conditions are satisfied:
(i) for every graph G, the coefficients ei satisfy
ei ( G ) : =

∑

λ H,i ind( H, G )

(2)

H ∈G αi

for certain λ H,i ∈ C;
(ii) for each i and H ∈ Gαi , the coefficient λ H,i can be computed in time β i .
We have the following result for computing coefficients of BIGCPs.
Theorem 2.1. Let n, m, ∆ ∈ N and let p(·) be a bounded induced graph counting polynomial
with parameters α and β. Then there is a deterministic Õ(n(e∆)αm β m 4αm )-time algorithm,
which, given any n-vertex graph G of maximum degree at most ∆, computes the first m coefficients e1 ( G ), . . . , em ( G ) of p( G ). (Here the Õ-notation means that we suppress polynomial
factors in m.)
Remark 2.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 .
Before we prove Theorem 2.1 we will first gather some facts from [13] about induced
subgraph counts and the number of connected induced subgraphs of fixed size that
occur in a graph. Compared to [13] we actually need to slightly sharpen the statements.

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

3

cH
H1 ,H2 ind( H, ·),

(3)

where for a graph H, c H
H1 ,H2 is the number of pairs of subsets of V ( H ), (U, T ), such that
U ∪ T = V ( H ) and H [U ] = H1 and H [ T ] = H2 . In particular, given H1 and H2 , c H
H1 ,H2
is nonzero for only a finite number of graphs H.
In what follows we will often have to maintain a list L of subsets S of [n] with
|S| ≤ k (for some k) as well as some (complex) number cS associated to S. We will use
the standard word-RAM machine model with logarithmic-sized words. This means that
given a set S of size k, we have access to cS in O(k) time. In particular, this also means
we can determine whether S is contained in our list in O(k) time.
The next lemma says that computing ind( H, G ) is fixed parameter tractable (and
moreover gives an essentially optimal running time) when G has bounded degree and
H is connected.
Lemma 2.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(n∆k−1 k)-time algorithm, which, given any n-vertex graph G with maximum
degree at most ∆, computes the number ind( H, G ).
Note that Lemma 2.2 (i) enables us to test for graph isomorphism between bounded
degree graphs when |V ( G )| = |V ( H )|.
Proof. We follow the proof from [13]. We assume that V ( G ) = [n]. 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 vi . 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.
Throughout the procedure above we maintain a list L that contains all sets S such
that G [S] = H found thus far. Each time we find a set S ⊂ [n] such that G [S] = H
we check if it is contained in L. If this is not the case we add S to L and we discard S
otherwise. 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 [3, Lemma 2.1]:
Lemma 2.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
logarithmic size that occur in a bounded degree graph G.
Lemma 2.4. There is a O(nk3 (e∆)k )-time algorithm which, given k ∈ N and an n-vertex
graph G on [n] of maximum degree ∆, outputs Tk , the list of all S ⊆ [n] satisfying |S| ≤ k and
G [S] connected.
Proof. We assume that V ( G ) = [n]. By the previous result, we know that |Tk | ≤
n(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 iteratively compute
Tk by going over all S ∈ Tk−1 going over all v ∈ NG (S) (the collection of vertices that
are connected to an element of S) and checking whether S ∪ {v} is already contained in
Tk or not. We add it to Tk if it is not already contained in Tk .

4

The set NG (S) has size at most |S|∆ ≤ k∆ and takes time O(k∆) to find (assuming
G is given in adjacency list form). Therefore computing Tk takes time bounded by
O(|Tk−1 |k2 ∆) = O(nk2 (e∆)k ).
Starting from T1 , we perform the above iteration k times, requiring a total running
time of O(nk3 (e∆)k ). The proof that Tk contains all the sets we desire is straightforward
and can be found in [13].
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 [4]; it is fundamental to our approach. See [13] for a proof.
Lemma 2.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.
The next proposition is a variant of the Newton identities that relate the inverse
power sums and the coefficients of a polynomial. We refer to [13] for a proof.
Proposition 2.6. Let p(z) = a0 + · · · + ad zd be a polynomial of degree d with complex roots
−j
−j
ζ 1 , . . . , ζ d . Define p j := ζ 1 + · · · + ζ d . Then for each k = 1, 2, . . ., we have
k −1

kak = −

∑ ai pk−i .

i =0

(Here we take ai = 0 if i > d.)

2.2 Proof of Theorem 2.1
We follow the proof as given in [13], which we modify slightly at certain points.
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 coefficients of p. We will use Õ-notation throughout to mean that we suppress
polynomial factors in m. 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 (1)). We also
write pk := ζ 1−k + · · · + ζ d−k , where ζ 1 , . . . , ζ d ∈ C are the roots of the polynomial p( G ).
Noting e0 = 1, Proposition 2.6 gives
k −1

pk = −kek −

∑ ei p k−i ,

(4)

i =1

for each k = 1, . . . , d.
By (2), 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 implies that the same
holds for p1 . By induction, (3), and (4) we have that for each k
pk =

∑

a H,k ind( H, G ),

(5)

H ∈G αk

for certain, yet unknown, coefficients a H,k .
Since p is multiplicative, the inverse power sums are additive. Thus Lemma 2.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. Let us assume that G has
vertex set [n]. Denote by T≤αk ( G ) the list consisting of those sets S ⊆ [n] of size at most
αk that induce a connected graph in G. This way we can rewrite (5) as follows:
pk =

∑

a H,k ind( H, G ) =

H ∈C αk ( G )

∑

a G[S],k .

(6)

S ∈T ≤αk ( G )

The next lemma says that we can compute the coefficients aS,k := a G[S],k efficiently for
k = 1, . . . , m.

5

Lemma 2.7. There is an Õ(n(e∆)αm β m 4αm )-time algorithm, which given a BIGCP p (with
parameters α and β) and an n-vertex graph G of maximum degree ∆, computes and lists the
coefficients aS,k in (6) for all S ∈ T≤αk ( G ) and all k = 1, . . . , m.
Proof. We assume that the vertex set of G is equal to [n]. Using the algorithm of Lemma
2.4, we first compute the list T≤αk consisting of all subsets S of V ( G ) such that |S| ≤ αk
and G [S] is connected. This takes time bounded by
O(n(αm)3 (e∆)αm ) = Õ(n(e∆)αm ).

(7)

(Note that the algorithm in Lemma 2.4 actually computes T≤αk when it computes Tαm .)
To prove the lemma, let us fix k ≤ m and show how to compute the coefficients aS,k ,
assuming that we have already computed and listed the coefficients aS′ ,k′ for all k′ < k
and S′ ∈ T≤αk′ . Let us fix S ∈ T≤αk . Let H = G [S]. By (4), it suffices to compute the
coefficient of ind( H, ·) in pk−i ei for i = 1, . . . , k (where we set p0 = 1). By (2), (3) and (5)
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 =

∑

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

(8)

(U,T ) :U ∪ T =V ( H )

As |V ( H )| ≤ αk, the second sum in (8) is over at most 4αk = O(4αm ) pairs (U, T ). For
each such pair, we need to compute λ H [U ],i and a H [ T ],( k−i) . We can compute λ H [U ],i in
time bounded by O( β i ) = O( β m ) since p is a BIGCP. As H [ T ] = G [ T ], to compute
a H [ T ],( k−i) we just need to look up the coefficient a T,k−i , which takes time O(k − i ).
Together, all this implies that the coefficient of ind( H, ·) in pk−i ei can be computed
in time bounded by
O(4αm ( β m + m)) = Õ( β m · 4αm ).
(9)
So the coefficient a H,k can be computed in the same time (since we suppress polynomial
factors in m). Thus all coefficients aS,k for S ∈ T≤αk can be computed and listed in time
bounded by |T≤αk | multiplied by the expression (9), which is bounded by
Õ(n(e∆)αm β m 4αm )

(10)

by Lemma 2.3.
So the total running time is bounded by the time to compute the list T≤αm (which is
given by (7)) plus the time to compute the aS,k for S ∈ T≤αk (which is given by (10)) for
k = 1, . . . , m. This proves the lemma.
To finish the proof of the theorem, we compute pk for each k = 1, . . . , m by adding
all the numbers aS,k over all S ∈ T≤αk ( G ) using (6) (these numbers were computed in
the previous lemma in time Õ(n(e∆)αm β m 4αm )). Doing this addition takes time
O(m|T≤αm ( G )|) = Õ(n(e∆)αm ).
Finally, knowing the pi , we can inductively compute the ei for i = 1, . . . , m using the
relations (4), in quadratic time in m. So we see that the total running time for computing
e1 , . . . , em is dominated by the computation of the αS,k and is Õ(n(e∆)αm β m 4αm ). This
proves the theorem.

3

Proof of Theorem 1.1

We first set up some notation before we state our key definition. For a graph H we write
H = i1 H1 ∪ · · · ∪ ir Hr to mean that H is the disjoint union of i1 copies of H1 , i2 copies
of H2 all the way to ir copies of Hr for connected and pairwise non-isomorphic graphs

6

H1 , . . . , Hr . For vectors µ, ν ∈ Zr≥0 we write µ ◦ ν for the vector in Zr≥0 that is the pointν
wise or Hadamard product of µ and ν. We write µν for the product µ11 · · · µrνr ∈ Z ≥0 ,
while µ · ν denotes the usual scalar product. For a vector of variables x = ( x1 , . . . , xr )
µ
µ
and µ ∈ Zr≥0 we define x µ := x1 1 · · · xr r .
For pairwise non-isomorphic and connected graphs H1 , . . . , Hr write H = ( H1 , . . . , Hr );
we define the multivariate graph polynomial ZH ( G ) ∈ Z [ x1 , . . . , xr ] as follows. For a
graph G we let
ZH ( G; x ) =

ind(γH, G ) x γ◦h,

∑r

γ ∈ Z ≥0

where x = ( x1 , . . . , xr ), γ = (γ1 , . . . , γr ), h := (|V ( H1 )|, . . . , |V ( Hr )|) and where γH
denotes the graph γ1 H1 ∪ · · · ∪ γr Hr .
Computing ind( H, G ) for any two graphs H = i1 H1 ∪ · · · ∪ ir Hr and G can now be
i h
modelled as computing the coefficient of the monomial x11 1 x2i2 h2 · · · xrir hr in ZH ( G; x ).
Let us start by gathering some facts about the polynomial ZH .
Proposition 3.1. The polynomial ZH is multiplicative, i.e., for any two graphs G1 and G2 ,
ZH ( G1 ∪ G2 ; x ) = ZH ( G1 ; x ) · ZH ( G2 ; x ). In particular, any evaluation of ZH is also multiplicative.
Proof. Note first that every monomial in ZH ( G; x ) is of the form x γ◦h for some unique
choice of γ. For notational convenience we write sγ ( G ) := ind(γH, G ). Consider the
coefficient of x γ◦h in the polynomial ZH ( G1 ; x ) · ZH ( G2 ; x ). The coefficient is given by

∑

sµ ( G1 )sν ( G2 ),

µ+ν=γ

which counts precisely the number of copies of γ1 H1 ∪ · · · ∪ γr Hr in G1 ∪ G2 , that is,
sγ ( G1 ∪ G2 ), which is the coefficient of x γ◦h in the polynomial ZH ( G1 ∪ G2 ; x ).
Suppose µ ∈ Zr≥0 and let z be a variable. Define the graph polynomial Zµ =
Zµ,H ( G ) ∈ Z [z] by
Zµ (z) = ZH ( G; (µ1 z, . . . , µr z)) =:

∑ si ( µ) z i ;
i ≥0

here the second equality defines the numbers si (µ) = si (µ)( G ). In particular, we know
that
(11)
si (µ) = ∑ µγ ind(γH, G ).
γ ∈Z r≥0
γ ·h =i

Proposition 3.2. Fix H = ( H1 , . . . , Hr ) where the Hi are pairwise non-isomorphic connected
graphs each of maximum degree at most ∆ and fix µ ∈ Zr≥0 . Then Zµ,H ( G; z) is a BIGCP with
parameters α = 1 and β i = i2 r∆i−1 .
Proof. Since Zµ,H ( G ) is a particular evaluation of ZH ( G ), we know by Proposition 3.1
that it is multiplicative.
The coefficient of zi in Zµ,H ( G; z) is given by (11). Since γH is a graph with exactly
γ · h = i vertices, we can take α to be 1 in the definition of BIGCP.
For a given graph F, we must determine λ F,i in the definition of BIGCP and the time
β i required to do this. Note that we may assume |V ( F )| = i; otherwise λ F,i = 0. If
|V ( F )| = i, we must test if F is isomorphic to a graph of the form γH with γ · h = i
and if so we must output the value of λ F,i as µγ (this last step taking i arithmetic
operations). To test if F is isomorphic to a graph of the form γH, we test isomorphism
of each component of F against each of the graphs H1 , . . . , Hr , which takes time at most

7

O(ir∆i−1 ) using Lemma 2.2 at most ir times. Thus the total time to compute λ F,i is at
most O(i2 r∆i−1 ).
Now since Zµ,H ( G; z) is a BIGCP, Theorem 2.1 allows us to compute the coefficients
si (µ) in (11) with the desired running time. However the si (µ) are linear combinations
of the numbers ind(γH, G ), while we wish to compute one of these numbers in particular, say ind(ρH, G ). By making careful choices of different µ, we will obtain an
invertible linear system whose solution will include the number ind(ρH, G ). We will
require Alon’s Combinatorial Nullstellensatz [1], which we state here for the reader’s
convenience.
Theorem 3.3 ([1]). Let f ( x1 , . . . , x n ) be a polynomial of degree d over a field F. Suppose the
µ
µ
coefficient of the monomial x1 1 · · · xn n in f is nonzero and µ1 + · · · + µn = d. If S1 , . . . , Sn
are finite subsets of F with |Si | ≥ µi + 1 then there exists a point x ∈ S1 × · · · × Sn for which
f ( x ) 6= 0.
Given a vector h ∈ Nr , let us write Pm,r,h for the set of vectors γ ∈ Zr≥0 such that
γ · h = m. We note that, as the the number of elements in Pm,r,h is at most the number
of monomials in r variables of degree m, we have


m+r−1
|Pm,r,h | ≤
.
(12)
r−1
Lemma 3.4. Fix m, r ∈ N and h ∈ Nr , and let γ1 , . . . , γk be an enumeration of the elements
in Pm,r,h . Given a vector ν ∈ Nr , let us write ν∗ ∈ N k for the vector (νγi ◦h )ni=1 ∈ N k . In
time O(k5 + k2 mem ), we can find vectors ν1 , . . . , νk ∈ Nr such that ν1∗ , . . . , νk∗ are linearly
independent.
Proof. For any vector ν, let us write ν| j to denote the vector consisting of the first j
components. Suppose we have found vectors ν1 , . . . , νℓ−1 ∈ Nr such that the (ℓ − 1) ×
(ℓ − 1) matrix
∗
Mℓ−1 := (ν1∗ |ℓ−1 , . . . , νℓ−
1 | ℓ−1 )
has non-zero determinant. We will show how to find νℓ ∈ Nr such that the corresponding matrix Mℓ has non-zero determinant. First consider the components of νℓ to be
unknown variables x1 , . . . , xr so that det( Mℓ ) becomes a polynomial P = P( x1 , . . . , xr )
in the variables x1 , . . . , xr . In fact it is a homogeneous polynomial of degree m. Writing
x = ( x1 , . . . , xr ), we know that the coefficient of x γℓ ◦h is det( Mℓ−1 ) 6= 0 (consider the
determinant expansion of the matrix Mℓ along the ℓth column). We must now find
νℓ ∈ Nr such that det( Mℓ ) = P(νℓ,1, . . . , νℓ,ℓ ) 6= 0, where v ℓ,i is the ith component of vℓ .
Assume the components of γℓ ∈ Nr are a1 , . . . , ar . Applying Theorem 3.3 to the
monomial x γℓ ◦h and taking the sets Si = {1, . . . , ai hi + 1} for i = 1, . . . , r, we know there
exists a vector νℓ ∈ S := S1 × · · · × Sr such that P(νℓ,1, . . . , νℓ,ℓ ) 6= 0. Computing the
polynomial P requires time at most O(k · k3 ) (using that computing the determinant of
an n × n matrix takes O(n3 ) time) and evaluating it at every point in S requires at most
O(m · k · |S|) operations. We can bound |S| as follows:
!r 

m r
m+r r 
1 r
= 1+
≤ em .
( a i h i + 1) ≤
| S | = ( a1 h 1 + 1 ) · · · ( ar h r + 1 ) ≤
∑
r i =1
r
r
The first inequality follows from the arithmetic-geometric mean inequality. Iterating the
procedure, we can determine ν1 , . . . , νk in time O(k · (k4 + mk|S|)) ≤ O(k5 + k2 mem ).
Remark 3.1. We suspect there should be a simpler argument than the one we have just
given (perhaps one where the vectors ν1 , . . . , νk can be explicitly written down rather
than having an algorithm to determine them). Note that one can also use a faster
randomised algorithm by applying the Schwarz-Zippel Lemma.

8

We can now prove Theorem 1.1.
Proof of Theorem 1.1. We may assume that ∆( H ) ≤ ∆, for otherwise ind( H, G ) = 0. Let
H = ρ1 H1 ∪ ρ2 H2 ∪ . . . ∪ ρr Hr , where the Hj are components of H such that the Hj are
non-isomorphic and occur ρ j ≥ 1 times. We can find the Hj and ρ j in time O(m3 ∆m )
using Lemma 2.2 (i) to test for isomorphism. Write H = ( H1 , . . . , Hr ), h = (h1 , . . . , hr )
with hi = |V ( Hi )|, and ρ = (ρ1 , . . . , ρr ). Note that ρ · h = m. Also recall

Pm,r,h = {γ ∈ Nr : γ · h = m},
and enumerate the elements of Pm,r,h as γ1 , . . . , γk . We may assume that ρ = γ1 . Given
a vector ν ∈ Nr let us write, as before, ν∗ for the vector (νγi ◦h )ki=1. By Lemma 3.4,
we can find vectors ν1 , . . . , νk ∈ Nr such that the vectors ν1∗ , . . . , νk∗ ∈ N k are linearly
independent. We can find these vectors in time O(k5 + k2 mem ) = Õ(210m ), noting that
r −1
m +r ) = O (22m ).
by (12) k is at most (m+
r −1 ) = O ( 2
Now, for i = 1, . . . , k, consider the univariate polynomials Zνi (z) = Zνi ,H,G (z). In
particular, using Proposition 3.2 and Theorem 2.1 we can compute the coefficient sm (νi )
of zm in Zνi (z) in time Õ(n(e∆)αm β m 4αm ) with α = 1 and β i = i2 r∆i−1 . So computing al
these coefficients can be done in time
Õ(k · (n(4∆)m )(e∆)m ) = Õ(n(7∆)2m ).
Recall that this coefficient is
k

sm (νi )( G ) =

γ j ◦h

∑ νi

k

sγ j =

γ j ◦h

∑ νi

ind(γ j H, G ).

j =1

j =1

More conveniently, writing s ∈ Z k≥0 for the vector given by s j := sγ j = (ind(γ j H, G ))kj=1,
we have the invertible system of linear equations given by
νi∗ · s = sm (νi ) for i = 1, . . . , k,
where we have computed the values of sm (νi ) and νi∗ , while the vector s is unknown
(the system is invertible because we chose the νi∗ to be linearly independent). We can
then invert the system in time O(k3 ) = Õ(26m ). In particular finding the value of s1 =
ind(ρH, G ) can be done in Õ(26m ). The total running time is bounded by Õ(n(7∆)2m +
210m )).

4

Concluding remarks

As we remarked in the introduction our approach also works in the setting of vertexand edge-coloured graphs. We will not elaborate on the details here, but just refer the
interested reader to Section 3.3 of [13] where we have briefly explained how to extend
the results for computing coefficients of BIGCPs to the setting of coloured graphs. In
addition we note that the part of the proof given in Section 3 also carries over to the
coloured graphs setting replacing graph by coloured graph everywhere.
We moreover remark that the approach used to prove Theorem 1.1 is very robust.
Besides extending to the coloured setting, it also easily extends to other graph like
structures. For example, in [13] it has been extended to fragments, i.e., vertex-coloured
graphs in which some edges may be unfinished and more recently, Liu, Sinclair, and
Srivastava [10] extended it to insects, i.e., vertex-coloured hypergraphs in which some
edges may be unfinished. We expect our approach to be applicable to the problem of
counting (induced) substructures in other structures as well, as long as there is a notion
of connectedness and maximum degree.

9

Acknowledgements
We thank John Lapinskas for raising a question about the complexity of our main algorithm in a previous version of this paper, which led to an improved running time. We
also thank Radu Curticapean for informing us of some historical context to our result.

References
[1] N. Alon and M. Tarsi. Combinatorial nullstellensatz. Combinatorics Probability and
Computing, 8(1):7–30, 1999.
[2] A. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer, 2017.
[3] C. Borgs, J. Chayes, J. Kahn, and L. Lovász. Left and right convergence of graphs
with bounded degree. Random Structures & Algorithms, 42(1):1–28, 2013.
[4] P. Csikvári and P. E. Frenkel. Benjamini–schramm continuity of root moments of
graph polynomials. European Journal of Combinatorics, 52:302–320, 2016.
[5] R. Curticapean, H. Dell, F. V. Fomin, L. A. Goldberg, and J. Lapinskas. A fixedparameter perspective on #Bis. CoRR, abs/1702.05543, 2017.
[6] R. Curticapean, H. Dell, and D. Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–
223, 2017.
[7] R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness
II: on completeness for W[1]. Theor. Comput. Sci., 141(1&2):109–131, 1995.
[8] D. S. Johnson and M. Szegedy. What are the least tractable instances of max independent set? In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete
Algorithms, 17-19 January 1999, Baltimore, Maryland., pages 927–928, 1999.
[9] T. Kloks, D. Kratsch, and H. Müller. Finding and counting small induced subgraphs efficiently. Inf. Process. Lett., 74:115–121, 1995.
[10] J. Liu, A. Sinclair, and P. Srivastava. The Ising partition function: Zeros and deterministic approximation. arXiv preprint arXiv:1704.06493, 2017.
[11] L. Lovász. Large networks and graph limits, volume 60 of American Mathematical
Society Colloquium Publications. American Mathematical Society, Providence, RI,
2012.
[12] J. Nešetřil and S. Poljak. On the complexity of the subgraph problem. Comment.
Math. Univ. Carolin., 26(2):415–419, 1985.
[13] V. Patel and G. Regts. Deterministic polynomial-time approximation algorithms for
partition functions and graph polynomials. Siam Journal on Computing, to appear.
[14] 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(5):1151–1261,
2005.

10

