Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus
(SIC<EMAIL_ADDRESS>saarland.dehttps://orcid.org/0000-0002-0943-8282 Cluster of Excellence (MMCI),
Saarland Informatics Campus (SIC), Saarbrücken<EMAIL_ADDRESS>saarland.dehttps://orcid.org/0000-0003-3159-9418 ETH Zürich, Switzerland and
https://people.math.ethz.ch/~schmittj/
johannes.schmitt@math.ethz.chhttps://orcid.org/0000-0001-5774-3508The third
author has received funding from the European Research Council (ERC) under the
EU’s Horizon 2020 research and innovation programme (No 786580). Max Planck
Institute for Informatics, Saarland Informatics Campus (SIC), Saarbrücken,
Germany and https://people.mpi-inf.mpg.de/~wellnitz/wellnitz@mpi-
inf.mpg.dehttps://orcid.org/0000-0002-6482-8478 Julian Dörfler and Marc Roth
and Johannes Schmitt and Philip Wellnitz[500]Theory of computation
Parameterized complexity and exact algorithms [300]Theory of computation
Problems, reductions and completeness [300]Mathematics of computing
Combinatorics [300]Mathematics of computing Graph theory

###### Acknowledgements.

We are very grateful to Radu Curticapean and Holger Dell for fruitful
discussions and valuable feedback on early drafts of this work.John Q. Open
and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT
2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Counting Induced Subgraphs:
An Algebraic Approach to #W[1]-hardness

Julian Dörfler  Marc Roth  Johannes Schmitt  Philip Wellnitz

###### Abstract

We study the problem $\\#\textsc{IndSub}(\Phi)$ of counting all induced
subgraphs of size $k$ in a graph $G$ that satisfy the property $\Phi$. This
problem was introduced by Jerrum and Meeks and shown to be
$\\#\mathsf{W[1]}$-hard when parameterized by $k$ for some families of
properties $\Phi$ including, among others, connectivity [JCSS 15] and even- or
oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18],
two of the authors introduced a novel technique for the complexity analysis of
$\\#\textsc{IndSub}(\Phi)$, inspired by the “topological approach to
evasiveness” of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph
motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to
prove hardness of a wide range of properties $\Phi$. In this work, we refine
this technique for graph properties that are non-trivial on edge-transitive
graphs with a prime power number of edges. In particular, we fully classify
the case of monotone bipartite graph properties: It is shown that, given _any_
graph property $\Phi$ that is closed under the removal of vertices and edges,
and that is non-trivial for bipartite graphs, the problem
$\\#\textsc{IndSub}(\Phi)$ is $\\#\mathsf{W[1]}$-hard and cannot be solved in
time $f(k)\cdot n^{o(k)}$ for any computable function $f$, unless the
Exponential Time Hypothesis fails. This holds true even if the input graph is
restricted to be bipartite and counting is done modulo a fixed prime. A
similar result is shown for properties that are closed under the removal of
edges only.

###### keywords:

counting complexity, edge-transitive graphs, graph homomorphisms, induced
subgraphs, parameterized complexity

##  1 Introduction

The study of the computational complexity of counting problems was initiated
by Valiant’s seminal work about the complexity of computing the permanent
[24]. In contrast to a decision problem which requires to _verify_ the
existence of a solution, a counting problem asks to compute the _number_ of
solutions. Counting complexity theory is particularly interesting for problems
whose decision versions are solvable efficiently but whose counting versions
are intractable. One such example is the problem of finding/counting perfect
matchings, whose decision version is solvable in polynomial time [10] and
whose counting version is as least as hard as every problem in the Polynomial
Hierarchy $\mathsf{PH}$ with respect to polynomial-time Turing reductions [24,
23]. In this work, we consider the following problem which was first
introduced by Jerrum and Meeks [13]: Fix a graph property $\Phi$, given a
graph $G$ and a positive integer $k$, compute the number of all induced
subgraphs of $G$ with $k$ vertices that satisfy $\Phi$. We denote this problem
by $\\#\textsc{IndSub}(\Phi)$ and remark that, strictly speaking,
$\\#\textsc{IndSub}(\Phi)$ is the _unlabeled_ version of
$p\text{-}\\#\textsc{InducedSubgraphWithProperty}(\Phi)$ as defined in [15,
Section 1.3.1]. In particular, our properties only depend on the isomorphism
type of a graph and not on any labeling of the vertices.

We study the _parameterized complexity_ of $\\#\textsc{IndSub}(\Phi)$
depending on the property $\Phi$. The underlying framework, known as
_parameterized counting complexity theory_ , was introduced independently by
Flum and Grohe [11] and McCartin [18], and constitutes a hybrid of (classical)
computational counting and parameterized complexity theory. Here, the method
of parameterization allows us to perform a multivariate analysis of the
complexity of $\\#\textsc{IndSub}(\Phi)$: Instead of the distinction between
polynomial-time solvable and $\mathsf{NP}$-hard cases, we search for
properties $\Phi$ for which the problem is solvable in time $f(k)\cdot
n^{O(1)}$, where $n$ is the number of vertices of the graph and $f$ can be any
computable function. If this is the case, the problem is called _fixed-
parameter tractable_. Unfortunately, the only known cases of $\Phi$ for which
$\\#\textsc{IndSub}(\Phi)$ is fixed-parameter tractable are trivial in the
sense that there are only finitely many $k$ such that $\Phi$ is neither true
nor false on the set of all graphs with $k$ vertices. On the contrary, it is
easy to see that $\\#\textsc{IndSub}(\Phi)$ is most likely not fixed-parameter
tractable if $\Phi$ encodes a problem whose decision version is already known
to be hard. An example of the latter is the property of being a complete
graph. In this case, the problem $\\#\textsc{IndSub}(\Phi)$ is identical to
the problem of counting cliques of size $k$, for which even the decision
version, that is, _finding_ a clique of size $k$ in a graph with $n$ vertices,
cannot be done in time $f(k)\cdot n^{o(k)}$, unless the Exponential Time
Hypothesis fails [5, 6].

The first non-trivial hardness result of $\\#\textsc{IndSub}(\Phi)$ was given
by Jerrum and Meeks for $\Phi$ the property of being connected [13]. Note
that, in this case, the decision version of the problem can be solved
efficiently as, on input $G$ and $k$, one only has to decide whether there
exists a connected component of $G$ of size at least $k$. This result
initiated a line of research in which Jerrum and Meeks proved fixed-parameter
tractability of $\\#\textsc{IndSub}(\Phi)$ to be unlikely for the property of
having an even (or odd) number of edges [15], for properties that induce low
edge densities [14] and for properties that are closed under the addition of
edges and whose (edge-)minimal elements have large treewidth [19]. More
precisely, all of those results established hardness for the parameterized
complexity class $\\#\mathsf{W[1]}$, which can be seen as the parameterized
counting equivalent of $\mathsf{NP}$. In a recent breakthrough result [8],
Curticapean, Dell and Marx have shown, that for every graph property $\Phi$,
the problem $\\#\textsc{IndSub}(\Phi)$ is either fixed-parameter tractable or
hard for $\\#\mathsf{W[1]}$, that is, there are no cases of intermediate
difficulty. On the downside, they did not provide an explicit criterion for
$\\#\mathsf{W[1]}$-hardness that allows to pin down the complexity of
$\\#\textsc{IndSub}(\Phi)$, given a concrete property $\Phi$. However,
combining the framework of [8] with tools from the “topological approach to
evasiveness” by Kahn, Saks and Sturtevant [16], two of the authors of the
current paper established $\\#\mathsf{W[1]}$-hardness for a wide range of
properties, including, for example, all non-trivial properties that are closed
under the removal of edges and false on odd cycles [22]. Taken together, the
above results suggest the following conjecture.

######  Conjecture .

Let $\Phi$ be a computable graph property satisfying that there are infinitely
many positive integers $k$ such that $\Phi$ is neither true nor false on all
graphs with $k$ vertices. Then $\\#\textsc{IndSub}(\Phi)$ is
$\\#\mathsf{W[1]}$-hard.

Unfortunately, a proof of this conjecture seems to be a long way off. In this
work however, building up on [8, 22], we introduce an algebraic approach that
allows us to resolve the above conjecture in case of _all_ non-trivial
monotone properties on bipartite graphs. In particular, we obtain a matching
lower bound under the Exponential Time Hypothesis.

#### Results and techniques

We call a graph property _monotone_ if it closed under the removal of vertices
and edges and _edge-monotone_ if it is closed under the removal of edges only.
Furthermore, we write $\mathsf{IS}_{k}$ for the graph consisting of $k$
isolated vertices and $K_{t,t}$ for the complete bipartite graph with $t$
vertices on each side. Our main theorems read as follows.

######  Theorem 1.1.

Let $\Phi$ be a computable graph property and let $\mathcal{K}$ be the set of
all prime powers $t$ such that $\Phi(\mathsf{IS}_{2t})\neq\Phi(K_{t,t})$. If
$\mathcal{K}$ is infinite then $\\#\textsc{IndSub}(\Phi)$ is
$\\#\mathsf{W[1]}$ hard. If additionally $\mathcal{K}$ is dense then it cannot
be solved in time $f(k)\cdot n^{o(k)}$ for any computable function $f$ unless
ETH fails. This holds true even if the input graphs to
$\\#\textsc{IndSub}(\Phi)$ are restricted to be bipartite.

In the previous theorem, a set $\mathcal{K}$ is _dense_ if there exists a
constant $c$ such that for every $m\in\mathbb{N}$, there exists a
$k\in\mathcal{K}$ such that $m\leq k\leq cm$. While the hypotheses of Theorem
1.1 sound technical, the theorem applies in many situations. In particular, it
is applicable to properties that are neither (edge-) monotone nor the
complement thereof: Let $\Phi$ be the property of being Eulerian. The graph
$K_{t,t}$ contains an Eulerian cycle if $t=2^{s}$ for $s\geq 1$. Hence we can
apply Theorem 1.1 with $\mathcal{K}=\\{2^{s}\leavevmode\nobreak\
|\leavevmode\nobreak\ s\geq 1\\}$, which is infinite and dense.

######  Corollary 1.2.

Let $\Phi$ be the property of being Eulerian. Then $\\#\textsc{IndSub}(\Phi)$
is $\\#\mathsf{W[1]}$-hard and cannot be solved in time $f(k)\cdot n^{o(k)}$
for any computable function $f$ unless the ETH fails. This holds true even if
the input graphs to $\\#\textsc{IndSub}(\Phi)$ are restricted to be bipartite.

In case $\Phi$ is edge-monotone, the condition
$\Phi(\mathsf{IS}_{2t})\neq\Phi(K_{t,t})$ is equivalent to non-triviality and
if $\Phi$ is monotone, we obtain the following, more concise statement of the
hardness result.

######  Theorem 1.3.

Let $\Phi$ be a computable monotone graph property such that $\Phi$ and
$\neg\Phi$ hold on infinitely many bipartite graphs. Then
$\\#\textsc{IndSub}(\Phi)$ is $\\#\mathsf{W[1]}$-hard and cannot be solved in
time $f(k)\cdot n^{o(k)}$ for any computable function $f$ unless the
Exponential Time Hypothesis fails. This holds true even if the input graphs to
$\\#\textsc{IndSub}(\Phi)$ are restricted to be bipartite.

Let us illustrate further consequences of the previous theorems with respect
to (edge-) monotone properties. First of all, most of the prior hardness
results ([13, 14, 19, 15, 22]) are shown to hold in the restricted case of
bipartite graphs. We provide three examples:

######  Corollary 1.4.

The problem $\\#\textsc{IndSub}(\Phi)$, restricted to _bipartite input graphs_
, is $\\#\mathsf{W[1]}$-hard and cannot be solved in time
$f(k)\cdot|V(G)|^{o(k)}$ for any computable function $f$ unless ETH fails, if
$\Phi$ is one of the properties of being disconnected, planar or non-
hamiltonian.

One example of a monotone property $\Phi$ for which the complexity of
$\\#\textsc{IndSub}(\Phi)$ was unknown, even for general graphs, is given by
the following corollary of Theorem 1.3.

######  Corollary 1.5.

Let $F$ be a fixed bipartite graph with at least one edge and define
$\Phi(G)=1$ if $G$ does not contain a subgraph isomorphic to $F$. Then
$\\#\textsc{IndSub}(\Phi)$ is $\\#\mathsf{W[1]}$-hard and cannot be solved in
time $f(k)\cdot|V(G)|^{o(k)}$ for any computable function $f$ unless ETH
fails. This holds true even if the input graphs of $\\#\textsc{IndSub}(\Phi)$
are restricted to be bipartite.

As the number of induced subgraphs of size $k$ that satisfy $\Phi$ equals
$\binom{|V(G)|}{k}$ minus the number of induced subgraphs of size $k$ that
satisfy $\neg\Phi$, _all of the previous result remain true for the
complementary properties_ $\neg\Phi$.

In proving the previous theorems we build up on the approach in [8, 22], where
it was shown that, given a graph property $\Phi$ and a positive integer $k$,
the number of induced subgraphs of size $k$ in a graph $G$ that satisfy $\Phi$
can equivalently be expressed as the following sum over all (isomorphism types
of) graphs $H$:

$\sum_{H}a_{\Phi}(H)\cdot\\#\mbox{$\mathsf{Hom}(H\to G)$}\,,$ (1)

where $a_{\Phi}$ is a function from graphs to integers with finite support and
$\\#\mbox{$\mathsf{Hom}(H\to G)$}$ is the number of graph homomorphisms from
$H$ to $G$. It is known that computing a linear combination of homomorphism
numbers, as in the above expression, is _precisely as hard as_ computing its
hardest term with a non-zero coefficient ([8], also implicitly proved in [4]).
We refer to this property as _complexity monotonicity_. In [22] two of the
authors of the current paper used a topological approach to analyze the
coefficient $a_{\Phi}(K_{k})$ of the complete graph on $k$ vertices. If this
coefficient is non-zero then complexity monotonicity implies that computing
the number of induced subgraphs of size $k$ in a graph $G$ that satisfy $\Phi$
is at least as hard as computing the number $\\#\mbox{$\mathsf{Hom}(K_{k}\to
G)$}$. This, in turn, is equivalent to computing the number of cliques of size
$k$ in $G$, the canonical $\\#\mathsf{W[1]}$-complete problem [11]. While this
approach led to hardness proofs for a wide range of properties $\Phi$, it
seems that resolving Conjecture 1, even restricted to monotone properties,
requires a significant amount of new ideas. Without going too much into the
details111Readers familiar with [22] might recall that fixed points of group
actions have been used to derive a simpler formula to compute the number
$a_{\Phi}(K_{t})$ modulo a prime $p$ for positive powers $t$ of $p$. This
formula would simplify greatly if the group had a $p$-power number of elements
_and_ acted transitively on the edges of $K_{t}$. Unfortunately, this can
never happen for $t\geq 4$, since the number of edges of $K_{t}$ is not itself
a $p$-power. of [22], our analysis of $a_{\Phi}(K_{k})$ is complicated by the
fact that the number of edges of the complete graph on $k\geq 4$ vertices is
not a prime power. In this work, we hence focus on the coefficient of
$a_{\Phi}(H)$ for graphs $H$ that have a prime power number of edges and for
which computing $\\#\mbox{$\mathsf{Hom}(H\to G)$}$ is hard. One example of
such graphs is the biclique $K_{t,t}$ for some prime power $t$. Here a
biclique $K_{t,t}$, also called a complete bipartite graph, has $t$ vertices
on each side and contains every edge from a vertex on the left side to a
vertex to the right side. Hence the number of edges is $t^{2}$ which is a
prime power if $t$ is.

In analyzing the coefficient $a_{\Phi}(K_{t,t})$ of the complete bipartite
graph, we invoke the results of Rivest and Vuillemin [21] who considered
transitive boolean functions over a domain of prime power cardinality to
resolve the asymptotic version of what is known as _Karp’s evasiveness
conjecture_ (we recommend Miller’s survey [20] for an excellent overview).

Given a property $\Phi$ and a graph $H$, the _alternating enumerator_ of
$\Phi$ and $H$ is defined to be

$\hat{\chi}(\Phi,H):=\sum_{S\subseteq E(H)}\Phi(H[S])\cdot(-1)^{\\#S}\,,$

where $H[S]$ is the graph with vertices $V(H)$ and edges $S$. Roughly
speaking, it will turn out that the value of $a_{\Phi}(H)$ is closely related
to $\hat{\chi}(\Phi,H)$. We furthermore point out that, in case $\Phi$ is
closed under the removal of edges, the alternating enumerator
$\hat{\chi}(\Phi,H)$ equals what is called the reduced Euler characteristic of
the simplicial complex on $E(H)$ associated to $\Phi$ [20, 22]. In Section 3
we study the alternating enumerator in case of edge-transitive graphs, that
is, graphs whose automorphism groups act transitively on the set of edges. We
give a self-contained proof of the following fact, which implicitly follows
from [21].

######  Lemma 1.6.

Let $\Phi$ be a graph property and let $H$ be an edge-transitive graph with
$p^{k}$ edges such that $p$ is a prime and $\Phi(H[\emptyset])\neq\Phi(H)$.
Then it holds that $\hat{\chi}(\Phi,H)=(\pm 1)\mod p\,.$

Now, intuitively, Lemma 1.6 induces a strategy towards proving hardness of
$\\#\textsc{IndSub}(\Phi)$: Assume a family of edge-transitive graphs
$\mathcal{H}$ can be found such that $\\#E(H)$ is a prime power and
$\Phi(H[\emptyset])\neq\Phi(H)$ for every $H\in\mathcal{H}$. Then
$\\#\textsc{IndSub}(\Phi)$ is at least as hard as counting homomorphisms from
graphs in $\mathcal{H}$, the latter of which is fully understood [9]. This
observation gives a strong motivation for the study of edge-transitive graphs
with a prime power number of edges. In the second part of Section 3, we fully
classify those graphs as subgraphs of bipartite graphs or vertex-transitive
subgraphs of wreath graphs; consult Section 3 for the formal definitions. The
proof of the following theorem, which might be of independent interest, relies
on a non-trivial application of Sylow’s theorems.

######  Theorem 1.7.

Let $G$ be a connected edge-transitive graph with $p^{t}$ edges for some prime
$p$ and positive integer $t$. Then either $G$ is bipartite or $G$ is vertex-
transitive and can be obtained from the wreath graph $W_{p^{k}}$ for $k\geq 1$
by removing edges (or both).

With the analysis of $\hat{\chi}$ and edge-transitive graphs completed, we
turn to the reduction from counting homomorphisms in Section 4. More
precisely, given a class $\mathcal{H}$ of edge-transitive graphs with a prime
power number of edges and a graph property $\Phi$ such that for every
$H\in\mathcal{H}$ we have that $\Phi(H[\emptyset])\neq\Phi(H)$, we construct a
parameterized Turing reduction from $\\#\textsc{Hom}(\mathcal{H})$ to
$\\#\textsc{IndSub}(\Phi)$. Here, the problem $\\#\textsc{Hom}(\mathcal{H})$
is defined as follows: Given as input a graph $H\in\mathcal{H}$ and a graph
$G$, compute the number of homomorphisms from $H$ to $G$. For technical
reasons, we cannot immediately transform the number of induced subgraphs that
satisfy $\Phi$ to a linear combination of homomorphism numbers as in Equation
(1). We solve this technical issue by introducing color-prescribed variants of
those problems in an intermediate step. In this context we consider
$H$-colored graphs. Recall that a graph $G$ is $H$-colored if it comes with a
homomorphism $c$ from $G$ to $H$. A homomorphism from $H$ to $G$ is then
called color-prescribed if it maps every vertex $v$ of $H$ to a vertex $u$ of
$G$ satisfying that $c(u)=v$. We demonstrate that, given an $H$-colored graph
$G$ and oracle access to $\\#\textsc{IndSub}(\Phi)$, the following linear
combination can be computed in time $f(|V(H)|)\cdot|V(G)|^{O(1)}$.

$\sum_{S\subseteq
E(H)}\hat{a}_{\Phi}(S)\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to G).$ (2)

Here $\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to G)$ denotes the set of color-
prescribed homomorphisms from $H[S]$ to $G$ and $\hat{a}_{\Phi}$ is a function
of finite support only depending in $\Phi$. In particular,
$\hat{a}_{\Phi}(E(H))$ and $\hat{\chi}(\Phi,H)$ are proved to agree up to a
factor of $-1$. Finally, we establish complexity monotonicity for linear
combinations of color-prescribed homomorphisms as in Equation (2), which in
combination with Lemma 1.6 yields the desired reduction.

Combining the previous results, we invoke the reduction on graph properties
that are non-trivial on bipartite graphs and prove Theorem 1.1 and Theorem
1.3, in Section 5. Furthermore, we illustrate in the appendix that our
algebraic approach readily extends to modular counting by proving that both,
Theorem 1.1 and Theorem 1.3 remain true in case counting is done modulo a
fixed prime.

##  2 Preliminaries

Given a positive integer $k$, we write $[k]$ for the set $\\{1,\dots,k\\}$ and
given a set $A$ we write $\binom{A}{k}$ for the set of all subsets of size $k$
of $A$. Furthermore, assuming that $A$ is finite, we write $\\#A$ or $|A|$ for
its cardinality. Given a function $g:A\times B\rightarrow C$ and an element
$a\in A$, we write $g(a,\star)$ for the function which maps $b\in B$ to
$g(a,b)$.

###  2.1 Graph theory

Graphs in this work are considered simple, undirected and without self-loops.
More precisely, a graph $G$ is a pair of a finite set $V(G)$ of vertices and a
symmetric and irreflexive relation $E(G)\subseteq V(G)^{2}$. If a graph $H$ is
obtained from $G$ by deleting a set of edges and a set of vertices of $G$,
including incident edges, then $H$ is called a _subgraph_ of $G$. Given a
subset $\hat{V}$ of $V(G)$ we write $G[\hat{V}]$ for the graph with vertices
$\hat{V}$ and edges $E\cap\hat{V}^{2}$. The resulting graph is called an
_induced subgraph_ of $G$. An _edge-subgraph_ of a graph $H$ is a graph
obtained from $H$ by deleting edges. Given a set $S\subseteq E(H)$ we write
$H[S]$ for the edge-subgraph $(V(H),S)$ of $H$.

#### Homomorphisms and embeddings

A _homomorphism_ from a graph $H$ to a graph $G$ is a mapping
$h:V(H)\rightarrow V(G)$ that preserves adjacencies. In other words, for every
edge $\\{u,v\\}\in E(H)$ it holds that $\\{h(u),h(v)\\}\in E(G)$. We write
$\mathsf{Hom}(H\to G)$ for the set of all homomorphisms from $H$ to $G$. A
homomorphism inducing a bijection of vertices and satisfying $\\{u,v\\}\in
E(H)$ if and only if $\\{f(u),f(v)\\}\in E(G)$ is called an _isomorphism_ and
we say that two graphs $H$ and $\hat{H}$ are _isomorphic_ if there exists an
isomorphism from $H$ to $\hat{H}$. We write $\mathsf{Sub}(H\to G)$ and
$\mathsf{IndSub}(H\to G)$ for the sets of all subgraphs and induced subgraphs
of $G$, respectively, that are isomorphic to $H$.

An isomorphism from a graph to itself is called an _automorphism_. The set of
automorphisms of a graph, together with the operation of functional
composition constitutes a group, called the _automorphism group_ of a graph.
Slightly abusing notation, we will write $\mathsf{Aut}(H)$ for both the set of
automorphisms of a graph $H$ as well as for the automorphism group of $H$.

An _embedding_ is an injective homomorphism and we write $\mathsf{Emb}(H\to
G)$ for the set of embeddings from $H$ to $G$. If an embedding $h$ from $H$ to
$G$ additionally satisfies that $\\{h(u),h(v)\\}\in E(G)$ implies
$\\{u,v\\}\in E(H)$, we call it a _strong embedding_. We write
$\mathsf{StrEmb}(H\to G)$ for the set of strong embeddings from $H$ to $G$.
Observe that the images of embeddings and strong embeddings from $H$ to $G$
are precisely the subgraphs and induced subgraphs of $G$ that are isomorphic
to $H$.

#### Colored variants

Given graphs $G$ and $H$, we say that $G$ is $H$_-colored_ if $G$ comes with a
homomorphism $c$ from $G$ to $H$, called an $H$-_coloring_. Note that, in
particular, every edge-subgraph of $H$ can be $H$-colored by the identity
function on $V(H)$, which is assumed to be the given coloring whenever we
consider $H$-colored edge-subgraphs of $H$ in this paper. Given an edge-
subgraph $F$ of $H$ and a homomorphism $h$ from $F$ to a $H$-colored graph
$G$, we say that $h$ is _color-prescribed_ if for all $v\in V(F)=V(H)$ it
holds that $c(h(v))=v$. We write $\mathsf{cp}\text{-}\mathsf{Hom}(F\to G)$ for
the set of all color-prescribed homomorphisms from $F$ to $G$.
$\mathsf{cp}\text{-}\mathsf{StrEmb}(F\to G)$ is defined similarly for color-
prescribed strong embeddings. We point out that a definition of
$\mathsf{cp}\text{-}\mathsf{Emb}$ is obsolete as every color-prescribed
homomorphism is injective by definition and hence an embedding. Furthermore,
we write $\mathsf{cp}\text{-}\mathsf{Sub}(F\to G)$ and
$\mathsf{cp}\text{-}\mathsf{IndSub}(F\to G)$ for the sets of images of color-
prescribed embeddings and strong embeddings from $F$ to $G$, respectively.
Elements of $\mathsf{cp}\text{-}\mathsf{Sub}(F\to G)$ and
$\mathsf{cp}\text{-}\mathsf{IndSub}(F\to G)$ are referred to as color-
prescribed subgraphs and induced subgraphs.222The observant reader might have
noticed that the sets $\mathsf{cp}\text{-}\mathsf{Sub}(F\to G)$ and
$\mathsf{cp}\text{-}\mathsf{Hom}(F\to G)$ as well as
$\mathsf{cp}\text{-}\mathsf{IndSub}(F\to G)$ and
$\mathsf{cp}\text{-}\mathsf{StrEmb}(F\to G)$ are essentially the same as a
color-prescribed homomorphism is uniquely identified by its image. However, we
decided to distinguish those notions in order to make the combinatorial
arguments in Section 4 more accessible.

#### Graph properties and the alternating enumerator

A _graph property_ is a function $\Phi$ from graphs to $\\{0,1\\}$ such that
for any pair of isomorphic graphs $H$ and $\hat{H}$ we have that
$\Phi(H)=\Phi(\hat{H})$. Adapting the notation of Rivest and Vuillemin [21],
we define the _alternating enumerator_ of a property $\Phi$ and a graph $H$ to
be the function

$\hat{\chi}(\Phi,H):=\sum_{S\subseteq E(H)}\Phi(H[S])\cdot(-1)^{\\#S}\,.$

A graph property $\Phi$ is called _edge-monotone_ if it is closed under the
removal of edges. It is called _monotone_ if it is closed under the removal of
edges _and_ vertices.333To avoid confusion, we remark that in some literature,
e.g. in [19] a property is called monotone if it is closed under _addition_ of
vertices and edges. Given a graph property $\Phi$, a positive integer $k$ and
a graph $G$, we write $\mathsf{IndSub}(\Phi,k\to G)$ for the set of all
induced subgraphs of size $k$ of $G$ that satisfy $\Phi$. Furthermore, given a
graph property $\Phi$ and an $H$-colored graph $G$, we write
$\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$ for the set of all color-
prescribed induced subgraphs of size $|V(H)|$ in $G$ that satisfy $\Phi$.

###  2.2 Parameterized counting complexity

The field of parameterized counting was introduced independently by McCartin
[18] and Flum and Grohe [11] and constitutes a hybrid of classical
computational counting and parameterized complexity theory. A _parameterized
counting problem_ is a pair of a function
$P:\Sigma^{\ast}\rightarrow\mathbb{N}$ and a computable parameterization
$\kappa:\Sigma^{\ast}\rightarrow\mathbb{N}$. It is called _fixed-parameter
tractable_ (FPT) if there exists a computable function $f$ and a deterministic
algorithm that computes $P(x)$ in time $f(\kappa(x))\cdot|x|^{O(1)}$ for every
$x\in\Sigma^{\ast}$. A _parameterized Turing reduction_ from $(P,\kappa)$ to
$(\hat{P},\hat{\kappa})$ is a deterministic FPT algorithm with respect to
$\kappa$ that is given oracle access to $\hat{P}$ and that on input $x$
computes $P(x)$ with the additional restriction that there exists a computable
function $g$ such that for any oracle query $y$ it holds that
$\hat{\kappa}(y)\leq g(\kappa(x))$. We write
$(P,\kappa)\leq^{\mathrm{fpt}}_{\mathrm{T}}(\hat{P},\hat{\kappa})$ if a
parameterized Turing reduction exists.

Given a graph $G$ and a positive integer $k$, the parameterized counting
problem $\\#\textsc{Clique}$ asks to compute the number of complete subgraphs
of size $k$ in $G$ and is parameterized by $k$, that is $\kappa(G,k):=k$. It
is complete for the class $\\#\mathsf{W[1]}$, which can be seen as a
parameterized counting equivalent of $\mathsf{NP}$ [11]. Evidence for the
fixed-parameter intractability of $\\#\mathsf{W[1]}$-hard problems is given by
the _Exponential Time Hypothesis_ (ETH), which asserts that $3$-SAT cannot be
solved444We point out that this includes deterministic and randomized
algorithms. in time $\mathsf{exp}(o(m))$ where $m$ is the number of clauses of
the input formula. Assuming ETH, $\\#\textsc{Clique}$ cannot be solved in time
$f(k)\cdot n^{o(k)}$ for any function $f$ [5, 6] and hence
$\\#\mathsf{W[1]}$-hard problems are not fixed-parameter tractable.

Given a recursively enumerable class of graphs $\mathcal{H}$, the problem
$\\#\textsc{Hom}(\mathcal{H})$ asks, given a graph $H\in\mathcal{H}$ and an
arbitrary graph $G$, to compute $\\#\mbox{$\mathsf{Hom}(H\to G)$}$. Its
parameterization is given by $\kappa(H,G):=|V(H)|$. The problems
$\\#\textsc{cp-Hom}(\mathcal{H})$ and $\\#\textsc{cp-IndSub}(\mathcal{H})$ are
defined similarly. Furthermore, we define $\\#\textsc{cp-IndSub}(\Phi)$ to be
the problem of, given a graph $G$ that is $H$-colored for some graph $H$,
computing $\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$ and parameterize
it by $\kappa(G):=|V(H)|$ — note that the $H$-coloring of $G$ is part of the
input and hence $\kappa$ is well-defined. Finally, the problem
$\\#\textsc{IndSub}(\Phi)$ asks, given a graph $G$ and a positive integer $k$,
to compute $\\#\mbox{$\mathsf{IndSub}(\Phi,k\to G)$}$ and the parameterization
is given by $\kappa(G,k):=k$.

##  3 Alternating enumerators and p-edge-transitive graphs

In this part of the paper we will provide a rough exposition of the work of
Rivest and Vuillemin [21] who studied transitive boolean functions to resolve
the asymptotic version of Karp’s evasiveness conjecture. We will then apply
their result to graphs $H$ that are both edge-transitive and have $p^{\ell}$
many edges for some prime $p$. This will enable us to conclude that the
alternating enumerator of $\Phi$ and $H$ is $(\pm 1)$ modulo $p$ whenever
$\Phi(H[\emptyset])\neq\Phi(H)$. We start by introducing some required notions
from algebraic graph theory.

The automorphism group of a graph $H$ induces a group action on the edges of
$H$, given by $h\\{u,v\\}:=\\{h(u),h(v)\\}$. A group action is _transitive_ if
there exists only one orbit and a graph $H$ is called _edge-transitive_ if the
group action on the edges is transitive, that is, if for every pair of edges
$\\{u,v\\}$ and $\\{\hat{u},\hat{v}\\}$ there exists an automorphism
$h\in\mathsf{Aut}(H)$ such that $h\\{u,v\\}=\\{\hat{u},\hat{v}\\}$. If
additionally the number of edges of an edge-transitive graph is a prime power
$p^{\ell}$ we call the graph $p$_-edge-transitive_.

######  Lemma 3.1 (Lemma 1.6 restated).

Let $\Phi$ be a graph property and let $H$ be a $p$-edge-transitive graph such
that $\Phi(H[\emptyset])\neq\Phi(H)$. Then it holds that
$\hat{\chi}(\Phi,H)=(\pm 1)\mod p\,.$

Lemma 3.1 is implicitly proven in [21, Theorem 4.3], but for completeness we
will include a short and self-contained proof, demonstrating a first
application of the machinery of Sylow subgroups that we will need later.

For the proofs in this section, let us recall some key results from group
theory. Given a prime number $p$, a finite group $\Gamma^{\prime}$ is called a
_$p$ -group_ if the order $\\#\Gamma^{\prime}$ is a power of $p$. The
following is a well-known and central result from the theory of finite groups.

######  Theorem 3.2 (Sylow theorems).

Let $\Gamma$ be a finite group of order $\\#\Gamma=p^{k}m$ for a prime $p$ and
an integer $m\geq 1$ coprime to $p$. Then $\Gamma$ contains a subgroup
$\Gamma^{\prime}$ of order $p^{k}$. Moreover, every other subgroup
$\Gamma^{\prime\prime}$ of $\Gamma$ of order $p^{k}$ is conjugate to
$\Gamma^{\prime}$, that is there exists $g\in\Gamma$ with
$\Gamma^{\prime\prime}=g\Gamma^{\prime}g^{-1}$. In particular, the groups
$\Gamma^{\prime},\Gamma^{\prime\prime}$ are isomorphic (via the conjugation by
$g$).

Finally, every subgroup $\tilde{\Gamma}\subseteq\Gamma$ which is a $p$-group
is actually contained in some conjugate $g\Gamma^{\prime}g^{-1}$ of the group
$\Gamma^{\prime}$.

A subgroup $\Gamma^{\prime}\subseteq\Gamma$ as above is called a _$p$ -Sylow
subgroup_ of $\Gamma$.

The following result is a first important application of the Sylow theorems.
It can be found as Exercise (E28) in [1]; we include a proof for completeness.

######  Lemma 3.3.

Let $\Gamma$ be a finite group acting transitively on a set $T$ such that
$\\#T=p^{l}$ for some $l\geq 0$. Then the induced action of any $p$-Sylow
subgroup $\Gamma^{\prime}\subseteq\Gamma$ on $T$ is still transitive.

######  Proof 3.4.

Let $t_{0}\in T$ be any element, then $T$ is the orbit of $t_{0}$ under
$\Gamma$. Let
$\operatorname{Stab}_{\Gamma}(t_{0})=\\{g\in\Gamma:gt_{0}=t_{0}\\}$ be the
stabilizer of $t_{0}$ under the action of $\Gamma$. Then by the Orbit-
Stabilizer theorem, we have

$\\#\Gamma=(\\#\Gamma
t_{0})\cdot(\\#\operatorname{Stab}_{\Gamma}(t_{0}))=(\\#T)\cdot(\\#\operatorname{Stab}_{\Gamma}(t_{0})).$
(3)

As in the Sylow theorems, write $\\#\Gamma=p^{k}m$ with $m$ not divisible by
$p$ and let $\Gamma^{\prime}\subseteq\Gamma$ be a $p$-Sylow subgroup of
$\Gamma$, which is of order $p^{k}$. The stabilizer of $t_{0}$ under the
induced action of the subgroup $\Gamma^{\prime}\subseteq\Gamma$ is given by

$\operatorname{Stab}_{\Gamma^{\prime}}(t_{0})=\\{g\in\Gamma^{\prime}:gt_{0}=t_{0}\\}=\operatorname{Stab}_{\Gamma}(t_{0})\cap\Gamma^{\prime}.$

Clearly this is a subgroup of the group $\Gamma^{\prime}$ and by Lagrange’s
theorem, the order of $\operatorname{Stab}_{\Gamma^{\prime}}(t_{0})$ divides
the order $p^{k}$ of $\Gamma^{\prime}$. Thus it is itself a power of $p$, say
$\\#\operatorname{Stab}_{\Gamma^{\prime}}(t_{0})=p^{n}$.

On the other hand, $\operatorname{Stab}_{\Gamma^{\prime}}(t_{0})$ is also a
subgroup of $\operatorname{Stab}_{\Gamma}(t_{0})$. Inserting the order of
$\Gamma$ and the size of $T$ in equation (3) we obtain

$p^{k}m=p^{l}\cdot(\\#\operatorname{Stab}_{\Gamma}(t_{0})),$ (4)

and thus $\\#\operatorname{Stab}_{\Gamma}(t_{0})$ can at most contain a factor
of $p^{k-l}$. Again, by Lagrange’s theorem, the order $p^{n}$ of the subgroup
$\operatorname{Stab}_{\Gamma^{\prime}}(t_{0})$ divides the order of
$\operatorname{Stab}_{\Gamma}(t_{0})$ and thus $n\leq k-l$.

Finally, by the Orbit-Stabilizer theorem applied to the action of
$\Gamma^{\prime}$ on $t_{0}$, we have

$p^{k}=\\#\Gamma^{\prime}=(\\#\Gamma^{\prime}t_{0})\cdot(\\#\operatorname{Stab}_{\Gamma^{\prime}}(t_{0}))=(\\#\Gamma^{\prime}t_{0})\cdot
p^{n}.$ (5)

Thus, on the one hand we obtain $\\#\Gamma^{\prime}t_{0}=p^{k-n}\geq
p^{k-(k-l)}=p^{l}$. On the other hand we obtain $\Gamma^{\prime}t_{0}\subseteq
T$ and thus $\\#\Gamma^{\prime}t_{0}\leq\\#T=p^{l}$. Hence we have the
equality $\\#\Gamma^{\prime}t_{0}=p^{l}=\\#T$ and thus
$\Gamma^{\prime}t_{0}=T$. In other words, the action of $\Gamma^{\prime}$ on
$T$ is transitive, finishing the proof.

This result allows us to give a short proof of Lemma 3.1 above.

######  Proof 3.5 (Proof of Lemma 3.1).

Let $\Gamma=\mathsf{Aut}(H)$ be the automorphism group of the graph $H$, then
by assumption its action on the set $E(H)$ of edges of $H$ is transitive. By
Lemma 3.3, any $p$-Sylow subgroup $\Gamma^{\prime}\subseteq\Gamma$ still acts
transitively on $E(H)$. Now consider the sum

$\hat{\chi}(\Phi,H)=\sum_{S\subseteq E(H)}\Phi(H[S])\cdot(-1)^{\\#S}\,.$

The action of $\Gamma^{\prime}$ on $E(H)$ induces an action of
$\Gamma^{\prime}$ on the set of subsets $\mathcal{P}(E(H)):=\\{S\subseteq
E(H)\\}$ of $E(H)$. Indeed, for $S\subset E(H)$ and $g\in\Gamma^{\prime}$ we
define $gS=\\{gs:s\in S\\}$. For this action, the set $\mathcal{P}(E(H))$ can
be written as a disjoint union of the orbits $\Gamma^{\prime}S_{0}$ of a set
$\mathcal{S}\subseteq\mathcal{P}(E(H))$ of representatives $S_{0}$. (Recall
that for a group action two orbits are either disjoint or equal.) This allows
us to write the sum above as

$\hat{\chi}(\Phi,H)=\sum_{S_{0}\in\mathcal{S}}\sum_{S\in\Gamma^{\prime}S_{0}}\Phi(H[S])\cdot(-1)^{\\#S}\,.$

Until now we have just reordered the summands above, combining all summands
for $S$ in the same $\Gamma^{\prime}$ orbit.

Now since all elements $g\in\Gamma^{\prime}\subseteq\mathsf{Aut}(H)$ act by
graph automorphisms on $H$, we have that the graphs $H[gS_{0}]$ and $H[S_{0}]$
are isomorphic, so in particular $\Phi(H[gS_{0}])=\Phi(H[S_{0}])$. Applying
this to the formula for $\hat{\chi}(\Phi,H)$ above, we get

$\hat{\chi}(\Phi,H)=\sum_{S_{0}\in\mathcal{S}}(\\#\Gamma^{\prime}S_{0})\cdot\Phi(H[S_{0}])\cdot(-1)^{\\#S_{0}}\,.$
(6)

Now by the Orbit-Stabilizer theorem, the size $\\#\Gamma^{\prime}S_{0}$ of the
orbit of $S_{0}$ divides the order $p^{k}$ of $\Gamma^{\prime}$, so
$\\#\Gamma^{\prime}S_{0}$ is itself a power of $p$. Further, unless
$S_{0}\subseteq E(H)$ is invariant under $\Gamma^{\prime}$, the size of its
orbit $\\#\Gamma^{\prime}S_{0}$ is a _positive_ power of $p$ and thus
congruent to $0$ mod $p$. However, the only two sets $S_{0}\subseteq E(H)$
invariant under $\Gamma^{\prime}$ are $S_{0}=\emptyset$ and $S_{0}=E(H)$:
Consider for the sake of contradiction the case where $S_{0}$ is invariant
under $\Gamma^{\prime}$ and nonempty, but not the whole set $E(H)$. Then
$S_{0}$ contains an element $e_{0}$, and since $S_{0}$ is
$\Gamma^{\prime}$-invariant, $S_{0}$ also contains the entire orbit of $e_{0}$
under $\Gamma^{\prime}$. But since $\Gamma^{\prime}$ acted transitively on
$E(H)$, $S_{0}$ must have been the whole set $E(H)$, yielding a contradiction.

To summarize, when computing $\hat{\chi}(\Phi,H)$ modulo $p$ all but two
summands in the sum in Equation (6) are congruent to $0$. Hence, we can
simplify Equation (6) to

$\hat{\chi}(\Phi,H)=\Phi(H[\emptyset])+\Phi(H[E(H)])\cdot(-1)^{\\#E(H)}=\Phi(H[\emptyset])-\Phi(H)\mod
p\,.$

Note that we use the fact that for $p>2$ we have that $\\#E(H)$ is odd since
it is a prime power and for $p=2$ we have $-1=1$ modulo $p$. Now, the
condition $\Phi(H[\emptyset])\neq\Phi(H)$ exactly gives us
$\Phi(H[\emptyset])-\Phi(H)=\pm 1\mod p$.

There are two main examples for $p$-edge-transitive graphs. The first example
is the class of the complete, bipartite graphs $K_{p^{l},p^{m}}$ with $l,m\geq
0$. The graph $K_{p^{l},p^{m}}$ has $p^{l+m}$ edges and the automorphism group
clearly acts transitively on the edges of that graph. The second example is
the class of wreath graphs $W_{p^{k}}$ for $k\geq 1$. The graph $W_{p^{k}}$
has $p^{k}$ vertices that can be decomposed in disjoint sets
$V_{0},\ldots,V_{p-1}$ of order $p^{k-1}$ each, and edges
$\\{v_{i},v_{i+1}\\}$ for each $i=0,\ldots,p-1$ and vertices $v_{i}\in
V_{i},v_{i+1}\in V_{i+1}$ (where it is understood that $V_{p}=V_{0}$). Thus in
total, $W_{p^{k}}$ has $p^{2k-1}$ edges, except for $p=2$ where it has
$2^{2k-2}$ edges. The graph $W_{p^{k}}$ can be seen as the lexicographical
product of a $p$-cycle with a graph consisting of $p^{k-1}$ disjoint vertices.
For $k=1$ we exactly obtain the $p$-cycle. To see that $W_{p^{k}}$ is edge-
transitive, we observe that on the one hand, for fixed $i$ we can apply an
arbitrary permutation on $V_{i}$ leaving the graph invariant. On the other
hand, there exists a “rotational action” sending $V_{j}$ to $V_{j+1}$ for
$j=0,\ldots,p-1$, which also leaves the graph invariant. Using these two types
of automorphisms, we can map every edge to every other edge.

The following result tells us that in a certain sense the graphs
$K_{p^{l},p^{m}}$ and $W_{p^{k}}$ are the maximal $p$-edge-transitive graphs.
A graph $G$ is called _vertex-transitive_ if its automorphism group
$\mathsf{Aut}(G)$ acts transitively on its set of vertices $V(G)$.

######  Theorem 3.6 (Theorem 1.7 restated).

Let $G$ be a connected $p$-edge-transitive graph. Then either $G$ is bipartite
(and thus a subgraph of a graph of the form $K_{p^{l},p^{m}}$ for some
$l,m\geq 0$) or $G$ is vertex-transitive and an edge-subgraph of $W_{p^{k}}$
for $k\geq 1$ (or both).

For the proof of Theorem 3.6, we will make use of the following well-known
result about the relation between edge and vertex-transitivity [2, Proposition
15.1].

######  Lemma 3.7.

Let $G$ be a connected graph and let $\Gamma\subseteq\mathsf{Aut}(G)$ be a
subgroup acting transitively on the set of edges $E(G)$. Then either $\Gamma$
acts transitively on the set of vertices $V(G)$ (and thus $G$ is vertex-
transitive) or $G$ is bipartite (or both).

The proof from [2] carries over verbatim to the setting of the previous lemma,
by replacing the full group $\mathsf{Aut}(G)$ with the subgroup $\Gamma$. We
include it for completeness.

######  Proof 3.8.

Let $e_{0}=\\{v_{1},v_{2}\\}\in E(G)$ be some edge. Then for each vertex
$w_{1}$ and some edge $\\{w_{1},w_{2}\\}$ incident to $w_{1}$ there exists an
automorphism $g\in\Gamma$ sending $\\{v_{1},v_{2}\\}$ to $\\{w_{1},w_{2}\\}$,
thus either $w_{1}=gv_{1}$ or $w_{1}=gv_{2}$. This proves that the set $V(G)$
is the union of the orbits of $v_{1},v_{2}$ under $\Gamma$. If these two
orbits intersect, then in fact $\Gamma v_{1}=\Gamma v_{2}$ (orbits under a
group action are either disjoint or equal), and so $\Gamma v_{1}=V(G)$ since
the two sets above cover $V(G)$. On the other hand, if the two orbits are
disjoints, then they form a partition making $G$ into a bipartite graph.
Indeed, any edge of $G$ is in the orbit of the edge $\\{v_{1},v_{2}\\}$ and
thus connects an element of $\Gamma v_{1}$ to an element of $\Gamma v_{2}$.

######  Proof 3.9 (Proof of Theorem 3.6).

Let $G$ be a $p$-edge-transitive, non-bipartite graph. Then by Lemma 3.3 any
$p$-Sylow subgroup $\Gamma\subseteq\mathsf{Aut}(G)$ still acts transitively on
the edges $E(G)$ of $G$. By Lemma 3.7, since $G$ is not bipartite, the group
$\Gamma$ acts transitively on the set of vertices $V(G)$ (and thus $G$ is also
vertex-transitive). We observe that in this case, by the Orbit-Stabilizer
theorem, we have $\\#V(G)=p^{k}$ for some $k\geq 1$. We claim that then $G$ is
a subgraph of $W_{p^{k}}$.

To see this, let us reformulate our situation slightly: We identify the vertex
set $V(G)$ with the set $[p^{k}]=\\{1,\ldots,p^{k}\\}$. Then we can
canonically identify $\mathsf{Aut}(G)$ as a subgroup of $S_{p^{k}}$, the
symmetric group on $[p^{k}]$ (this is because a graph automorphism is uniquely
determined by its action on the vertices of a graph). Inside $\mathsf{Aut}(G)$
we have the subgroup $\Gamma$, which is a $p$-group. By the Sylow theorem,
there exists a $p$-Sylow subgroup $\Gamma^{\prime}\subseteq S_{p^{k}}$
containing $\Gamma$. Since the action of $\Gamma$ is transitive on the set of
edges $E(G)$, we can obtain $E(G)$ by starting with some edge
$e_{0}=\\{v_{1},v_{2}\\}\in E(G)$ with $v_{1},v_{2}\in[p^{k}]$ and taking its
orbit $\\{\\{gv_{1},gv_{2}\\}:g\in\Gamma\\}=E(G)$. But note that by instead
taking the orbit of $e_{0}$ under $\Gamma^{\prime}\subseteq S_{p^{k}}$ we get
at least this set of edges and maybe more. Denote by $G^{\prime}$ the graph
with vertices $[p^{k}]$ and edges
$\\{\\{gv_{1},gv_{2}\\}:g\in\Gamma^{\prime}\\}$. We claim that
$G^{\prime}\cong W_{p^{k}}$.

To show this we will explicitly identify the $p$-Sylow subgroup
$\Gamma^{\prime}\subseteq S_{p^{k}}$ (recall that by the Sylow theorem it is
unique up to conjugation, that is reordering of the elements of $[p^{k}]$).

First note that $S_{p^{k}}$ has $(p^{k})!$ elements. Inductively one sees that
the highest power of $p$ appearing in this number is $p^{e(k)}$ for
$e(k)=p^{k-1}+p^{k-2}+\ldots+p+1$. We will inductively construct a subgroup
$\Gamma(p,k)$ of $S_{p^{k}}$ with $p^{e(k)}$ elements, which then is a
$p$-Sylow subgroup. We note that a description of such a $p$-Sylow subgroup is
given in [25].

For $k=1$ we have $e(k)=1$ and a $p$-Sylow subgroup $\Gamma(p,1)\subseteq
S_{p}$ is generated by a cyclic permutation $1\mapsto 2,2\mapsto
3,\ldots,p\mapsto 1$ of the elements of $[p]$. The group $\Gamma(p,1)$ is
isomorphic to the cyclic group $\mathbb{Z}/p\mathbb{Z}$.

Now assume we constructed $\Gamma(p,k-1)$ for some $k\geq 2$, then we first
note that a product of $p$ copies $\prod_{i=0}^{p-1}\Gamma(p,k-1)$ of
$\Gamma(p,k-1)$ acts on $[p^{k}]$ where the $i$-th factor acts by permutations
on the elements $ip^{k-1}+1,ip^{k-1}+2,\ldots,ip^{k-1}+p^{k-1}=(i+1)p^{k-1}$.
All of these actions commute, so we can see the product
$\prod_{i=0}^{p-1}\Gamma(p,k-1)$ as a subgroup of $S_{p^{k}}$. However, there
is a further action of $\mathbb{Z}/p\mathbb{Z}$ on $[p^{k}]$ sending $j$ to
$j+p^{k-1}$ (modulo $p^{k}$). This action cyclically permutes the $p$ blocks
of $p^{k-1}$ elements in $[p^{k}]$ on which the $p$ factors of
$\prod_{i=0}^{p-1}\Gamma(p,k-1)$ act. Thus these two actions do not commute,
but indeed they induce an action of the semidirect product

$\Gamma(p,k)=\left(\prod_{i=0}^{p-1}\Gamma(p,k-1)\right)\rtimes\mathbb{Z}/p\mathbb{Z},$

where $\mathbb{Z}/p\mathbb{Z}$ acts on $\prod_{i=0}^{p-1}\Gamma(p,k-1)$ by
permuting the factors of the product. We claim that $\Gamma(p,k)$ is the
desired $p$-Sylow subgroup of $S_{p^{k}}$.

Indeed, as a semidirect product its number of elements is

$\\#\Gamma(p,k)=(\\#\Gamma(p,k-1))^{p}\cdot p=(p^{e(k-1)})^{p}\cdot
p=p^{pe(k-1)+1}=p^{e(k)},$

so it has the correct number of elements and is indeed a subgroup of
$S_{p^{k}}$.

Now recall what we want to show: for a pair $\\{v_{1},v_{2}\\}$ of vertices
forming an edge of our original graph $G$, we want to show that the graph
$G^{\prime}$ with edges
$\\{\\{gv_{1},gv_{2}\\}:g\in\Gamma^{\prime}\cong\Gamma(p,k)\\}$ is isomorphic
to the wreath graph $W_{p^{k}}$. By relabeling the vertices (that is
performing a conjugation in $S_{p^{k}}$) we may assume that
$\Gamma^{\prime}=\Gamma(p,k)$. Furthermore, by a translation in the group
$\Gamma(p,k)$, which acts transitively on the elements of $[p^{k}]$, we may
assume that $v_{1}=1$. Now if $v_{2}$ were in the first block $[p^{k-1}]$ of
vertices, on which the first factor $\Gamma(p,k-1)$ operates, then it is easy
to see that the resulting graph $G^{\prime}$ would not be connected: the first
factor $\Gamma(p,k-1)$ would send the edge $\\{1,v_{2}\\}$ only to edges
within the first block $[p^{k-1}]$ and then the cyclic permutation by the
factor $\mathbb{Z}/p\mathbb{Z}$ would send this pattern of edges to the $p-1$
other blocks, giving us a disjoint union of $p$ graphs. This is not possible,
since our original graph $G$ is a subgraph of $G^{\prime}$ and also was
assumed to be connected.

Thus we may assume that $v_{2}$ is in one of the other blocks
$P(a)=[p^{k-1}]+ip^{k-1}$ for $a=1,\ldots,p-1$. Now we want to argue that we
can reorder these blocks, sending $P(a)$ to $P(1)$ and leaving $P(0)$
invariant, such that the group action of $\Gamma(p,k)$ is respected. And
indeed, let $b\in\mathbb{Z}/p\mathbb{Z}$ be the multiplicative inverse of $a$
(such that $ab=1\mod p$), then there is a permutation of $[p^{k}]$ sending the
block $P(i)$ to $P(i\cdot b\mod p)$ (where the block is just translated as a
whole, not permuting the elements inside). And indeed, we see that $P(a)$ is
sent to $P(1)$. The reason why this permutation respects the form of the
action555To be precise, what happens is the following: the map sending $P(i)$
to $P(i\cdot b\mod p)$ is a permutation of $[p^{k}]$, that is an element
$\sigma\in S_{p^{k}}$. What we are claiming is that the subgroup
$\Gamma(p,k)\subseteq S_{p^{k}}$ is stable under the conjugation by $\sigma$,
that is $\Gamma(p,k)=\sigma\Gamma(p,k)\sigma^{-1}$. So $\sigma$ is a
relabeling of the vertices of our graph $G^{\prime}$ which leaves the graph
itself invariant. of $\Gamma(p,k)$ is that multiplication by $b$ induces a
group isomorphism $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$ on the
semidirect factor $\mathbb{Z}/p\mathbb{Z}$ of $\Gamma(p,k)$.

To summarize, we can assume without loss of generality that we start with an
edge $\\{1,v_{2}\\}$ with $v_{2}$ in the second block of vertices. But then it
is easy to see that the graph $G^{\prime}$ obtained by taking the orbit of
$\\{1,v_{2}\\}$ under $\Gamma(p,k)$ is indeed the wreath graph $W_{p^{k}}$.
Indeed, the group $\Gamma(p,k)$ acts transitively within each of the $p$
blocks of vertices (since the $i$-th factor $\Gamma(p,k-1)$ above acts
transitively there), so every edge from the first to the second block is in
the orbit of $\\{1,v_{2}\\}$. Then finally the cyclic permutation action of
$\mathbb{Z}/p\mathbb{Z}$ sends these edges to the set of all edges between
blocks $i$ and $i+1$, which exactly gives the set of edges of the wreath
graph. This finishes the proof.

##  4 The main reduction: From homomorphisms to induced subgraphs

In what follows we will construct a sequence of reductions, starting from
$\\#\textsc{Hom}(\mathcal{H})$ and ending in $\\#\textsc{IndSub}(\Phi)$. Here,
$\mathcal{H}$ is a recursively enumerable set of $p$-edge-transitive graphs
and $\Phi$ is a graph property such that for every graph $H\in\mathcal{H}$ we
have that $\Phi(H[\emptyset])\neq\Phi(H)$.

More precisely, we will prove that

$\\#\textsc{Hom}(\mathcal{H})\stackrel{{\scriptstyle\text{Lemma\leavevmode\nobreak\
\ref{lem:hom_to_colhom}}}}{{\leq^{\mathrm{fpt}}_{\mathrm{T}}}}\\#\textsc{cp-
Hom}(\mathcal{H})\stackrel{{\scriptstyle\text{Lemma\leavevmode\nobreak\
\ref{lem:main_lem}}}}{{\leq^{\mathrm{fpt}}_{\mathrm{T}}}}\\#\textsc{cp-
IndSub}(\Phi)\stackrel{{\scriptstyle\text{Lemma\leavevmode\nobreak\
\ref{lem:col_ind_sub_to_ind_sub}}}}{{\leq^{\mathrm{fpt}}_{\mathrm{T}}}}\\#\textsc{IndSub}(\Phi)$
(7)

In particular, all of those reductions will be tight in the sense that
conditional lower bounds on the fine-grained complexity of
$\\#\textsc{Hom}(\mathcal{H})$ immediately transfer to
$\\#\textsc{IndSub}(\Phi)$. For the hardness results we rely on a result of
Dalmau and Jonsson [9] stating that the problem $\\#\textsc{Hom}(\mathcal{H})$
is known to be $\\#\mathsf{W[1]}$-hard whenever $\mathcal{H}$ is recursively
enumerable and of unbounded treewidth.666We remark that the graph parameter of
treewidth is not used explicitly in this work. Hence we omit the definition
and refer the interested reader e.g. to Chapter 11 in [12]. Here a class of
graphs is said to have unbounded treewidth if for every $b\in\mathbb{N}$ there
exists a graph in the class with treewidth at least $b$.

#### Reducing homomorphisms to color-prescribed homomorphisms

In the first reduction we are given graphs $H$ and $G$ and the goal is to
compute $\\#\mbox{$\mathsf{Hom}(H\to G)$}$ using an oracle for
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to\star)$. This can be done by taking
precisely $|V(H)|$ copies of the vertices of $G$, that is, one for each vertex
in $H$ and then adding an edge between two vertices $u$ and $v$ if they have
been adjacent in $G$ and the vertices of $H$ corresponding to the copies of
$V(G)$ that contain $u$ and $v$ are adjacent in $H$ as well. The construction
is formalized in the proof of the following lemma. In particular it is shown
that the resulting graph $\hat{G}$ is $H$-colored.

######  Lemma 4.1.

Let $H$ be a graph. There exists an algorithm $\mathbb{A}$ that is given a
graph $G$ as input and has oracle access to the function
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to\star)$ and computes
$\\#\mbox{$\mathsf{Hom}(H\to G)$}$ in time $f(|V(H)|)\cdot|V(G)|$ where $f$ is
a computable function. Furthermore, every oracle query $\hat{G}$ satisfies
$|V(\hat{G})|\leq f(|V(H)|)\cdot|V(G)|$.

######  Proof 4.2.

Let $k=|V(H)|$. It will be convenient to assume that $V(H)=[k]$. Given $G$, we
construct a graph $\hat{G}$ as follows. The vertex set of $\hat{G}$ is defined
to be

$V(\hat{G})=\bigcup_{i=1}^{k}V_{i}\,,$

where $V_{i}=\\{v_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ v\in V(G)\\}$
is a copy of $V(G)$ identified with vertex $i\in V(H)$. We add an edge
$\\{u_{i},v_{j}\\}$ to $\hat{G}$ if and only if $\\{i,j\\}\in E(H)$ and
$\\{u,v\\}\in E(G)$. Now it can easily be verified that the function
$c:V(\hat{G})\to V(H)$ given by $c(v_{i}):=i$ is an $H$-coloring of $\hat{G}$.
Furthermore it is easy to see that

$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to\hat{G})=\\#\mbox{$\mathsf{Hom}(H\to
G)$}\,,$

which concludes the proof.

#### Reducing color-prescribed homomorphisms to color-prescribed induced
subgraphs

The reduction from color-prescribed homomorphisms to color-prescribed induced
subgraphs requires the introduction of an $H$-colored variant of the framework
of graph motif parameters, which was explicitly introduced in [8] and
implicitly used in [4]. More precisely, given an $H$-colored graph $G$ and a
property $\Phi$, we will express
$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$ as a linear combination of
color-prescribed homomorphisms, that is, terms of the form
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to G)$. In a first step, we show
complexity monotonicity for linear combinations of color-prescribed
homomorphisms. While this property allows a quite simple proof, a second step,
in which we study the coefficient of $\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to
G)$ requires a thorough understanding of the alternating enumerator of $\Phi$
and $H$. In case of $p$-edge-transitive graphs, the latter is provided by
Lemma 3.1.

We start by introducing a colored variant of the tensor product of graphs (see
e.g. Chapter 5.4.2 in [17]). Given two $H$-colored graphs $G$ and $\hat{G}$
with colorings $c$ and $\hat{c}$ we define their _color-prescribed_ tensor
product $G\times_{H}\hat{G}$ as the graph with vertices $V=\\{(v,\hat{v})\in
V(G)\times V(\hat{G})\leavevmode\nobreak\ |\leavevmode\nobreak\
c(v)=\hat{c}(\hat{v})\\}$ and edges between two vertices $(v,\hat{v})$ and
$(u,\hat{u})$ if and only if $\\{v,u\\}\in E(G)$ and $\\{\hat{v},\hat{u}\\}\in
E(\hat{G})$. The next lemma states that $\\#\mathsf{cp}\text{-}\mathsf{Hom}$
is linear with respect to $\times_{H}$.

######  Lemma 4.3.

Let $H$ be a graph, let $F$ be an edge-subgraph of $H$ and let $G$ and
$\hat{G}$ be $H$-colored. Then we have that

$\\#\mathsf{cp}\text{-}\mathsf{Hom}(F\to
G\times_{H}\hat{G})=\\#\mathsf{cp}\text{-}\mathsf{Hom}(F\to
G)\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(F\to\hat{G})\,.$

######  Proof 4.4.

It can easily be verified that the function
$b(h,\hat{h})(v):=(h(v),\hat{h}(v))$ that assigns elements in
$\mathsf{cp}\text{-}\mathsf{Hom}(F\to
G)\times\mathsf{cp}\text{-}\mathsf{Hom}(F\to\hat{G})$ to elements in
$\mathsf{cp}\text{-}\mathsf{Hom}(F\to G\times_{H}\hat{G})$ is a well-defined
bijection.

The proof of the complexity monotonicity property for color-prescribed
homomorphisms (Lemma 4.7) will require to solve a system of linear equations.
The following lemma proves that the corresponding matrix is non-singular.

######  Lemma 4.5.

Let $H$ be a graph and let $M$ be a quadratic matrix of size $2^{|E(H)|}$ such
that the rows and columns are identified by the subsets of edges of $H$.
Furthermore assume that the entries of $M$ are given by
$M(S,T):=\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to H[T])$. Then $M$ is non-
singular. This holds true even if $M$ is considered as a matrix over
$\mathbb{Z}_{p}$, that is, the field with $p$ elements. In the latter case,
the entries are taken modulo $p$.

######  Proof 4.6.

We fix any linear extension $\lesssim$ of the subset inclusion relation on
$E(H)$ and order the columns and rows of $M$ accordingly. We claim that $M$ is
triangular. To see this we first observe that $M(S,S)=1$ for every $S$, given
by the identity homomorphism from $H[S]$ to $H[S]$ which is, of course, color-
prescribed. Now consider $M(S,T)$ for some $T\neq S$ with $T\lesssim S$. It
follows that there exists an edge $\\{u,v\\}$ in $S\setminus T$ since
$\lesssim$ linearly extends subset inclusion. Now assume that there exists a
color-prescribed homomorphism $h$ from $H[S]$ to $H[T]$. By color-
prescribedness we have that $h(u)=u$ and $h(v)=v$, contradicting the fact that
$h$ is a homomorphism and $\\{u,v\\}\notin T$. Hence $M(S,T)=0$ and,
consequently, $M$ is triangular.

We are now prepared to prove the color-prescribed variant of complexity
monotonicity.

######  Lemma 4.7 (Complexity monotonicity).

Let $H$ be a graph and let $a$ be a function from edge-subgraphs of $H$ to
rationals. There exists an algorithm $\mathbb{A}$ that is given an $H$-colored
graph $G$ as input and has oracle access to the function

$\sum_{S\subseteq
E(H)}a(H[S])\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to\star)\,,$

and computes $\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to G)$ for all $S$ such
that $a(H[S])\neq 0$ in time $f(|H|)\cdot|V(G)|$ where $f$ is a computable
function. Furthermore, every oracle query $\hat{G}$ satisfies
$|V(\hat{G})|\leq f(|H|)\cdot|V(G)|$.

######  Proof 4.8.

Using Lemma 4.3 we have that for every $H$-colored graph $F$ it holds that

$\displaystyle\sum_{S\subseteq
E(H)}a(H[S])\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to(G\times_{H}F))$
(8) $\displaystyle=$ $\displaystyle\sum_{S\subseteq
E(H)}a(H[S])\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to
G)\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to F)\,,$ (9)

which we can evaluate for $F=H[\emptyset],\dots,H[E(H)]$. This induces a
system of linear equations and the corresponding matrix is non-singular by
Lemma 4.5. Consequently, the numbers
$a(H[S])\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to G)$ are uniquely
determined and can be computed by solving the system using Gaussian
elimination. Finally, we obtain the numbers
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S]\to G)$ by multiplying with
$a(H[S])^{-1}$ whenever $a(H[S])\neq 0$.

It remains to express the number of color-prescribed induced subgraphs that
satisfy a property $\Phi$ as a linear combination of color-prescribed
homomorphisms.

######  Lemma 4.9.

Let $H$ be a graph, let $\Phi$ be a graph property and let $G$ be an
$H$-colored graph. Then it holds that

$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)=\sum_{S\in
E(H)}\Phi(H[S])\sum_{J\subseteq E(H)\setminus
S}(-1)^{\\#J}\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}([H[S\cup J]\to G)\,.$

Moreover, the absolute values of the coefficient of
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to G)$ and $\hat{\chi}(\Phi,H)$ are
equal.

######  Proof 4.10.

We start by establishing the following claim.

######  Claim 1.

Let $H$ be graph, let $S\subseteq E(H)$ and let $G$ be an $H$-colored graph.
Then we have that

$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(H[S]\to G)=\sum_{J\subseteq
E(H)\setminus S}(-1)^{\\#J}\cdot\\#\mathsf{cp}\text{-}\mathsf{Sub}(H[S\cup
J]\to G)\,.$

It holds that

$\mathsf{cp}\text{-}\mathsf{IndSub}(H[S]\to
G)=\mathsf{cp}\text{-}\mathsf{Sub}(H[S]\to G)\setminus\left(\bigcup_{e\in
E(H)\setminus S}\mathsf{cp}\text{-}\mathsf{Sub}(H[S\cup\\{e\\}]\to
G)\right)\,,$ (10)

and hence, by inclusion-exclusion,

$\displaystyle\\#\mathsf{cp}\text{-}\mathsf{IndSub}(H[S]\to G))$ (11)
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\\#\mathsf{cp}\text{-}\mathsf{Sub}(H[S]\to
G)-\sum_{\emptyset\subsetneq J\subseteq E(H)\setminus
S}(-1)^{\\#J-1}\cdot\\#\mathsf{cp}\text{-}\mathsf{Sub}(H[S\cup J]\to G)$ (12)
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle\sum_{J\subseteq
E(H)\setminus S}(-1)^{\\#J}\cdot\\#\mathsf{cp}\text{-}\mathsf{Sub}(H[S\cup
J]\to G)\,.$ (13)

Now we have that

$\displaystyle\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)=$
$\displaystyle\sum_{S\in
E(H)}\Phi(H[S])\cdot\\#\mathsf{cp}\text{-}\mathsf{IndSub}(H[S]\to G)$ (14)
$\displaystyle=$ $\displaystyle\sum_{S\in E(H)}\Phi(H[S])\sum_{J\subseteq
E(H)\setminus S}(-1)^{\\#J}\cdot\\#\mathsf{cp}\text{-}\mathsf{Sub}(H[S\cup
J]\to G)$ (15) $\displaystyle=$ $\displaystyle\sum_{S\in
E(H)}\Phi(H[S])\sum_{J\subseteq E(H)\setminus
S}(-1)^{\\#J}\cdot\\#\mathsf{cp}\text{-}\mathsf{Hom}(H[S\cup J]\to G)$ (16)

where (14) follows from the definition of
$\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$, (15) is Claim 1 and (16)
holds as color-prescribed homomorphisms are injective and a color-prescribed
embedding is uniquely identified by its image. Collecting for the coefficient
of $\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to G)$ yields

$\displaystyle\sum_{S\in
E(H)}\Phi(H[S])\cdot(-1)^{\\#E(H)-\\#S}=(-1)^{\\#E(H)}\cdot\hat{\chi}(\Phi,H)\,.$
(17)

The application of the complexity monotonicity property for color-prescribed
homomorphisms (Lemma 4.7) requires non-zero coefficients. However, this can be
guaranteed for the coefficient of interest in case of $p$-edge-transitive
graphs as shown in Section 3. Formally, the reduction is constructed as
follows.

######  Lemma 4.11.

Let $\Phi$ be a graph property and let $H$ be a $p$-edge-transitive graph such
that $\Phi(H[\emptyset])\neq\Phi(H)$. There exists an algorithm $\mathbb{A}$
that is given an $H$-colored graph $G$ as input and has oracle access to the
function $\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to\star)$ and computes
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to G)$ in time $f(|H|)\cdot|V(G)|$ where
$f$ is a computable function. Furthermore, every oracle query $\hat{G}$ is
$H$-colored as well and satisfies $|V(\hat{G})|\leq f(|H|)\cdot|V(G)|$.

######  Proof 4.12.

Using Lemma 4.9 we can express
$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to\star)$ as a linear combination
of color-prescribed homomorphisms. In particular, the coefficient of
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to\star)$ is $(\pm
1)\cdot\hat{\chi}(\Phi,H)$ and by Lemma 3.1 we have that this number is non-
zero whenever $H$ is $p$-edge-transitive and $\Phi(H[\emptyset])\neq\Phi(H)$.
Hence we can use the algorithm from Lemma 4.7 to compute
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(H\to G)$ in the desired running time.

#### Reducing color-prescribed induced subgraphs to uncolored induced
subgraphs

The last part of the reduction sequence allows us to get rid of the colors.
More precisely, we will reduce the problem of counting color-prescribed
induced subgraphs of an $H$-colored graph to the problem of counting uncolored
induced subgraphs of size $|V(H)|$ in a graph, both with respect to some
property $\Phi$. The proof is a straightforward application of the inclusion-
exclusion principle.

######  Lemma 4.13.

Let $\Phi$ be a graph property and let $H$ be a graph with $k$ vertices. There
exists an algorithm $\mathbb{A}$ that is given an $H$-colored graph $G$ as
input and has oracle access to the function
$\\#\mbox{$\mathsf{IndSub}(\Phi,k\to\star)$}$ and computes
$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$ in time $f(k)\cdot|V(G)|$
where $f$ is a computable function. Furthermore, every oracle query $\hat{G}$
satisfies $|V(\hat{G})|\leq|V(G)|$ and, in particular, $\hat{G}$ allows an
$H$-coloring as well.

######  Proof 4.14.

It will be convenient to assume that $V(H)=[k]$. We first check whether the
$H$-coloring $c$ of $G$ is surjective. If this is not the case then there
exists some vertex $i\in V(H)$ such that $i\notin\mathsf{im}(c)$ and hence
there is no color-prescribed induced subgraph of $G$, so $\mathbb{A}$ can just
output $0$. Otherwise, the $H$-coloring of $G$ induces a partition of $V(G)$
in $k$ many non-empty and pairwise disjoint subsets, each associated with some
“color” $i\in V(H)$. This allows us to equivalently express
$\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$ in terms of vertex-colorful
induced subgraphs:

$\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to
G)=\left\\{S\subseteq\binom{V(G)}{k}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ c(S)=[k]\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ \Phi(G[S])=1\right\\}$ (18)

By the principle of inclusion and exclusion we obtain that

$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to
G)=\sum_{J\subseteq[k]}(-1)^{\\#J}\cdot\\#\mbox{$\mathsf{IndSub}(\Phi,k\to
G_{J})$}\,,$ (19)

where $G_{J}$ is the graph obtained from $G$ by deleting all vertices that are
colored with some color in $J$. Hence we can compute
$\\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi\to G)$ using $2^{k}$ oracle calls.
Finally, we observe that $H$-colored graphs are closed under the removal of
vertices and therefore every oracle query $G_{J}$ allows an $H$-coloring.

##  5 Non-trivial monotone properties on bipartite graphs

In the last part of the paper, we apply the algebraic approach which was laid
out in the preceding sections to bipartite graph properties. This will allow
us to prove our main result. To this end, we say that a set
$\mathcal{K}\subseteq\mathbb{N}$ is _dense_ if there exists a constant $c$
such that for every $k^{\prime}\in\mathbb{N}$ there exists $k\in\mathcal{K}$
such that $k^{\prime}\leq k\leq ck^{\prime}$. Furthermore, we write
$\mathsf{IS}_{k}$ for the graph with $k$ isolated vertices. The following
theorem is obtained by invoking the reduction sequence (7) to complete
bipartite graphs $K_{t,t}$ for prime powers $t=p^{k}$, which are $p$-edge-
transitive (see Section 3). The extension to modular counting can be found in
the appendix.

######  Theorem 5.1 (Theorem 1.1 restated).

Let $\Phi$ be a computable graph property and let $\mathcal{K}$ be the set of
all prime powers $t$ such that $\Phi(\mathsf{IS}_{2t})\neq\Phi(K_{t,t})$. If
$\mathcal{K}$ is infinite then $\\#\textsc{IndSub}(\Phi)$ is
$\\#\mathsf{W[1]}$ hard. If additionally $\mathcal{K}$ is dense then it cannot
be solved in time $f(k)\cdot n^{o(k)}$ for any computable function $f$ unless
ETH fails. This holds true even if the input graphs to
$\\#\textsc{IndSub}(\Phi)$ are restricted to be bipartite.

While $\\#\mathsf{W[1]}$-hardness will follow by the classification of Dalmau
and Jonsson [9], hardness under ETH requires a tight reduction from counting
cliques, which we will present first. In particular we use a trick inspired by
Lemma 1.11 in [7] to make the reduction parsimonious which is required for the
extension to modular counting in the subsequent section.

######  Lemma 5.2.

There exists an algorithm that, given a positive integer $\ell>1$ and a graph
$G$ with $n$ vertices, computes in time $O(\ell n)$ a $K_{\ell,\ell}$-colored
graph $G^{\prime}$ with at most $O(\ell n)$ vertices such that the number of
cliques of size $\ell$ in $G$ equals
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(K_{\ell,\ell}\to G^{\prime})$.

######  Proof 5.3.

Let the vertex set of $G$ be $\\{v_{i}\mid 1\leq i\leq n\\}$ and let that of
$K_{\ell,\ell}$ be $\\{a_{i},b_{i}\mid 1\leq i\leq\ell\\}$. We now construct
the graph $G^{\prime}$ on the vertex set $\\{u_{i,j},w_{i,j}\mid 1\leq
i\leq\ell,1\leq j\leq n\\}$ with a $K_{\ell,\ell}$-coloring given by
$c(u_{i,j})=a_{i}$ and $c(w_{i,j})=b_{i}$. We add an edge between $u_{i,j}$
and $w_{i^{\prime},j^{\prime}}$ if and only if

  * •

either $(i,j)=(i^{\prime},j^{\prime})$,

  * •

or $i<i^{\prime}$, $j<j^{\prime}$ and the vertices $v_{j}$ and
$v_{j^{\prime}}$ are adjacent,

  * •

or $i>i^{\prime}$, $j>j^{\prime}$ and the vertices $v_{j}$ and
$v_{j^{\prime}}$ are adjacent.

Let $\\{v_{i_{1}},\ldots v_{i_{\ell}}\\}$ be an $\ell$-clique in $G$. Assume
w.l.o.g. that $i_{k}<i_{k^{\prime}}$ for $k<k^{\prime}$. Then the set
$\\{u_{1,j_{1}},\ldots u_{\ell,j_{\ell}},w_{1,i_{1}},\ldots
w_{\ell,j_{\ell}}\\}$ forms a colorful biclique in $G^{\prime}$, so it gives
rise to a color-prescribed homomorphism
$h\in\mathsf{cp}\text{-}\mathsf{Hom}(K_{\ell,\ell}\to G^{\prime})$. Now let
$h^{\prime}\in\mathsf{cp}\text{-}\mathsf{Hom}(K_{\ell,\ell}\to G^{\prime})$ be
a color-prescribed homomorphism. Then there has to be the following colorful
biclique in $G^{\prime}$:

$\\{u_{1,\alpha_{1}},\ldots u_{\ell,\alpha_{\ell}},w_{1,\beta_{1}},\ldots
w_{\ell,\beta_{\ell}}\\}\,.$

We first see that for every $i$ we have $\alpha_{i}=\beta_{i}$ since there has
to be an edge between $u_{i,\alpha_{i}}$ and $w_{i,\beta_{i}}$. Furthermore
the edges enforce $\alpha_{j}<\beta_{j^{\prime}}$ for every $j<j^{\prime}$.
Thus $\\{v_{\alpha_{1}},\ldots,v_{\alpha_{\ell}}\\}$ is a clique of size
$\ell$ in $G$. Since every homomorphism yields
$\beta_{j}=\alpha_{j}<\beta_{j^{\prime}}=\alpha_{j^{\prime}}$ for
$j<j^{\prime}$ there is exactly one homomorphism in
$\mathsf{cp}\text{-}\mathsf{Hom}(K_{\ell,\ell}\to G^{\prime})$ corresponding
to each $\ell$-clique in $G$.

######  Proof 5.4 (Proof of Theorem 5.1).

Let $\Phi$ and $\mathcal{K}$ be as given in Theorem 5.1. We define a class of
graphs $\mathcal{H}$ as follows:

$\mathcal{H}=\\{K_{t,t}\leavevmode\nobreak\ |\leavevmode\nobreak\
t\in\mathcal{K}\\}\,.$

By the reductions sequence (7), given by Lemma 4.1, Lemma 4.11 and Lemma 4.13,
we obtain that
$\\#\textsc{Hom}(\mathcal{H})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{IndSub}(\Phi)$.
As $\Phi$ is computable, $\mathcal{H}$ is recursively enumerable. Furthermore,
as $\mathcal{K}$ is infinite, we have that there are arbitrary large bicliques
in $\mathcal{H}$ and, in particular, the treewidth of $\mathcal{H}$ is
unbounded. Therefore $\\#\textsc{Hom}(\mathcal{H})$, and hence
$\\#\textsc{IndSub}(\Phi)$, are $\\#\mathsf{W[1]}$-hard by the classification
of counting homomorphisms due to Dalmau and Jonsson [9]. For the tight bound
under ETH, we reduce from the _decision problem_ Clique which asks, given $G$
and $k$, to _decide_ whether $G$ contains a clique of size $k$ and which
cannot be solved in time $f(k)\cdot n^{o(k)}$ for any computable function $f$,
unless ETH fails [5, 6]. Now assume that $\mathcal{K}$ is dense and let
$(G,k)$ be an instance of Clique. By density of $\mathcal{K}$, there exists
$\ell\in\mathcal{K}$ such that $k\leq\ell\leq ck$ for some overall constant
$c$ independent of $k$. We construct the graph $\hat{G}$ from $G$ by adding
$\ell-k$ further vertices and adding edges between all new vertices as well as
between every pair of an old and a new vertex. It can then easily be verified
that $G$ contains a clique of size $k$ if and only if $\hat{G}$ contains a
clique of size $\ell$.

Next we apply Lemma 5.2 to $\hat{G}$ and $\ell$, and obtain an
$K_{\ell,\ell}$-colored graph $G^{\prime}$ satisfying that the number of
$\ell$-cliques in $\hat{G}$ is equal to
$\\#\mathsf{cp}\text{-}\mathsf{Hom}(K_{\ell,\ell}\to G^{\prime})$. Finally, we
invoke Lemma 4.11 and Lemma 4.13 to conclude the reduction. In particular, all
reductions are tight in the sense that every oracle call for
$\\#\textsc{IndSub}(\Phi)$ in the final part of the reduction is a pair
$(\tilde{G},2\ell)$ where the number of vertices of $\tilde{G}$ is bounded by
$O(\ell\cdot|V(G)|)$. As $\ell\leq ck$ we conclude that every algorithm that
solves $\\#\textsc{IndSub}(\Phi)$ in time $f(k)\cdot n^{o(k)}$ can be used to
solve Clique in time $f(k)\cdot n^{o(k)}$ — just check in the end whether the
output is a number greater than zero.

Finally, we point out that for both ($\\#\mathsf{W[1]}$ and ETH) hardness
results, the last part of the reduction, that is, Lemma 4.13 only queries for
graphs that are $K_{t,t}$-colorable and hence bipartite.

Note that, in case $\Phi$ or its complement is edge-monotone, we only have to
find infinitely many prime powers $t$ for which $\Phi$ is neither true nor
false on the set of all edge-subgraphs of $K_{t,t}$, which is the case for all
sensible, non-trivial properties that do not rely on the number of vertices in
some way. If $\Phi$ (or its complement) is monotone, that is, not only closed
under the removal of edges, but also under the removal of vertices, then such
artificial properties do not exist and we can state the result more clearly as
follows.

######  Corollary 5.5 (Theorem 1.3 restated).

Let $\Phi$ be a computable monotone graph property such that $\Phi$ and
$\neg\Phi$ hold on infinitely many bipartite graphs. Then
$\\#\textsc{IndSub}(\Phi)$ is $\\#\mathsf{W[1]}$-hard and cannot be solved in
time $f(k)\cdot n^{o(k)}$ for any computable function $f$ unless ETH fails.
This holds true even if the input graphs to $\\#\textsc{IndSub}(\Phi)$ are
restricted to be bipartite.

######  Proof 5.6.

If $\Phi$ is monotone and $\Phi$ and $\neg\Phi$ hold on infinitely many
bipartite graphs, then $\Phi(\mathsf{IS}_{k})=1$ for all positive integers $k$
and $\Phi(K_{t,t})=0$ for all but finitely many $t$. Hence we can apply
Theorem 5.1 and, in particular, the set $\mathcal{K}$ will contain all but
finitely many prime powers and is therefore dense.

#### Conclusion

We have established hardness for $\\#\textsc{IndSub}(\Phi)$ for _any_
(edge-)monotone property $\Phi$ that is non-trivial on bipartite graphs. In
particular, this holds true even if we count modulo a prime and restrict the
input graphs to be bipartite as well. Hence, we did not only significantly
extend the set of graph properties $\Phi$ for which the (parameterized)
complexity of $\\#\textsc{IndSub}(\Phi)$ is understood, but we also
generalized many of the prior results, such as [13], [19] and parts of [22] to
the cases of bipartite input graphs and modular counting.

As a next step towards a proof of Conjecture 1, we suggest the study of
properties that are defined by forbidden induced subgraphs, for which the
complexity of $\\#\textsc{IndSub}(\Phi)$ is only partially resolved at this
point.

## References

  * [1] Shreeram S. Abhyankar.  Lectures on algebra. Vol. I.  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2006.  doi:10.1142/9789812773449.
  * [2] Norman Biggs.  Algebraic graph theory.  Cambridge Mathematical Library. Cambridge University Press, Cambridge, second edition, 1993.  doi:10.1017/CBO9780511608704.
  * [3] Andreas Björklund, Holger Dell, and Thore Husfeldt.  The parity of set systems under random restrictions with applications to exponential time problems.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 231–242, 2015.  doi:10.1007/978-3-662-47672-7\\_19.
  * [4] Hubie Chen and Stefan Mengel.  Counting answers to existential positive queries: A complexity classification.  In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 315–326, 2016.  doi:10.1145/2902251.2902279.
  * [5] Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia.  Tight lower bounds for certain parameterized NP-hard problems.  Inf. Comput., 201(2):216–231, 2005.  doi:10.1016/j.ic.2005.05.001.
  * [6] Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia.  Strong computational lower bounds via parameterized complexity.  J. Comput. Syst. Sci., 72(8):1346–1367, 2006.  doi:10.1016/j.jcss.2006.04.007.
  * [7] Radu Curticapean.  The simple, little and slow things count: On parameterized counting complexity.  PhD thesis, Saarland University, 2015.  URL: http://scidok.sulb.uni-saarland.de/volltexte/2015/6217/.
  * [8] Radu Curticapean, Holger Dell, and Dániel 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.  doi:10.1145/3055399.3055502.
  * [9] Víctor Dalmau and Peter Jonsson.  The complexity of counting homomorphisms seen from the other side.  Theor. Comput. Sci., 329(1-3):315–323, 2004.  doi:10.1016/j.tcs.2004.08.008.
  * [10] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.  doi:10.4153/CJM-1965-045-4.
  * [11] Jörg Flum and Martin Grohe.  The Parameterized Complexity of Counting Problems.  SIAM J. Comput., 33(4):892–922, 2004.  doi:10.1137/S0097539703427203.
  * [12] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.  doi:10.1007/3-540-29953-X.
  * [13] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting connected subgraphs and graph motifs.  J. Comput. Syst. Sci., 81(4):702–716, 2015.  doi:10.1016/j.jcss.2014.11.015.
  * [14] Mark Jerrum and Kitty Meeks.  Some hard families of parameterized counting problems.  TOCT, 7(3):11:1–11:18, 2015.  doi:10.1145/2786017.
  * [15] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting even and odd induced subgraphs.  Combinatorica, 37(5):965–990, 2017.  doi:10.1007/s00493-016-3338-5.
  * [16] Jeff Kahn, Michael E. Saks, and Dean Sturtevant.  A topological approach to evasiveness.  Combinatorica, 4(4):297–306, 1984.  doi:10.1007/BF02579140.
  * [17] László Lovász.  Large Networks and Graph Limits, volume 60 of Colloquium Publications.  American Mathematical Society, 2012.  URL: http://www.ams.org/bookstore-getitem/item=COLL-60.
  * [18] Catherine McCartin.  Parameterized counting problems.  Ann. Pure Appl. Logic, 138(1-3):147–182, 2006.  doi:10.1016/j.apal.2005.06.010.
  * [19] Kitty Meeks.  The challenges of unbounded treewidth in parameterised subgraph counting problems.  Discrete Applied Mathematics, 198:170–194, 2016.  doi:10.1016/j.dam.2015.06.019.
  * [20] Carl A. Miller.  Evasiveness of graph properties and topological fixed-point theorems.  Foundations and Trends in Theoretical Computer Science, 7(4):337–415, 2013.  doi:10.1561/0400000055.
  * [21] Ronald L. Rivest and Jean Vuillemin.  On recognizing graph properties from adjacency matrices.  Theoret. Comput. Sci., 3(3):371–384, 1976/77.  doi:10.1016/0304-3975(76)90053-0.
  * [22] Marc Roth and Johannes Schmitt.  Counting induced subgraphs: A topological approach to #W[1]-hardness.  In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, pages 24:1–24:14, 2018.  doi:10.4230/LIPIcs.IPEC.2018.24.
  * [23] Seinosuke Toda.  PP is as hard as the polynomial-time hierarchy.  SIAM J. Comput., 20(5):865–877, 1991.  doi:10.1137/0220053.
  * [24] Leslie G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.  doi:10.1016/0304-3975(79)90044-6.
  * [25] Alan J. Weir.  The Sylow subgroups of the symmetric groups.  Proc. Amer. Math. Soc., 6:534–541, 1955.  doi:10.2307/2033425.
  * [26] Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu.  Finding four-node subgraphs in triangle time.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1671–1680, 2015.  doi:10.1137/1.9781611973730.111.

##  Appendix A Extension to modular counting

In this very final part of the paper, we show that our main result (Theorem
5.1) can easily be extended to counting modulo a fixed prime:

######  Theorem A.1.

Let $p$ be a prime number, let $\Phi$ be a computable graph property and let
$\mathcal{K}$ be the set of all prime powers $t=p^{k}$ such that
$\Phi(\mathsf{IS}_{2t})\neq\Phi(K_{t,t})$. If $\mathcal{K}$ is infinite then
$\mathsf{Mod}_{p}\textsc{IndSub}(\Phi)$ is $\mathsf{Mod}_{p}\mathsf{W[1]}$
hard. If additionally $\mathcal{K}$ is dense then it cannot be solved in time
$f(k)\cdot n^{o(k)}$ for any computable function $f$ unless ETH fails. This
holds true even if the input graphs to $\mathsf{Mod}_{p}\textsc{IndSub}(\Phi)$
are restricted to be bipartite.

Here $\mathsf{Mod}_{p}\textsc{IndSub}(\Phi)$ asks, given $G$ and $k$, to
compute the number of induced subgraphs with $k$ vertices in $G$ that satisfy
$\Phi$ _modulo_ $p$. The parameterized complexity class
$\mathsf{Mod}_{p}\mathsf{W[1]}$ is defined by the problem of, given $G$ and
$k$, deciding whether the number of $k$-cliques in $G$ is $0$ modulo $p$,
which is complete for the class (see [3] for $p=2$ and Chapter 1.2.2 in [7]
for the general case).

First of all, we point out that the modular counting version of Theorem 1.3
follows as corollary from the above theorem in the same way Theorem 1.3
follows from Theorem 5.1. For the proof of Theorem A.1 we rely on the
following fact stating that all required reductions in Section 4 work as well
in the case of counting modular a prime number.

######  Fact 2.

Let $p$ be a fixed prime. Then Lemma 4.11 and Lemma 4.13 remain true when
counting is done modulo $p$ if the graph $H$ is restricted to be $K_{t,t}$ for
some prime power $t=p^{k}$.

The only two non-trivial observations required to verify Fact 2 are, first,
that $\hat{\chi}(\Phi,K_{t,t})\neq 0\mod p$ whenever
$\Phi(K_{t,t}[\emptyset])\neq\Phi(K_{t,t})$ (Lemma 3.1) and, second, that
complexity monotonicity (Lemma 4.7) holds for computation modulo $p$ as well,
since non-singularity of the matrix $M$ in the proof is given by Lemma 4.5
even in case the entries of $M$ are considered to be elements of
$\mathbb{Z}_{p}$. The last ingredient for the proof of Theorem A.1, in
particular for hardness under ETH, requires a method of isolating cliques that
works in the parameterized setting. This is given by the following result of
Williams et al.

######  Lemma A.2 (Lemma 2.1 in [26]).

Let $p\geq 2$ be an integer, $G,H$ be undirected graphs. Let $G^{\prime}$ be a
random induced subgraph of $G$ such that each vertex is taken with probability
$1/2$, independently. If there is at least one induced $H$ in $G$, the number
of induced $H$ in $G^{\prime}$ is not a multiple of $p$ with probability at
least $2^{-|H|}$.

######  Proof A.3 (Proof of Theorem A.1).

The proof is most similar to the proof of the tight lower bound under ETH in
Theorem 5.1. We start our reduction from the problem of _finding_ a clique of
size $k$. In case $\mathcal{K}$ is dense and we aim to establish the ETH
hardness result, we perform the following two initial steps before the main
reduction:

  1. 1.

Given $G$ and $k$, we construct a graph $\hat{G}$ such that $G$ contains a
clique of size $k$ if and only if $\hat{G}$ contains a clique of size $\ell$
where $k\leq\ell\leq ck$ for some overall constant $c$. The details of the
construction are given in the proof of Theorem 5.1.

  2. 2.

We use Lemma A.2 to isolate an $\ell$-clique in $\hat{G}$, assuming there is
any, with high probability.

For the main part of the reduction we then first apply the reduction from
counting cliques to counting color-prescribed homomorphisms from the biclique
as given by Lemma 5.2. In particular, this reduction is parsimonious. Finally,
we proceed from this point on precisely as in the proof of Theorem 5.1, the
correctness of which follows by Fact 2.

We conclude by pointing out that, in case the randomized construction of Lemma
A.2 was used, we can perform probability amplification by repeating the final
algorithm $2^{k}$ times to end up in a constant success probability.