\section{Introduction}
We study the following subgraph counting problem: given two graphs $H$ and $G$, compute the number of copies of $H$ in $G$. For several decades this problem has received widespread attention from the theoretical community, leading to a rich algorithmic toolbox that draws from different techniques~\cite{NesetrilP85,AlonYZ95,BubleyD97,JerrumSV04} and to deep structural results in parameterised complexity theory~\cite{FlumG04,CurticapeanDM17}. Since it was discovered that subgraph counts reveal global properties of complex networks~\cite{Miloetal02,Miloetal04}, subgraph counting has also found several applications in fields such as biology~\cite{Nogaetat08,Schilleretal15} genetics~\cite{Tranetal13}, phylogeny~\cite{Kuchaievetal10}, and data mining~\cite{Babis17}.
Unfortunately, the subgraph counting problem is in general intractable, since it contains as special cases hard problems such as \textsc{Clique}. This does not mean however that the problem is \emph{always} intractable; it just means that it is tractable when the pattern $H$ is restricted to certain graph families. Identifying these families of patterns that are efficiently countable has been a key question for the last twenty years. A long stream of research eventually showed that, unless standard conjectures fail, subgraph counting is tractable only for very restricted families of patterns~\cite{FlumG04,DalmauJ04,ChenTW08,CurticapeanM14,JerrumM15,Meeks16,CurticapeanDM17,RothSW20,FockeR22}.

To circumvent this ``wall of intractability'', in this work we restrict both the family of the pattern $H$ and the family of the host $G$. Formally, given two classes of graphs $\mathcal{H}$ and $\mathcal{G}$, we study the problems $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$, defined as follows. For all of them, the input is a pair $(H,G)$ with $H\in\mathcal{H}$ and $G\in\mathcal{G}$. The outputs are respectively the number of subgraphs of $G$ isomorphic to $H$, denoted by $\#\subs{H}{G}$, the number of induced subgraphs of $G$ isomorphic to $H$, denoted by $\#\indsubs{H}{G}$, and the number of homomorphisms (edge-preserving maps) from $H$ to $G$, denoted by $\#\homs{H}{G}$.
Our goal is to determine for which $\mathcal{H}$ and $\mathcal{G}$ these three problems are tractable. To formalize what we mean by tractable, we adopt the framework of parameterized complexity~\cite{CyganFKLMPPS15}: we say that a problem is \emph{fixed-parameter tractable}, or in the class $\ccStyle{FPT}$, if it is solvable in time $f(|H|)\cdot |G|^{O(1)}$ for some computable function $f$ (see Section~\ref{sec:prelims} for a complete introduction). For instance, we consider as tractable a running time of $2^{O(|H|)} \cdot |G|$ but not one of $|G|^{O(|H|)}$. This captures the intuition that $H$ is ``small'' compared to $G$, and is the main theoretical framework for subgraph counting~\cite{FlumG04}. Thus, the goal of this work is understanding the fixed-parameter tractability of $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$ as a function of $\mathcal{H}$ and $\mathcal{G}$. Moreover, when those problems are not fixed-parameter tractable we aim to show that they are hard for the complexity class $\#\mathrm{W}[1]$, which can be thought of as the equivalent of $\mathrm{NP}$ for parameterized counting. 

We first briefly discuss which properties of $\mathcal{G}$ are worthy of attention. When $\mathcal{G}$ is the class of all graphs, it is well known that each of the three problems  is either $\ccStyle{FPT}$ or $\ccSharpW{1}$-hard depending on whether certain structural parameters of $\mathcal{H}$ (such as treewidth or vertex cover number) are bounded or not.
Thus, when $\mathcal{G}$ is the class of all graphs, the problem is solved.
However, when $\mathcal{G}$ is arbitrary, no such characterization is known. This is partly due to the fact that ``natural'' structural properties related to subgraph counting are harder to find for $\mathcal{G}$ than for $\mathcal{H}$; subgraph counting algorithms themselves usually exploit the structure of $H$ but not that of $G$ (think of tree decompositions).
There is however one deep structural property that, if held by $\mathcal{G}$, yields tractability: the property of being \emph{nowhere dense}, introduced by Ne{\v{s}}et{\v{r}}il and Ossona de Mendez~\cite{NesetrildM11}. In a nutshell $\mathcal{G}$ is nowhere dense if, for all $r \in \mathbb{N}$, its members do not contain as subgraphs $r$-subdivisions of arbitrarily large cliques; it can be shown that this generalizes several natural definitions of sparsity, including having bounded degree or bounded local treewidth, or excluding some topological minor.
In a remarkable result, Ne{\v{s}}et{\v{r}}il and Ossona de Mendez proved:\footnote{In the realm of decision problems, an even more general meta-theorem is known for first-order model-checking on nowhere dense graphs~\cite{GroheKS17}.}
\begin{theorem}[Theorem 18.9 in~\cite{Sparsity}]\label{thm:sparsity_intro}
If $\mathcal{G}$ is nowhere dense then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$, $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$, and $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ are fixed-parameter tractable and can be solved in time
$f(|H|)\cdot |V(G)|^{1+o(1)}$ for some computable function $f$.
\end{theorem}
 

\noindent Thus the case that $\mathcal{G}$ is nowhere dense is closed, and we can focus on its complement --- the case where $\mathcal{G}$ is \emph{somewhere dense}. Hence the question studied in this work is: when are $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$ fixed-parameter tractable, provided $\mathcal{G}$ is somewhere dense?



\subsection{Our Results}\label{sec:results}
We prove dichotomies for $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$ into $\ccStyle{FPT}$ and $\ccSharpW{1}$-hard cases, assuming that $\mathcal{G}$ is somewhere dense. 
It is known~\cite{RothW20} that a fully general dichotomy is   impossible even assuming that $\mathcal{G}$ is somewhere dense; thus we focus on the natural cases where $\mathcal{H}$ and/or $\mathcal{G}$ are monotone (closed under taking subgraphs) or hereditary (closed under taking induced subgraphs).
We give dichotomies which are expressed in terms of the finiteness of combinatorial parameters of $\mathcal{H}$ and $\mathcal{G}$, such as their clique number or their induced matching number.  
Existing complexity dichotomies for subgraph counting 
are based on using interpolation to evaluate linear combinations of
homomorphism counts~\cite{CurticapeanDM17}. This technique has been exploited for families of host graphs that are closed under tensorisation -- the closure is used to create new instances for the interpolation. 
The host graphs in our dichotomy theorems do not have  this closure property. Nevertheless, we obtain a dichotomy for all somewhere dense classes using a combination
of techniques involving graph fractures and colourings.
The rest of this section presents our main conceptual contribution (Section~\ref{sec:concept}), gives a detailed walk-through of our complexity dichotomies (Section~\ref{sub:subs}, Section~\ref{sub:inds}, Section~\ref{sub:homs}), and overviews the techniques behind our proofs (Section~\ref{sec:tech}). For full proofs of our claims see Section~\ref{sec:prelims} onward.

\paragraph{Basic preliminaries.} We concisely state some necessary definitions and observations which are given in more detail in Section~\ref{sec:prelims}. We denote by ${\mathcal{U}}$ the class of all graphs. We denote by $\omega(G),\alpha(G),\beta(G)$, and ${\mathrm{m}}(G)$ respectively the clique, independence, biclique, and matching number of a graph $G$. The notation extends to graph classes by taking the supremum over their elements. Induced versions of those quantities are identified by the subscript $_{\mathsf{ind}}$ (for instance, $\m_{\mathsf{ind}}$ denotes the induced matching number). $G^r$ denotes the $r$-subdivision of $G$, and $F \times G$ denotes the tensor product of $F$ and $G$.
All of our lower bounds assume the Exponential Time Hypothesis (ETH)~\cite{ImpagliazzoP01}; and most of them rule out algorithms running in time $f(k)\cdot n^{o(k/\log k)}$ for any function $f$, and are therefore tight except possibly for a $O(\log k)$ factor in the exponent.\footnote{This $O(\log k)$ gap is not an artifact of our proofs, but a consequence of the well-known open problem ``Can you beat treewidth?''~\cite{Marx10,Marx13}.} 
All of our $\#\mathrm{W}[1]$-hardness results are actually $\#\mathrm{W}[1]$-completeness results; this holds because $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$ are always in $\#\mathrm{W}[1]$ due to a characterisation of $\#\mathrm{W}[1]$ via parameterised model-counting problems (see~\cite[Chapter 14]{FlumG06}).



\subsubsection{Simpler Hardness Proofs for More Graph Families}\label{sec:concept}
Our first and most conceptual contribution is a novel approach to proving hardness of parameterized subgraph counting problems for somewhere-dense families of host graphs. This approach allows us to significantly generalize existing results while simultaneously yielding surprisingly simpler proofs.

The starting point is the observation that proving intractability results for parameterized counting problems is discouragingly difficult, as it often requires tedious and involved arguments. For instance, after Flum and Grohe conjectured that counting $k$-matchings is $\#\mathrm{W}[1]$-hard~\cite{FlumG04}, the first proof required nine years and relied on sophisticated algebraic techniques~\cite{Curticapean13}. This partially changed in 2017 when Curticapean, Dell and Marx 
showed how to express subgraph counts as linear combinations of homomorphism counts, allowing interpolation via graph tensors as a solution technique.
Using interpolation,
the computation of a linear combination $\sum_{F} a_F \cdot \#\homs{F}{G}$ is equivalent in complexity to the computation of the most difficult summand $\#\homs{F}{G}$ with a non-zero coefficient.
This principle can be used to prove intractability of generic subgraph counting problems, including of course $k$-matchings.\footnote{In the field of database theory 
a similar  technique 
expressing answers to unions of conjunctive queries
as linear combinations of answers of conjunctive queries
was independently discovered by Chen and Mengel~\cite{ChenM16}.} 
Curticapean et al.\ \cite{CurticapeanDM17} 
also showed that counts of \emph{induced} subgraphs can be expressed as linear combinations of homomorphisms. Ultimately, their work established complexity dichotomies for a variety of pattern counting problems, including both $\#\textsc{Sub}(\mathcal{H}\to {\mathcal{U}})$ and $\#\textsc{IndSub}(\mathcal{H}\to {\mathcal{U}})$ --- recall that ${\mathcal{U}}$ is the class of all graphs.
The particular interpolation technique used in~\cite{CurticapeanDM17}
applies  when the family of host graphs satisfies certain conditions. One condition is that the host class $\mathcal{G}$ is closed under tensoring, i.e., that $G \times G' \in \mathcal{G}$ for every $G\in \mathcal{G}$ and every graph $G'$.
This property is used because the interpolation relies on evaluating $\sum_F a_F\cdot \homs{F}{\hat{G}}$ for a variety of graphs~$\hat{G}$ and
these graphs~$\hat{G}$ are constructed by tensoring the original host graph $G$ with carefully chosen graphs $G_i$.
The choice is to make a certain matrix invertible, but it is important that the resulting $\hat{G}$ is in the class of host graphs so that the computation can be done. We will make this explicit using the example of counting $k$-matchings in our detailed technical overview in Section~\ref{sec:tech}.

 
Now, closedness under tensoring holds trivially when $\mathcal{G}=\mathcal{U}$.
But many other natural graph families are not closed under tensoring, including somewhere dense ones (for instance, the family of $d$-degenerate graphs for any fixed integer $d\geq 2$). 
Until now, this has been the main obstacle towards proving hardness of subgraph counting for somewhere dense graph families.
The central insight of our work is that this obstacle can be circumvented in a surprisingly simple way. Using well-established results from the theory of sparsity, we prove the following claim, which we explain in detail in Section~\ref{sec:tech}:
\begin{center}
\textit{Every monotone and somewhere dense class of graphs is closed \\under vertex-colourful tensor products of subdivided graphs.}
\end{center}
Ignoring for a moment its technicalities, this result allows us to lift the interpolation technique via graph tensors to \emph{any} monotone somewhere dense class of host graphs, including for instance the aforementioned class of $d$-degenerate graphs. In turn this yields complexity classifications for $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$, $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$ that subsume and significantly strengthen almost all classifications known in the literature (see below). Moreover, our approach yields simple and almost self-contained proofs, helping understand the underlying causes of the hardness.

 
\subsubsection{The Complexity of $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$}\label{sub:subs}
This section presents our results on the fixed-parameter tractability of $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$. We start by presenting a minimal\footnote{This means that, for every class $\mathcal{H}'$, $\#\textsc{Sub}(\mathcal{H}' \to \mathcal{G})$ is intractable if and only if the monotone closure of $\mathcal{H}'$ includes $\mathcal{H}$. The same holds for $\#\textsc{IndSub}$ with ``monotone'' replaced by ``hereditary''.} family $\mathcal{H}$ for which 
hardness holds:
the family of all $k$-matchings (or $1$-regular graphs). In this case we also denote $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ as $\#\textsc{Match}(\mathcal{G})$.
In the foundational work by Flum and Grohe~\cite{FlumG04}, $\#\textsc{Match}({\mathcal{U}})$ was identified as a central problem because of the significance of its classical counterpart (counting the number of perfect matchings); a series of works then identified $\#\textsc{Match}({\mathcal{U}})$ as the minimal intractable case~\cite{Curticapean13,CurticapeanM14,CurticapeanDM17}.
In this work, we show that $\#\textsc{Match}(\mathcal{G})$ is the minimal hard case for \emph{every} class $\mathcal{G}$ that is monotone and somewhere dense:
\begin{theorem}\label{thm:intro_match}
Let $\mathcal{G}$ be a monotone class of graphs\footnote{We emphasize that we do not need our classes to be computable or recursively enumerable. This is due to the assumed closure properties of the classes.} and assume ETH holds. Then $\#\textsc{Match}(\mathcal{G})$ is fixed-parameter tractable if and only if $\mathcal{G}$ is nowhere dense. More precisely, if $\mathcal{G}$ is nowhere dense then $\#\textsc{Match}(\mathcal{G})$ can be solved in time $f(k)\cdot|V(G)|^{1+o(1)}$ for some computable function~$f$. Otherwise $\#\textsc{Match}(\mathcal{G})$ is $\#\mathrm{W}[1]$-hard and cannot be solved in time $f(k)\cdot |G|^{o(k/\log k)}$ for any function $f$. 
\end{theorem}
\noindent Theorem~\ref{thm:intro_match} subsumes the existing intractability results for counting $k$-matchings in bipartite graphs~\cite{CurticapeanM14}, in $F$-colourable graphs~\cite{RothW20}, in bipartite graphs with one-sided degree bounds~\cite{CurticapeanDR17}, and in degenerate graphs~\cite{BressanR21}. It also strengthens the latter result: while \cite{BressanR21} establishes hardness of counting $k$-matchings in $\ell$-degenerate graphs for $k+\ell$ as a parameter, Theorem~\ref{thm:intro_match} yields hardness for $d$-degenerate graphs for every fixed $d\geq 2$.\footnote{The class of all $d$-degenerate graphs is somewhere dense for all $d \ge 2$.}
Additionally, we show that Theorem~\ref{thm:intro_match} cannot be strengthened to achieve polynomial-time tractability of $\#\textsc{Match}(\mathcal{G})$ for nowhere dense and monotone $\mathcal{G}$, unless $\#\ccStyle{P}=\ccStyle{P}$.

As a first consequence of Theorem~\ref{thm:intro_match}, we obtain the following complete classification of the fixed-parameter tractability of $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ when $\mathcal{H}$ is monotone.
\begin{theorem}\label{thm:subs_monotone_intro}
Let $\mathcal{H}$ and $\mathcal{G}$ be monotone graph classes and assume ETH holds. Then $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is fixed-parameter tractable if ${\mathrm{m}}(\mathcal{H}) < \infty$ or $\mathcal{G}$ is nowhere dense. Otherwise $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is $\#\mathrm{W}[1]$-complete and cannot be solved in time $f(|V(H)|)\cdot |G|^{o(|V(H)|/ \log(|V(H)|))}$ for any function $f$.
\end{theorem}
As a second consequence of Theorem~\ref{thm:intro_match}, when $\mathcal{H}$ is hereditary we obtain the classification shown in Table~\ref{tab:resultsSubsHereditary_intro}.
The unique fixed-parameter tractability result in the table is a ``real'' $\ccStyle{FPT}$ case: we can show that, unless $\mathrm{P}=\#\mathrm{P}$, it is in $\ccStyle{FPT}$ but not in $\ccStyle{P}$.
\begin{theorem}\label{thm:subs_hereditary_intro}
Let $\mathcal{H}$ and $\mathcal{G}$ be graph classes such that $\mathcal{H}$ is hereditary and $\mathcal{G}$ is monotone. Then the complexity of $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is exhaustively classified by Table~\ref{tab:resultsSubsHereditary_intro}.
\end{theorem}

\begin{table}[ht]
    \begin{tabularx}{\textwidth}{lllll}
        \toprule
        \begin{tabular}{@{}l}
             $~$
        \end{tabular}&\begin{tabular}{@{}l}
             $\mathcal{G}$
             n.\ dense
        \end{tabular} &\begin{tabular}{@{}l}
             $\mathcal{G}$
             s.\ dense\\
             $\omega(\mathcal{G})=\infty$
        \end{tabular}& \begin{tabular}{@{}l}
             $\mathcal{G}$
             s.\ dense\\
        $\omega(\mathcal{G})<\infty$\\  
            ${\beta}(\mathcal{G})=\infty$
        \end{tabular}&\begin{tabular}{@{}l}
             $\mathcal{G}$
             s.\ dense\\
             $\omega(\mathcal{G})<\infty$\\ 
             ${\beta}(\mathcal{G})<\infty$
        \end{tabular}\\%[25pt]
        \cmidrule(r{2ex}){2-5}
        \begin{tabular}{l}
             ${\mathrm{m}}(\mathcal{H})<\infty$
        \end{tabular} & P & P & P & P \\[8pt]
        \begin{tabular}{l}
             $\m_{\mathsf{ind}}(\mathcal{H})= \infty$
        \end{tabular} & FPT & hard & hard & hard
        \\[8pt]
        \begin{tabular}{l}
            $\m_{\mathsf{ind}}(\mathcal{H})<\infty$,
            $\beta_{\mathsf{ind}}(\mathcal{H})= \infty$
        \end{tabular} & P & hard$^\dagger$ & hard$^\dagger$ & P \\[8pt]
        \begin{tabular}{l}
         Otherwise 
         ~~~
        \end{tabular} & P & hard$^\dagger$ & P & P 
        \\\bottomrule
        \end{tabularx}
     \caption[caption]{\small The complexity of $\#\textsc{Sub}(\mathcal{H}\to \mathcal{G})$ for hereditary $\mathcal{H}$ and monotone $\mathcal{G}$. Here ``hard'' means $\#\mathrm{W}[1]$-hard and, unless ETH fails, without an algorithm running in time $f(|H|)\cdot |G|^{o(|V(H)|/ \log |V(H)|)}$; ``hard$^\dagger$'' means the same, but without an algorithm running in $f(|H|)\cdot |G|^{o(|V(H)|)}$.}
      \label{tab:resultsSubsHereditary_intro}
\end{table}
\textbf{Remark.} We observe that Table~\ref{tab:resultsSubsHereditary_intro} (and the proofs of its bounds) suggest the existence of three general algorithmic strategies for subgraph counting:
\begin{enumerate}
    \item If $\mathcal{G}$ is nowhere dense (first column of Table~\ref{tab:resultsSubsHereditary_intro}), then one can use the FPT algorithm of Theorem~\ref{thm:sparsity_intro}, based on Gaifman's locality theorem for first-order formulas and the local sparsity of nowhere dense graphs (see~\cite{Sparsity}).
    \item If ${\mathrm{m}}(\mathcal{H})< \infty$ (first row of Table~\ref{tab:resultsSubsHereditary_intro}), then one can use the polynomial-time algorithm of Curticapean and Marx~\cite{CurticapeanM14}, based on guessing the image of a maximum matching of $H$ and counting its extensions via dynamic programming.
\item All remaining entries marked as ``P'' are shown to be essentially trivial. Concretely, we will rely on Ramsey's theorem to prove that minor modifications of the naive brute-force approach yield polynomial-time algorithms for those cases.
\end{enumerate}

\subsubsection{The Complexity of $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$}\label{sub:inds}
In the previous section we proved that, when $\mathcal{G}$ is somewhere dense, $k$-matchings are the minimal hard family of patterns for $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$. In this section we show that $k$-independent sets play a similar role for $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$. Let $\#\textsc{IndSet}(\mathcal{G})=\#\textsc{IndSub}(\mathcal{I} \to \mathcal{G})$ where $\mathcal{I}$ is the set of all all independents sets (or $0$-regular graphs). We prove:
\begin{theorem}\label{thm:intro_is}
Let $\mathcal{G}$ be a monotone class of graphs and assume ETH holds. Then $\#\textsc{IndSet}(\mathcal{G})$ is fixed-parameter tractable if and only if $\mathcal{G}$ is nowhere dense. More precisely, if $\mathcal{G}$ is nowhere dense, then $\#\textsc{IndSet}(\mathcal{G})$ can be solved in time $f(k)\cdot|V(G)|^{1+o(1)}$ for some computable function~$f$. Otherwise, there is no function $f$ for which $\#\textsc{IndSet}(\mathcal{G})$ can be solved in time $f(k)\cdot |G|^{o(k/\log k)}$. 
\end{theorem}
This result subsumes the intractability result for counting $k$-independent sets in bipartite graphs of~\cite{CurticapeanDFGL19}. It also strengthens the result of~\cite{BressanR21}, which shows $\#\textsc{IndSet}(\mathcal{G})$ is hard when parameterized by $k+d$ where $d$ is the degeneracy of $G$. More precisely, \cite{BressanR21} does not imply that $\#\textsc{IndSet}(\mathcal{G})$ is hard for $\mathcal{G}$ being the class of $d$-degenerate graphs, for any $d \ge 2$;  Theorem~\ref{thm:intro_is} instead proves such hardness for \emph{every} $d \geq 2$. Finally, we point out that the $\ccStyle{FPT}$ case of Theorem~\ref{thm:intro_is} is not in $\ccStyle{P}$ unless $\mathrm{P}=\#\mathrm{P}$.

As consequence of Theorem~\ref{thm:intro_is}, when $\mathcal{H}$ is hereditary (and thus in particular when $\mathcal{H}$ is monotone) we obtain:

\begin{theorem}\label{thm:indsubs_hereditary_intro}
Let $\mathcal{H}$ and $\mathcal{G}$ be classes of graphs such that $\mathcal{H}$ is hereditary and $\mathcal{G}$ is monotone. Then the complexity of $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ is exhaustively classified by Table~\ref{tab:resultsIndSubsHereditary_intro}.
\end{theorem}
\begin{table}[ht]\centering
    \begin{tabularx}{.65\textwidth}{llll}
        \toprule
        \begin{tabular}{@{}l}
             $~$
        \end{tabular}&\begin{tabular}{@{}l}
             $\mathcal{G}$
             n.\ dense
        \end{tabular} &\begin{tabular}{@{}l}
             $\mathcal{G}$
             s.\ dense\\
             $\omega(\mathcal{G})=\infty$
        \end{tabular}& \begin{tabular}{@{}l}
             $\mathcal{G}$
             s.\ dense\\
        $\omega(\mathcal{G})<\infty$\\  
            ${\alpha}(\mathcal{G})=\infty$
        \end{tabular}\\
        \cmidrule(r{2ex}){2-4}
        \begin{tabular}{l}
             $|\mathcal{H}| < \infty$
        \end{tabular} & P & P & P \\[8pt]
        \begin{tabular}{l}
             $\alpha(\mathcal{H})= \infty$
        \end{tabular} & FPT &  hard$^\dagger$ & hard
        \\[8pt]
        \begin{tabular}{l}
           Otherwise 
            ~~
        \end{tabular} & P & hard$^\dagger$ & P\\
        \bottomrule
        \end{tabularx}
     \caption[caption]{\small The complexity of $\#\textsc{IndSub}(\mathcal{H}\to \mathcal{G})$ for hereditary $\mathcal{H}$ and monotone $\mathcal{G}$. Here ``hard'' means $\#\mathrm{W}[1]$-hard and, unless ETH fails, without an algorithm running in time $f(|H|)\cdot |G|^{o(|V(H)|/ \log |V(H)|)}$; ``hard$^\dagger$'' means the same, but without an algorithm running in $f(|H|)\cdot |G|^{o(|V(H)|)}$.}
      \label{tab:resultsIndSubsHereditary_intro}
\end{table}

\subsubsection{The Complexity of $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$}\label{sub:homs}
Finally, we study the parameterized complexity of $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$. We denote by $\mathsf{tw}(H)$ the treewidth of a graph $H$. Informally, graphs of small treewidth admit a decomposition in small separators that allow for efficient dynamic programming. In this work we use treewidth in a purely black-box fashion (e.g.\ via excluded-grid theorems); for its formal definition  see~\cite[Chapter 7]{CyganFKLMPPS15}. We prove the following result, whose novel part is in point (3):
 

\vbox{
\begin{theorem}\label{thm:main_homs_intro}
Let $\mathcal{H}$ and $\mathcal{G}$ be monotone classes of graphs. 
\begin{enumerate}
    \item If $\mathcal{G}$ is nowhere dense then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G}) \in \ccStyle{FPT}$ and can be solved in time $f(|H|)\cdot |V(G)|^{1+o(1)}$ for some computable function $f$.
    \item If $\mathsf{tw}(\mathcal{H})< \infty$ then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G}) \in \ccStyle{P}$, and if a tree decomposition of $H$ of width $t$ is given, then it can be solved in time $|H|^{O(1)}\cdot |V(G)|^{t+1}$. 
    \item If $\mathcal{G}$ is somewhere dense and $\mathsf{tw}(\mathcal{H})=\infty$ then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ is $\#\mathrm{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(|H|)\cdot |G|^{o(\mathsf{tw}(H))}$ for any function $f$.
\end{enumerate}
\end{theorem}}

Unfortunately, in contrast to $\#\textsc{Sub}$ and $\#\textsc{IndSub}$, we do not know how to extend Theorem~\ref{thm:main_homs_intro} to hereditary $\mathcal{H}$. We point out however that for hereditary $\mathcal{H}$ the finiteness of $\mathsf{tw}(\mathcal{H})$ cannot be the correct criterion: if $\mathcal{H}$ is the set of all complete graphs and $\mathcal{G}$ is the set of all bipartite graphs, then $\mathcal{H}$ is hereditary and $\mathsf{tw}(\mathcal{H})=\infty$, but $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ is easy since $|V(H)|\le 2$ or $\#\homs{H}{G}=0$.

More generally, the complexity of $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ appears to be far from completely understood for arbitrary classes $\mathcal{H}$. In fact, it has been recently posed as an open problem even for specific monotone and somewhere dense $\mathcal{G}$ such as the family of $d$-degenerate graphs~\cite{BressanR21,BeraGLSS22}. There is some evidence that the finiteness of induced grid minors is the right criterion for tractability; some evidence for this conjecture was given in~\cite{BressanR21}.

In what follows, we provide a detailed exposition of our proof techniques, which we start by a brief summary of the state of the art.

\subsection{Context: Counting Subgraphs via Interpolation and Graph Tensors}\label{sec:context}
In general, the method of interpolation as a reduction technique for counting problems dates back to the foundational works of Valiant~\cite{Valiant79b}.
If one aims to apply interpolation in a reduction, the main technical work is to prove that a related system of linear equations has a unique solution. For example, in the special case of polynomial interpolation,\footnote{That is, one is given an oracle to a univariate polynomial, and the goal is to compute its coefficients.} the corresponding matrix is a Vandermonde matrix and thus non-singular. 
In our specific case of linear combinations of homomorphism counts from small pattern graphs to large host graphs, the existence of an interpolation technique based on graph tensoring follows implicitly by works of Lov{\'{a}}sz (see e.g.\ \cite[Chapters 5 and 6]{Lovasz12}). It was then discovered by Curticapean et al.\ in~\cite{CurticapeanDM17} that 
subgraph counts and induced subgraph counts may be expressed as linear combinations of homomorphism counts.
Using this description,
they showed that the reduction technique of interpolation
via graph tensoring applies to a wide variety of  parameterised pattern counting problems. Concretely, their results established improved upper and lower bounds for subgraph and induced subgraph counting including, among others, complete parameterised complexity dichotomies for $\#\textsc{Sub}(\mathcal{H} \to {\mathcal{U}})$ and $\#\textsc{IndSub}(\mathcal{H}\to {\mathcal{U}})$.


\subsection{Overview of Our Techniques}\label{sec:tech}
The present section expands upon Section~\ref{sec:concept} and gives a detailed technical overview of our proofs of hardness. 
Those proofs contain virtually all the effort in characterizing the parameterized complexity of $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$, since the complexity of the tractable cases follows mostly from the running time of existing algorithms. 

We start by analysing a simple case. Recall that a graph family $\mathcal{G}$ is somewhere dense if, for some $r \in \mathbb{N}$, for all $k\in \mathbb{N}$, 
there is a $G\in \mathcal{G}$ such that
the $r$-subdivision $K_k^r$ of $K_k$ is a subgraph of~$G$.   From this characterization it is immediate that, if $\mathcal{G}$ is somewhere dense \emph{and monotone}, then it contains  the $r$-subdivisions of every graph. In turn, this implies that detecting subdivisions of cliques in $\mathcal{G}$ is at least as hard as the parameterised clique problem~\cite{DvorakKT13}.
Since the parameterised clique problem is $\ccW{1}$-hard, we deduce that $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is intractable when $\mathcal{H}=\{K_k^r : k,r \in \mathbb{N}\}$ and $\mathcal{G}$ is monotone and somewhere dense. Hence for this choice of $\mathcal{H}$, the monotonicity and somewhere-density of $\mathcal{G}$ yield hardness pretty easily.

It is unclear how to extend this approach to arbitrary $\mathcal{H}$, since the elements of $\mathcal{H}$ are not necessarily $r$-subdivisions of graphs that are hard to count in arbitrary host graphs. In what follows we will 
use the example where $\mathcal{G}$ is the class of $k$-matchings
to illustrate our proof strategy.
The class of $k$-matchings is defined as  $\mathcal{M} = \{M_k : k \in \mathbb{N}\}$. This example will introduce  the key ingredients of our proof and will serve as a base case for the proof itself. In order to give a self-contained technical overview, we first outline the hardness proof of $\#\textsc{Sub}(\mathcal{M} \to {\mathcal{U}})$ using the interpolation technique discussed in Section~\ref{sec:context}; recall that ${\mathcal{U}}$ is the class of all graphs.
From~\cite{CurticapeanDM17}, we know that for every $k \in \mathbb{N}$ there is a function $a_k : {\mathcal{U}} \to \mathbb{Q}$ with finite support such that, for every $G \in {\mathcal{U}}$,
\begin{equation}\label{eq:intro_hombasis}
    \#\subs{M_k}{G} = \sum_H a_k(H) \cdot \#\homs{H}{G}
\end{equation}
where the sum is over all isomorphism classes of all graphs. By a classic result of Dalmau and Jonsson~\cite{DalmauJ04}, computing $\#\homs{H}{G}$ is not fixed-parameter tractable for $H$ of unbounded treewidth, unless ETH fails. Hence, if we could prove that an FPT algorithm for computing $\#\subs{M_k}{G}$ yields an FPT algorithm for computing $\#\homs{H}{G}$ for some $H$ whose treewidth grows with $k$, we would conclude that computing $\#\subs{M_k}{G}$ is not fixed-parameter tractable unless ETH fails. 
This is what~\cite{CurticapeanDM17} indeed prove.
The idea is to apply~\eqref{eq:intro_hombasis} not to $G$ itself, but to several carefully chosen host graphs
$\hat{G}$ such that $\#\homs{H}{\hat{G}}$ tells us $\#\homs{H}{G}$. Several graphs~$\hat{G}$ are used in order to obtain a large linear system whose unknowns are all the terms $\#\homs{H}{\hat{G}}$ such that $a_k \ne 0$. 
There are only finitely many such terms
since $a_k$ has finite support; hence, if the system has sufficiently many equations, then we may be able to solve it (using an oracle for the calls to $\#\subs{M_k}{\hat{G}}$) and retrieve all those terms. If among them is some $H$ of high treewidth, then we are done.

To construct the linear system, one uses the well-known fact that for all graphs $H, G, G'$:
\begin{equation}\label{eq:intro_tensor_linear}
\#\homs{H}{G\times G'} = \#\homs{H}{G}\cdot \#\homs{H}{G'}.
\end{equation}
Now let $\ell$ be the size of the support of $a_k$ and let $\{G_i\}_{i=1,\ldots,\ell}$ be a set of graphs, each one of size $f(|H|)$. For each $i$ in FPT time we can compute $\#\homs{H}{G_i}$. Equations~\eqref{eq:intro_hombasis}
and~\eqref{eq:intro_tensor_linear}  then yield
\begin{align}\label{eq:intro_hombasis_tensor}
    \#\subs{M_k}{G\times G_i} &=
    \sum_{H} a_{k}(H) \cdot \#\homs{H}{G_i} \cdot \#\homs{H}{G} = \sum_{\substack{H\\a_k(H)\neq 0}} b^i_H \cdot X_H\,,
\end{align}
where $b^i_H := \#\homs{H}{G_i}$ and $X_H:=a_{k}(H) \cdot \#\homs{H}{G}$.

Applied to all $i$, this yields the desired system of $\ell$ linear equations. Now, by applying classical results due to Lov{\'{a}}sz (see e.g.\ \cite[Chapter 5]{Lovasz12}), Curticapean et al.\ \cite{CurticapeanDM17} showed that there always exists a choice of the $G_i$'s such that the system has a unique solution. Therefore, if one can compute $\#\subs{M_k}{G\times G_i}$ in FPT time for all $i$, then one can compute $\#\homs{H}{G}$ in FPT time for all $H$ with $a_{k}(H) \ne 0$. In particular, one can compute $\#\homs{F_k}{G}$ where $F_k$ is any $k$-edge graph of maximal treewidth, since~\cite{CurticapeanDM17} also showed that $a_{k}(H) \ne 0$ for all $H$ with $|E(H)| \le k$.
This gives a parameterized reduction from $\#\textsc{Hom}(\mathcal{F} \to {\mathcal{U}})$ to $\#\textsc{Sub}(\mathcal{M} \to {\mathcal{U}})$, where $\mathcal{F}$ is the class of all maximal-treewidth graphs $F_k$. Since $\#\textsc{Hom}(\mathcal{F} \to {\mathcal{U}})$ is hard by~\cite{DalmauJ04}, the reduction establishes hardness of $\#\textsc{Sub}(\mathcal{M} \to {\mathcal{U}})$ as desired.

Our main question is whether this strategy can be extended from $\mathcal{U}$ to any monotone somehere dense class $\mathcal{G}$. This it not obvious, since the argument above relies on two crucial ingredients that may be lost when moving from $\mathcal{U}$ to $\mathcal{G}$:
\begin{enumerate}
    \item[(I.1)] We need to find a family of graphs $\hat{\mathcal{F}}= \{ \hat{F}_k~|~k\in \mathbb{N}\}$ such that $\#\textsc{Hom}(\hat{\mathcal{F}} \to \mathcal{G})$ is hard
    and, for all $k\in \mathbb{N}$,
    $a_k(\hat{F}_k) \neq 0$. 
    \item[(I.2)] We need to find graphs $G_i$ such that $G \times G_i \in \mathcal{G}$. This is necessary since the argument performs a reduction to the problem of counting $\#\subs{M_k}{G\times G_i}$, and is not straightforward
    since $G\times G_i$ may not be in $\mathcal{G}$ even when both $G,G_i$ are.
\end{enumerate}
It turns out that both requirements can be satisfied in a systematic way.
First, we study each one of our problems, $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$, in some carefully chosen vertex-coloured and edge-coloured version. It is well-known that 
the coloured versions of these counting problems are equivalent in complexity (in the FPT sense) to the uncoloured versions, so to make progress, we may consider the coloured versions. Next, coloured graphs come with a canonical coloured version of the tensor product which satisfies (\ref{eq:intro_tensor_linear}), so we can 
hope to apply interpolation via tensor products.  The introduction of colours in the analysis of 
parameterised problems is a common tool for streamlining reductions that are otherwise unnecessarily complicated (see e.g.\ \cite{CurticapeanM14,RothSW21Icalp,DorflerRSW22,FockeR22}). The technical details of the coloured versions are not hard, but cumbersome to state, hence we defer them to Section~\ref{sec:prelims}. 
We will not need the exact definitions to
give   a high-level explanation of how we achieve (I.1) and (I.2) for these coloured versions. These are achieved as follows.

For (I.1), we choose as $\hat{\mathcal{F}}$ the class of all $r$-subdivisions of a family $\mathcal{E}$ of regular expander graphs. A simple construction then allows us to reduce $\#\textsc{Hom}(\mathcal{E} \to {\mathcal{U}})$, which is known to be hard, to $\#\textsc{Hom}(\hat{\mathcal{F}}\to {\mathcal{U}}^r)$, where ${\mathcal{U}}^r$ is the set of all $r$-subdivisions of graphs. As noted above ${\mathcal{U}}^r \subseteq \mathcal{G}$, hence 
$\#\textsc{Hom}(\hat{\mathcal{F}} \to \mathcal{G})$ is hard.
We will show in the coloured version that for each graph $F_k \in \hat{\mathcal{F}}$ with $k$ edges, $a_k(F_k)\neq 0$ (see the proof of Lemma~\ref{lem:main_colmatch}). Thus, (I.1) is satisfied. 







For (I.2) we construct, for each $k$, a (finite) sequence of coloured graphs $G_1, G_2,\dots$ satisfying the following two conditions: the system of linear equations given by (the coloured version of)~\eqref{eq:intro_hombasis_tensor} has a unique solution, and the coloured tensor product between each $G_i$ and any coloured graph in ${\mathcal{U}}^r$ is in $\mathcal{G}$. Concretely, we choose as $G_i$ the so-called \emph{fractured graphs} of the $r$-subdivisions of the expanders in $\mathcal{E}$. Fractured graphs are obtained by a splitting operation on a graph and come with a natural vertex colouring. They have been introduced in recent work on classifying subgraph counting problems~\cite{RothSW21Icalp} and we provide a detailed introduction in Section~\ref{sec:prelims_fractures}.

Together, our resolutions of (I.1) and (I.2) yield a colourful version of the framework of~\cite{CurticapeanDM17} that applies to \emph{any monotone somewhere dense class of host graphs}. In the case of counting $k$-matchings we obtain as a consequence that  $\#\textsc{Hom}(\mathcal{E} \to {\mathcal{U}})$, i.e., the problem of counting homomorphisms from expanders in $\mathcal{E}$ to arbitrary hosts graphs, reduces to $\#\textsc{Sub}(\mathcal{M} \to \mathcal{G})$, i.e., counting $k$-matchings of graphs in $\mathcal{G}$, whenever $\mathcal{G}$ is monotone and somewhere dense. Since $\#\textsc{Hom}(\mathcal{E} \to {\mathcal{U}})$ is intractable, this proves the hardness of $\#\textsc{Sub}(\mathcal{M} \to \mathcal{G})$ for all monotone and somewhere dense $\mathcal{G}$, as desired. From this result, we will then be able to prove our more general classifications for $\#\textsc{Sub}(\mathcal{H}\to \mathcal{G})$ (see Theorems~\ref{thm:subs_monotone_intro} and~\ref{thm:subs_hereditary_intro}).

For counting small \emph{induced} subgraphs, i.e., for $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$, we will rely on a different transformation. However, identifying the problem of counting $k$-independent sets as a minimal case similar to $\#\textsc{Match}(\mathcal{G})$ above, the proof technique will be similar to the case of $\#\textsc{Sub}(\mathcal{H}\to \mathcal{G})$. For our classification of $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$, we will rely on a different approach, described in the next section.

\subsubsection{Classifying Homomorphism Counting via Wall-Minors}
The proof of our dichotomy for $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ for monotone $\mathcal{H}$ and $\mathcal{G}$ (see Theorem~\ref{thm:main_homs_intro}) requires us to establish hardness given that $\mathcal{G}$ is somewhere dense and $\mathcal{H}$ has unbounded treewidth. Recall that our solution of (I.1) relied on a reduction from (the coloured version of) $\#\textsc{Hom}(\mathcal{E}\to {\mathcal{U}})$ to (the coloured version of) $\#\textsc{Hom}(\hat{\mathcal{F}} \to {\mathcal{U}}^r)$, where $\mathcal{E}$ is a family of regular expander graphs, and $\hat{\mathcal{F}}$ is the class of all $r$-subdivisions of graphs in $\mathcal{E}$, and ${\mathcal{U}}^r$ is the class of $r$-subdivisions of all graphs. Since for all monotone somewhere dense classes $\mathcal{G}$ there is an $r$ such that ${\mathcal{U}}^r\subseteq \mathcal{G}$, we would be done if we could make sure that every monotone class of graphs of unbounded treewidth $\mathcal{H}$ contains $\hat{\mathcal{F}}$ as a subset. Unfortunately, this is not the case. As a trivial example, $\mathcal{H}$ could be the class of all graphs of degree at most $3$ while $\mathcal{E}$ is a family of $4$-regular expanders. Straightforward weakenings of this condition also fail.

 
To circumvent this problem, we use a result of Thomassen~\cite{Thomassen88} to prove that, for every positive integer $r$ and every monotone class of graphs $\mathcal{H}$ with unbounded treewidth, the following is true:  For each \emph{wall} $W_{k,k}$, the class $\mathcal{H}$ contains a subdivision of $W_{k,k}$ in which each edge is subdivided a positive multiple of $r$ times. Now, the crucial property of the class of all walls $\mathcal{W}:=\{W_{k,k}~|~k\in \mathbb{N}\}$ is that $\#\textsc{Hom}(\mathcal{W}\to \mathcal{U})$ is intractable by the classification of Dalmau and Jonsson~\cite{DalmauJ04}. Refining our constructions based on subdivided graphs, we are then able to show that $\#\textsc{Hom}(\mathcal{W}\to \mathcal{U})$ reduces to $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$ whenever $\mathcal{H}$ is monotone and of unbounded treewidth, and $\mathcal{G}$ is monotone and somewhere dense. Theorem~\ref{thm:main_homs_intro} will then follow as a direct consequence.
 




\section{Preliminaries}\label{sec:prelims}
We denote the set of non-negative integers with $\mathbb{N}_0$, and the set of positive integers by $\mathbb{N}$.
Graphs in this work are undirected and without self-loops unless stated otherwise. A \emph{subdivision} of a graph $G$ is obtained by subdividing each edge of $G$ arbitrarily often. Given a non-negative integer $r$ and a graph $G$, we write $G^r$ for the $r$-\emph{subdivision} of $G$, i.e., the graph obtained from $G$ by subdividing each edge   $r$ times (so that it becomes a path of $r+1$ edges). Note that $G^0=G$. (The graph~$G^{r-1}$ is also called the ``$r$-stretch of~$G$'' in the literature).   Given a graph $G$ and a vertex $v\in V(G)$, we write $E_G(v):= \{e\in E(G)~|~v\in e \}$ for the set of edges incident to $v$. Furthermore, given a subset of edges $A\subseteq E(G)$, we write $G[A]$ for the 
graph~$(V(G),A)$.
Given a subset of vertices $S\subseteq V(G)$, we write $G[S]$ for the subgraph of $G$ induced by the vertices in $S$, that is, 
$G[S] := (S, \{e\in E(G)~|~e \subseteq S \})$. An ``induced subgraph'' of~$G$ is a subgraph induced by some $S\subseteq V(G)$.



A \emph{homomorphism} from a graph $H$ to a graph $G$ is a mapping $\varphi:V(H)\to V(G)$ which is edge-preserving, that is, $\{u,v\}\in E(H)$ implies $\{\varphi(u),\varphi(v)\}\in E(G)$. 
Given graphs $H$ and $G$, we write
\begin{itemize}
\item $\homs{H}{G}$ for the set of all homomorphisms from $H$ to $G$,
\item $\surhoms{H}{G}$ for the set of all homomorphims
from~$H$ to~$G$ that surjective on~$V(G)$,
\item $\subs{H}{G}$ for the set of all subgraphs of $G$ isomorphic to $H$, and
\item $\indsubs{H}{G}$ for the set of all induced subgraphs of $G$ isomorphic to $H$.
\end{itemize}

 


\subsection{Coloured Graphs and Fractures}\label{sec:prelims_fractures}
Let $H$ be a graph. 
It is common to refer to an element of $\homs{G}{H}$ as an 
``$H$-colouring of~$G$''. 
We therefore refer to an element of $\surhoms{G}{H}$ as a ``surjective $H$-colouring of~$G$''
An $H$-\emph{coloured graph} is a pair $(G,c)$ where $G$ is a graph and $c\in \homs{G}{H}$.
A ``surjectively $H$-coloured graph'' is a pair $(G,c)$ where $G$ is a graph and $c\in \surhoms{G}{H}$.





 

Given two $H$-coloured graphs $(F,c_F)$ and $(G,c_G)$, a homomorphism from $(F,c_F)$ to $(G,c_G)$ is a mapping $\varphi\in\homs{F}{G}$ such that
$c_G(\varphi(v))=c_F(v)$ for each $v\in V(F)$.\footnote{We remark that in previous works~\cite{RothSW21Icalp,PeyerimhoffRSSV21}, homomorphisms between $H$-coloured graphs are called ``colour-preserving'' or, if $F=H$, ``colour-prescribed''. Since we will work almost exclusively in the coloured setting in this work, we will just speak of homomorphisms and always provide the $H$-colourings explicitly in our notation.} We write $\homs{(F,c_F)}{(G,c_G)}$ for the set of all homomorphisms from $(F,c_F)$ to $(G,c_G)$.

Following the terminology of~\cite{RothSW21Icalp,PeyerimhoffRSSV21}, we define a fracture of a graph $H$ as a $|V(H)|$-tuple $\rho=(\rho_v)_{v\in V(H)}$ where $\rho_v$ is a partition of the set $E_v(H)$ of edges of $H$ incident to $v$. Now, given a fracture $\rho$ of $H$, we obtain the \emph{fractured graph} $\fracture{H}{\rho}$ from $H$ by splitting each vertex $v$ according to the partition $\rho_v$. Formally, the graph $\fracture{H}{\rho}$ contains a vertex $v^B$ for each vertex $v\in V(H)$ and block $B \in \rho_v$, and we make $v^B$ and $u^{B'}$ adjacent if and only if $\{v,u\}\in E(H)$ and $\{u,v\} \in B \cap B'$. An illustration is provided in Figure~\ref{fig:fracture}.

\begin{figure}[t]
    \centering
    \begin{tikzpicture}[scale=1.5]
        \node[vertex,inner sep=.4ex,label={[label distance=.03]below:\(v\)}] (m) at (0, 0) {};

        \draw[very thick,red] (m) -- ++(135:1);
        
        \draw[very thick,green!80!blue] (m) -- ++(180:1);
        
        \draw[very thick,blue] (m) -- ++(-135:1);


        \draw[very thick,yellow!50!orange] (m) -- ++(45:1);
        
        \draw[very thick] (m) -- ++(0:1);
        
        \draw[very thick,cyan] (m) -- ++(-45:1);
        

        \begin{scope}[shift={(5,0)}]
            
            \begin{scope}[scale=2.4]
                \kowaen{0,0}{-90/90/white,90/270/white}{1};
            \end{scope}


            \node[label={[label distance=.03]below:\(v^{B_1}\)}]  at (1-2) {};

            \draw[very thick,red] (1-2) -- ++(135:1);
            
            \draw[very thick,green!80!blue] (1-2) -- ++(180:1);
            
            \draw[very thick,blue] (1-2) -- ++(-135:1);

            \node[label={[label distance=.03]below:\(v^{B_2}\)}]  at
                (1-1) {};

            \draw[very thick,yellow!50!orange] (1-1) -- ++(45:1);
            
            \draw[very thick] (1-1) -- ++(0:1);
            
            \draw[very thick,cyan] (1-1) -- ++(-45:1);


            \begin{scope}[scale=1.8]
                \kowaen{0,0}{-90/90/black,90/270/black}{1};
            \end{scope}

        \end{scope}
    \end{tikzpicture}
    \caption{\label{fig:fracture} A fractured graph $\fracture{Q}{\sigma}$ from~\cite{PeyerimhoffRSSV21}. Left: a vertex $v \in V(Q)$ with incident edges $E_Q(v)=\{
        \redc{2pt},\greenc{2pt},\bluec{2pt},\yellowc{2pt},\blackc{2pt},\brownc{2pt}\}$. Right: the splitting of $v$ in $\fracture{Q}{\sigma}$ for a fracture $\sigma$ where the partition $\sigma_v$ of $E_Q(v)$ consists of the two blocks $B_1 =\{ \redc{2pt},\greenc{2pt},\bluec{2pt}\}$, and $B_2=\{\yellowc{2pt},\blackc{2pt},\brownc{2pt}\}$.}
\end{figure}

The following $H$-colouring of a fractured graph is used implicitly in~\cite{RothSW21Icalp,PeyerimhoffRSSV21}. We decided to give the definition explicitly for the sake of readability.
\begin{definition}\label{def:canonical_col}
Let $H$ be a graph and let $\rho$ be a fracture of $H$. We denote by $c_\rho:V(\fracture{H}{\rho}) \to V(H)$ the function that maps $v^B$ to $v$ for each $v\in V(H)$ and $B\in \rho_v$.
\end{definition}
\begin{observation}\label{obs:canonical_col}
For each $H$ and $\rho$,   $c_\rho$ is an $H$-colouring of the fractured graph $\fracture{H}{\rho}$.
\end{observation}


\subsection{Graph Classes, Invariants and Minors}
We use symbols $\mathcal{F},\mathcal{G},\mathcal{H}$ to denote classes of graphs and we set ${\mathcal{U}}$ to be the class of \emph{all} graphs. A graph invariant $g$ is a function from the set of all graphs to $\mathbb{N}$ such that $g(G)=g(H)$ whenever $G$ and $H$ are isomorphic. A graph invariant $g$ is \emph{bounded} on a graph family $\mathcal{H}$, and we write $g(\mathcal H)<\infty$, if there is a constant $B$ such that $g(H)\leq B$ for each $H\in \mathcal{H}$. Otherwise we say that $g$ is unbounded on $\mathcal{H}$ and write $g(\mathcal H)=\infty$. The following invariants arise in our complexity classifications:

\begin{definition}[Graph Invariants]\label{def:invariants}
Let $G$ be a graph. We write
\begin{itemize}
    \item $\alpha(G)$ for the independence number of $G$, that is, for the size of a maximum independent set.
    \item $\omega(G)$ for the clique number of $G$, that is, for the size of a maximum complete subgraph.
    \item $\beta(G)$ for the maximum $k$ such that $G$ contains a $k$-by-$k$ biclique as a subgraph.
    \item $\beta_{\mathsf{ind}}(G)$ for the maximum $k$ such that $G$ contains a $k$-by-$k$ biclique as an induced subgraph.
    \item ${\mathrm{m}}(G)$ for the matching number of $G$, that is, for the size of a maximum matching.
    \item $\m_{\mathsf{ind}}(G)$ for the induced matching number of $G$, that is, for the size of a maximum induced matching.
\end{itemize}
\end{definition}
We denote by $\mathsf{tw}(G)$ the \emph{treewidth} of a graph $G$. We omit the definition of treewidth as we rely on it in a black-box manner; the interested reader can see e.g.\ Chapter 7 of~\cite{CyganFKLMPPS15}.
For any $k \in \mathbb{N}$ the $k$-by-$k$ grid graph $\boxplus_k$, depicted in Figure~\ref{fig:wall_and_grid}, is defined by $V(\boxplus_k)=[k]^2$ and $E(\boxplus_k)=\{\{(i,j),(i',j')\} : i,j,i',j' \in [k], |i-i'|+|j-j'|=1\}$.
It is well known that $\mathsf{tw}(\boxplus_k)=k$, see~\cite[Chapter 7.7.1]{CyganFKLMPPS15}.

We make use of the following two consequences of Ramsey's Theorem for an arbitrary class of graphs $\mathcal{H}$. The first one is immediate, and the second one was established by Curticapean and Marx in~\cite{CurticapeanM14}.
\begin{theorem}\label{thm:ramsey}
If $|\mathcal{H}|=\infty$ then $\max(\alpha(\mathcal{H}),\omega(\mathcal{H}))=\infty$.
\end{theorem}
\begin{theorem}\label{thm:ramsey_match}
If ${\mathrm{m}}(\mathcal{H})=\infty$ then $\max(\omega(\mathcal{H}),\beta_{\mathsf{ind}}(\mathcal{H}),\m_{\mathsf{ind}}(\mathcal{H}))=\infty$.
\end{theorem}

A class of graphs is \emph{hereditary} if it is closed under vertex deletion, and is \emph{monotone} if it is hereditary and closed under edge deletion. In other words, hereditary classes are closed under taking induced subgraphs, and monotone classes are closed under taking subgraphs.


For presenting the different notions of graph minors used in this paper in a unified way, we start by introducing \emph{contraction models}.

\begin{definition}[Contraction model]
A \emph{contraction model} of a graph $H$ in a graph $G$ is a partition $\{V_1,\dots,V_k\}$ of $V(G)$ such that $G[V_i]$ is connected for each $i\in[k]$ and that $H$ is isomorphic to the graph obtained from $G$ by contracting each $G[V_i]$ into a single vertex (and deleting multiple edges and self-loops).
\end{definition}

Recall that a graph $F$ is a \emph{minor} of a graph $G$ if $F$ can be obtained from $G$ by deletion of edges and vertices, and by contraction of edges; equivalently, $F$ is a minor of $G$ if $F$ is a subgraph of a graph that has a contraction model in $G$. In this work, we will also require the subsequent stricter notion of minors.



\begin{definition}[Shallow minor~\cite{NesetrildM11}]
A graph $F$ is a \emph{shallow minor} at depth $d$ of a graph $G$ if $F$ is a subgraph of graph $H$ that has a contraction model $\{V_1,\dots,V_k\}$ in $G$ satisfying the following additional constraint: for each $i\in[k]$ there is a vertex $x_i\in V_i$ such that each vertex in $V_i$ has distance at most $d$ from $x_i$.
Given a class of graphs $\mathcal{G}$, we write $\mathcal{G} \triangledown d$ for the set of all shallow minors at depth $d$ of graphs in $\mathcal{G}$.
\end{definition}

Observe that the shallow minors at depth $0$ of $G$ are exactly the subgraphs of $G$, and the shallow minor of depth $|V(G)|$ are exactly the minors of $G$. For this reason, the notion of a shallow minor can be considered an interpolation between subgraphs and minors. Furthermore, having introduced this notion, we are now able to define somewhere dense and nowhere dense graph classes. 

\begin{definition}[Somewhere dense graph classes~\cite{NesetrildM11}]
A class of graphs $\mathcal{G}$ is \emph{somewhere dense} if $\omega(\mathcal{G} \triangledown d)=\infty$ for some $d \in \mathbb{N}_0$, and is \emph{nowhere dense} if instead $\omega(\mathcal{G} \triangledown d)< \infty$ for all $d \in \mathbb{N}_0$.
\end{definition}


We use the following characterisation of monotone somewhere dense graph classes.\footnote{It is non-trivial to pinpoint the first statement of Lemma~\ref{lem:nd_subdivisions} in the literature: Dvor{\'{a}}k et al.\ \cite{DvorakKT13} attribute it to Ne{\v{s}}et{\v{r}}il and de Mendez~\cite{NesetrildM11}, who provide an implicit proof. The first explicit statement is, to the best of our knowledge, due to Adler and Adler~\cite{Adlers14}.}

\begin{lemma}[Remark~2 in~\cite{Adlers14}]\label{lem:nd_subdivisions}
Let $\mathcal{G}$ be a monotone class of graphs. Then $\mathcal{G}$ is somewhere dense if and only if there exists $r \in \mathbb{N}_0$ such that $G^r \in \mathcal{G}$ for every graph $G$.
\end{lemma}



\subsection{Parameterised and Fine-Grained Complexity}\label{sec:param_fg}

A \emph{parameterized counting problem} is a pair $(P,\kappa)$ where $P:\{0,1\}^\ast \rightarrow \mathbb{N}$ and $\kappa:\{0,1 \}^\ast \rightarrow \mathbb{N}$ is computable. For an instance $x$ of $P$ we call $\kappa(x)$ the \emph{parameter} of $x$.
An algorithm $\mathbb{A}$ is \emph{fixed-parameter tractable} (FPT) w.r.t.\ a parameterization $\kappa$ if there is a computable function $f$ such that $\mathbb{A}$ runs in time $f(\kappa(x))\cdot |x|^{O(1)}$ on every input $x$. A parameterized counting problem $(P,\kappa)$ is \emph{fixed-parameter tractable} (FPT) if there is an FPT algorithm (w.r.t.\ $\kappa$) that computes $P$.

A \emph{parameterized Turing reduction} from $(P,\kappa)$ to $(P',\kappa')$ is an algorithm $\mathbb{A}$ equipped with oracle access to $P'$ satisfying the following constraints:
\begin{itemize}\itemsep0pt
    \item[(A1)] $\mathbb{A}$ computes $P$
    \item[(A2)] $\mathbb{A}$ is FPT w.r.t.\ $\kappa$
    \item[(A3)] there is a computable function $g$ such that, on input $x$, each oracle query $x'$ satisfies that $\kappa'(x')\leq g(\kappa(x))$.
\end{itemize}
We write $(P,\kappa) \leq^{\mathsf{FPT}} (P',\kappa')$ if a parameterized Turing reduction from $(P,\kappa)$ to $(P',\kappa')$ exists. 

The parameterized counting problem $\#\textsc{Clique}$ asks, on input a graph $G$ and a positive integer $k$, to compute the number of $k$-cliques in $G$; the parameter is $k$. As shown by Flum and Grohe~\cite{FlumG04}, $\#\textsc{Clique}$ is the canonical complete problem for the parameterized complexity class $\#\mathrm{W}[1]$. In particular, a parameterized counting problem $(P,\kappa)$ is called $\#\mathrm{W}[1]$-\emph{hard} if $\#\textsc{Clique} \leq^{\mathsf{FPT}} (P,\kappa)$. We omit the technical definition of $\#\mathrm{W}[1]$ via weft-1 circuits (see Chapter 14 of~\cite{FlumG06}), but we recall that $\#\mathrm{W}[1]$-hard problems are not FPT unless standard hardness assumptions fail (see below).

We define the problems studied in this work. As usual $\mathcal{H}$ and $\mathcal{G}$ denote classes of graphs. 

\begin{definition
$\#\textsc{Hom}(\mathcal{H}\!\to\!\mathcal{G}),\#\textsc{Sub}(\mathcal{H} \to \mathcal{G}),\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ ask, given $H \in \mathcal{H}$ and $G\in \mathcal{G}$, to compute respectively $\#\homs{H}{G},\#\subs{H}{G}, \#\indsubs{H}{G}$. The parameter is $|H|$.
\end{definition}
For example, $\#\textsc{Sub}(\mathcal{H}\to \mathcal{G})=\#\textsc{Clique}$ when $\mathcal{H}$ is the class of all complete graphs and $\mathcal{G}$ the class of all graphs. The following result follows immediately from an algorithm for counting answers to Boolean queries in nowhere dense graphs due to Ne{\v{s}}et{\v{r}}il and de Mendez~\cite{Sparsity}.

\begin{theorem}[Theorem 18.9 in~\cite{Sparsity}]\label{thm:sparsity}
If $\mathcal{G}$ is nowhere dense then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$, $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$, and $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ are fixed-parameter tractable and can be solved in time
$f(|H|)\cdot |V(G)|^{1+o(1)}$ for some computable function $f$.
\end{theorem}

In an intermediate step towards our classifications, we will rely on a coloured version of homomorphism counting.

 

\begin{definition}\label{defwithsurj}
$\#\text{\sc{cp-Hom}}(\mathcal{H} \to \mathcal{G})$ asks, given $H\in \mathcal{H}$ and a surjectively\footnote{In previous works (e.g.\ in~\cite{RothSW21Icalp}), the definition of $\#\text{\sc{cp-Hom}}(\mathcal{H} \to \mathcal{G})$ did not require the $H$-colouring to be surjective. However, it was noted that one can always assume surjectivity, since $\#\homs{(H,\mathsf{id}_H)}{(G,c)}=0$ if $c$ is not surjective. We decided to make the surjectivity condition explicit in the current work.} $H$-coloured graph $(G,c)$ with $G \in \mathcal G$, to compute $\#\homs{(H,\mathsf{id}_H)}{(G,c)}$, where $\mathsf{id}_H$ denotes the identity on $V(H)$. The parameter is $|H|$.
\end{definition}
Recall that ${\mathcal{U}}$ denotes the class of all graphs. It is well known that $\#\text{\sc{cp-Hom}}(\mathcal{H} \to {\mathcal{U}})$ reduces to the uncoloured version via the inclusion-exclusion principle. This holds for $\#\text{\sc{cp-Hom}}(\mathcal{H} \to \mathcal{G})$, too, if $\mathcal{G}$ is monotone. Thus:
\begin{lemma}[see e.g.\ Lemma~2.49 in~\cite{Roth19}]\label{lem:hom_colreduction}
If $\mathcal{G}$ is monotone then $\#\text{\sc{cp-Hom}}(\mathcal{H} \to \mathcal{G}) \leq^{\mathsf{FPT}} \#\textsc{Hom}(\mathcal{H}\to \mathcal{G})$.
Moreover, on input $H\in \mathcal{H}$ and $(G,c)$ with $G\in \mathcal{G}$, every oracle query $(H',G')$ in the reduction satisfies $H'=H$ and $G' \subseteq G$.
\end{lemma}

An implicit consequence of the parameterized complexity classification for counting homomorphisms due to Dalmau and Jonsson~\cite{DalmauJ04} establishes the following hardness result for $\#\text{\sc{cp-Hom}}$; an explicit argument can be found e.g.\ in Chapter~2 in~\cite{Roth19}.

\begin{theorem}[\cite{DalmauJ04}]\label{thm:cphomshard}
If $\mathcal{H}$ is recursively enumerable and $\mathsf{tw}(\mathcal{H})=\infty$ then $\#\text{\sc{cp-Hom}}(\mathcal{H} \to {\mathcal{U}})$ is $\#\mathrm{W}[1]$-hard.
\end{theorem}

\paragraph*{Fine-Grained Complexity and Conditional Lower Bounds}
All running-time lower bounds in this paper will be conditioned on the ETH:
\begin{definition}[\cite{ImpagliazzoP01}]
The \emph{Exponential Time Hypothesis (ETH)} asserts that $3$-$\textsc{SAT}$ cannot be solved in time $\mathsf{exp}(o(n))$ where $n$ is the number of variables of the input formula. 
\end{definition}

Chen et al.~\cite{Chenetal05,Chenetal06} showed that there is no function $f$ such that $\#\textsc{Clique}$ can be solved in time $f(k)\cdot |G|^{o(k)}$ unless ETH fails. This in particular implies that $\#\mathrm{W}[1]$-hard problems are not FPT unless ETH fails. Marx~\cite{Marx10} strengthened Theorem~\ref{thm:cphomshard} into:\footnote{More precisely, Marx established the bound for the so-called partitioned subgraph problem. However, as shown in~\cite{RothSW20}, the lower bound immediately translates to $\#\text{\sc{cp-Hom}}(\mathcal{H}\to {\mathcal{U}})$.}

\begin{theorem}[\cite{Marx10}]\label{thm:cybt}
If $\mathcal{H}$ is recursively enumerable and $\mathsf{tw}(\mathcal{H})=\infty$ then $\#\text{\sc{cp-Hom}}(\mathcal{H}\to {\mathcal{U}})$ cannot be solved in time $f(|H|)\cdot |G|^{o\left(\frac{\mathsf{tw}(H)}{\log \mathsf{tw}(H)}\right)}$
for any function $f$, unless ETH fails.
\end{theorem}
\noindent The question of whether the $(\log \mathsf{tw}(H))^{-1}$ factor in the above lower bound can be omitted can be considered the counting version of the open problem ``Can you beat treewidth?''~\cite{Marx10,Marx13}.


\section{Counting Homomorphisms}

We start by showing a reduction from $\#\text{\sc{cp-Hom}}(\mathcal{H}\to {\mathcal{U}})$ to counting colour-prescribed homomorphisms between subdivided graphs. While the proof is straightforward, the reduction will be useful in the analysis of the more involved cases of counting subgraphs and induced subgraphs.

To begin with, let 
$c \in \surhoms{G}{H}$ and let $r \in \mathbb{N}_0$. Define the following canonical
homomorphism $c^r$ from~$G^r$ to~$H^r$.  For each $u\in V(G)$, set $c^r(u):= c(u)$. 
For any edge $e=\{u_1,u_2\} \in E(G)$,  let $u_1,w_1,\dots,w_r,u_2$ be the corresponding path in $G^r$. Let $e'=\{v_1,v_2\}=\{c(u_1),c(u_2)\}$ --- note that $e' \in E(H)$ as $c \in \homs{G}{H}$ --- and let $v_1,x_1,\dots,x_r,v_2$ be the corresponding path in $H^r$. Then, set $c^r(w_i):=x_i$ for each $i\in\{1,\dots,r\}$.
It is easy to see that $c^r$ is indeed a surjective $H^r$-colouring of $G^r$. Furthermore:
\begin{lemma}\label{lem:hom_subdiv}\label{lem:aa}
For every surjevtively $H$-coloured graph $(G,c)$ and every $r \in \mathbb{N}_0$,
\begin{align}
    \#\homs{(H,\mathsf{id}_H)}{(G,c)}=\#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}
\end{align}
where $\mathsf{id}_H$ and $\mathsf{id}_{H^r}$ are the identities on respectively  $V(H)$ and $V(H^r)$.
\end{lemma}
\begin{proof}
 We define a bijection $b:\homs{(H,\mathsf{id}_H)}{(G,c)} \to \homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}$. Let $\varphi \in \homs{(H,\mathsf{id}_H)}{(G,c)}$.
For every $v\in V(H)$ let $b(\varphi)(v)=\varphi(v)$. For every $\{v_1,v_2\} \in E(H)$ and every $i \in [r]$, if $u_1=\varphi(v_1)$ and $u_2=\varphi(v_2)$, and if $x_i$ and $w_i$ are the $i$-th vertices on the paths respectively between $v_1$ and $v_2$ in $H^r$ and between $u_1$ and $u_2$ in $G^r$, then let $b(\varphi)(x_i)=w_i$.
It is easy to see that $b(\varphi) \in \homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}$ and that $b$ is injective. To see that $b$ is surjective as well, note that for every $\varphi^r \in \homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}$ its restriction $\varphi^r|_{V(H)}$ to $V(H)$ satisfies $\varphi^r|_{V(H)} \in \homs{(H,\mathsf{id}_H)}{(G,c)}$ and $b(\varphi^r|_{V(H)})= \varphi^r$.
\end{proof}


\subsection{Warm-up: Minor-closed Pattern Classes}
Using the characterisation of somewhere dense graph classes in Lemma~\ref{lem:nd_subdivisions}, and known lower bounds for counting homomorphisms from grid graphs, we obtain as an easy consequence the following complexity dichotomy:
\begin{theorem}\label{thm:homs_warmup}
Let $\mathcal{H}$ be a minor-closed class of graphs and let $\mathcal{G}$ be a monotone and somewhere dense class of graphs. 
\begin{enumerate}
    \item If $\mathsf{tw}(\mathcal{H})< \infty$ then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G}) \in \mathsf{P}$. Moreover, if a tree decomposition of $H$ of width $t$ is given, then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ can be solved in time $|H|^{O(1)}\cdot |V(G)|^{t+1}$. 
    \item If $\mathsf{tw}(\mathcal{H})=\infty$, then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ is $\#\mathrm{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(|H|)\cdot |G|^{o(\mathsf{tw}(H))}$ for any function $f$.
\end{enumerate}
\end{theorem}
\begin{proof}
The tractability result is well known~\cite{DiazST02,DalmauJ04}, so we only need to prove the hardness part. Recall that $\boxplus_k$ denotes the $k$-by-$k$ grid; see Figure~\ref{fig:wall_and_grid} for a depiction of $\boxplus_4$. Let $\boxplus := \{\boxplus_k~|~k\in \mathbb{N}\}$.
It is known that $\#\text{\sc{cp-Hom}}(\boxplus\to {\mathcal{U}})$ is $\#\mathrm{W}[1]$-hard and, unless ETH fails, cannot be solved in time $f(k)\cdot |G|^{o(k)}$ for any function $f$ (see~\cite[Lemma 1.13 and 5.7]{Curticapean15} or \cite[Lemma 2.45]{Roth19}). As $\mathsf{tw}(\boxplus_k)=k$, the lower bound above can be written as $f(k)\cdot |G|^{o(\mathsf{tw}(\boxplus_k))}$.

Let $(\boxplus_k,(G,c))$ be the input to $\#\text{\sc{cp-Hom}}(\boxplus\to {\mathcal{U}})$. Since $\mathcal{G}$ is somewhere dense and monotone, by Lemma~\ref{lem:nd_subdivisions} there is $r \in \mathbb{N}_0$ such that $\mathcal{G}$ contains the $r$-subdivision of every graph and thus, in particular, $G^r$.
Moreover, since $\mathsf{tw}(\mathcal{H})=\infty$ and $\mathcal{H}$ is minor-closed, by the Excluded-Grid Theorem~\cite{RobertsonS86-ExGrid} $\mathcal{H}$ contains every planar graph and thus in particular $\boxplus_k^r$. Clearly, $\boxplus_k^r$, $G^r$ and $c^r$ can be computed in polynomial time.
Moreover, by Lemma~\ref{lem:aa},
\[\#\homs{(\boxplus_k,\mathsf{id}_{\boxplus_k})}{(G,c)}=\#\homs{(\boxplus_k^r,\mathsf{id}_{\boxplus_k^r})}{(G^r,c^r)}\,.\]
Hence $\#\text{\sc{cp-Hom}}(\boxplus\to {\mathcal{U}}) \leq^{\mathsf{FPT}} \#\text{\sc{cp-Hom}}(\mathcal{H} \to \mathcal{G})$.
Since $\#\text{\sc{cp-Hom}}(\mathcal{H} \to \mathcal{G}) \leq^{\mathsf{FPT}} \#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ by Lemma~\ref{lem:hom_colreduction}, we conclude that $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ is $\#\mathrm{W}[1]$-hard.
For the conditional lower bound, observe that both reductions used above preserve the treewidth of the pattern (the first because treewidth is invariant under edge subdivision,\footnote{For example,
this invariance is in  Exercises 7.7 and 7.13 in~\cite{CyganFKLMPPS15}.} the second by Lemma~\ref{lem:hom_colreduction}). 
\end{proof}

\subsection{Monotone Pattern Classes}
The strengthening of  Theorem~\ref{thm:homs_warmup} to monotone pattern classes can be done by reduction from counting homomorphisms from a class of graphs called ``walls''. 
The interior of a ``wall'' is a regular lattice in which each face is surrounded by 6 sides.


\begin{definition}[Walls]
Let $k$ and $\ell$ be positive integers. The \emph{wall} of height $k$ and length $\ell$, denoted by $W_{k,\ell}$, has vertices $v_{i,j}$ for all $1\leq i \leq k$ and $1\leq j\leq \ell$, and it contains the edges
\begin{itemize}
    \item $\{v_{i,j},v_{i,j+1}\}$ for all $1\leq i \leq k$ and $1\leq j\leq \ell-1$,
    \item $\{v_{i,1},v_{i+1,1}\}$ and $\{v_{i,\ell},v_{i+1,\ell}\}$ for all $1\leq i \leq k-1$, and
    \item $\{v_{i,j},v_{i+1,j}\}$ for all $1\leq i \leq k-1$ and $1\leq j\leq \ell$ such that $i+j$ is even.
\end{itemize}
The wall $W_{4,5}$ is depicted in Figure~\ref{fig:wall_and_grid}. We set $\mathcal{W}:=\{W_{k,k}~|~k\in\mathbb{N}_{>0}\}$ to be the class of all walls.
\end{definition}

\begin{figure}[t]
        \centering
        \begin{tikzpicture}[scale=1]
            \centering
            
                \node[vertex] (11) at (1, 1) {};
                \node[vertex] (12) at (1, 2) {};
                \node[vertex] (13) at (1, 3) {};
                \node[vertex] (14) at (1, 4) {};
                
                \node[vertex] (21) at (2, 1) {};
                \node[vertex] (22) at (2, 2) {};
                \node[vertex] (23) at (2, 3) {};
                \node[vertex] (24) at (2, 4) {};
                
                \node[vertex] (31) at (3, 1) {};
                \node[vertex] (32) at (3, 2) {};
                \node[vertex] (33) at (3, 3) {};
                \node[vertex] (34) at (3, 4) {};
                
                \node[vertex] (41) at (4, 1) {};
                \node[vertex] (42) at (4, 2) {};
                \node[vertex] (43) at (4, 3) {};
                \node[vertex] (44) at (4, 4) {};
                
                \node[vertex] (51) at (5, 1) {};
                \node[vertex] (52) at (5, 2) {};
                \node[vertex] (53) at (5, 3) {};
                \node[vertex] (54) at (5, 4) {};
               
               
                \draw (11) -- (12); \draw (12) -- (13); \draw (13) -- (14);  
                \draw (51) -- (52); \draw (52) -- (53); \draw (53) -- (54);  
                
                \draw (11) -- (21); \draw (21) -- (31); \draw (31) -- (41); \draw (41) -- (51); 
                \draw (12) -- (22); \draw (22) -- (32); \draw (32) -- (42); \draw (42) -- (52); 
                \draw (13) -- (23); \draw (23) -- (33); \draw (33) -- (43); \draw (43) -- (53); 
                \draw (14) -- (24); \draw (24) -- (34); \draw (34) -- (44); \draw (44) -- (54); 
                
                \draw (31) -- (32); \draw (33) -- (34);  \draw (22) -- (23); \draw (42) -- (43); 
                
              \begin{scope}[xshift = +6cm]
              
                \node[vertex] (11) at (1, 1) {};
                \node[vertex] (12) at (1, 2) {};
                \node[vertex] (13) at (1, 3) {};
                \node[vertex] (14) at (1, 4) {};
                
                \node[vertex] (21) at (2, 1) {};
                \node[vertex] (22) at (2, 2) {};
                \node[vertex] (23) at (2, 3) {};
                \node[vertex] (24) at (2, 4) {};
                
                \node[vertex] (31) at (3, 1) {};
                \node[vertex] (32) at (3, 2) {};
                \node[vertex] (33) at (3, 3) {};
                \node[vertex] (34) at (3, 4) {};
                
                \node[vertex] (41) at (4, 1) {};
                \node[vertex] (42) at (4, 2) {};
                \node[vertex] (43) at (4, 3) {};
                \node[vertex] (44) at (4, 4) {};
                
                \draw (11) -- (12); \draw (12) -- (13); \draw (13) -- (14);
                \draw (21) -- (22); \draw (22) -- (23); \draw (23) -- (24);
                \draw (31) -- (32); \draw (32) -- (33); \draw (33) -- (34);
                \draw (41) -- (42); \draw (42) -- (43); \draw (43) -- (44);
                
                \draw (11) -- (21); \draw (21) -- (31); \draw (31) -- (41); 
                \draw (12) -- (22); \draw (22) -- (32); \draw (32) -- (42); 
                \draw (13) -- (23); \draw (23) -- (33); \draw (33) -- (43); 
                \draw (14) -- (24); \draw (24) -- (34); \draw (34) -- (44); 
                
                
              \end{scope}
         \end{tikzpicture}
        \caption{The wall $W_{4,5}$ (\emph{left}) and the grid $\boxplus_4$ (\emph{right}).} 
        \label{fig:wall_and_grid}
    \end{figure}

The following structural property of large walls is due to Thomassen.\footnote{To avoid confusion, we emphasize that walls are called grids in~\cite{Thomassen88}.}
\begin{lemma}[Proposition~3.2 in~\cite{Thomassen88}]\label{lem:erdos_posa_walls}
For every pair of integers $k$ and $r$, there exists an integer $h(k,r)$ such that every subdivision of $W_{h(k,r),h(k,r)}$ contains as a subgraph a subdivision of $W_{k,k}$ in which each edge is subdivided a (positive) multiple of $r$ times.
\end{lemma}

The final ingredient of our proof for the classification of monotone pattern classes is given by Lemma~\ref{lem:nd_subdivision_strong}, which is an immediate consequence of Lemma~\ref{lem:nd_subdivisions}.
\begin{lemma}\label{lem:nd_subdivision_strong}
Let $\mathcal{G}$ be a monotone and somewhere dense class of graphs. There exists $r\in \mathbb{N}_0$ such that the following is true: Let $G$ be any graph and let $G'$ be any graph obtained from $G$ by subdividing each edge a (positive) multiple of $r$ times. Then $G'$ is contained in $\mathcal{G}$.
\end{lemma}
\begin{proof}
We show that the claim holds for $r\in\mathbb{N}_0$ given by Lemma~\ref{lem:nd_subdivisions}. 
For this $r$, Lemma~\ref{lem:nd_subdivisions}
guarantees that for every graph~$H$, $H^r\in \mathcal{G}$.
Now let $G$ be any graph and label its edges $e_1,\dots,e_m$. Let $G'$ be any graph obtained from $G$ by subdividing each edge a (positive) multiple of $r$ times. Then there are positive integers $d_1,\dots,d_m$ such that, for each $i\in[m]$, the edge $e_i$ is subdivided $d_ir$ times. Now let $\hat{G}$ be the graph obtained from $G$ by subdividing, for each $i\in[m]$, the edge $e_i$ just $d_i$ times.
It is immediate that $G'=\hat{G}^r$. Thus, by Lemma~\ref{lem:nd_subdivisions} and our choice of $r$, we have that $G'\in\mathcal{G}$.
\end{proof}

We are now ready to establish the main result of this section.
\begin{theorem}\label{thm:main_homs}
Let $\mathcal{H}$ be a monotone class of graphs and let $\mathcal{G}$ be a monotone and somewhere dense class of graphs. 
\begin{enumerate}
    \item If $\mathsf{tw}(\mathcal{H})< \infty$ then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G}) \in \mathsf{P}$. Moreover, if a tree decomposition of $H$ of width $t$ is given, then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ can be solved in time $|H|^{O(1)}\cdot |V(G)|^{t+1}$. 
    \item If $\mathsf{tw}(\mathcal{H})=\infty$, then $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ is $\#\mathrm{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(|H|)\cdot |G|^{o(\mathsf{tw}(H))}$ for any function $f$.
\end{enumerate}
\end{theorem}
\begin{proof}
The tractability result is well known~\cite{DiazST02,DalmauJ04}, so we only need to prove the hardness part. 

We will reduce from $\#\text{\sc{cp-Hom}}(\mathcal{W}\to {\mathcal{U}})$. Walls clearly have grid minors of linear size, that is, there is a function $h\in\Theta(k)$ such that $W_{k,k}$ contains $\boxplus_{h(k)}$ as a minor. Furthermore, it is well-known that $\#\text{\sc{cp-Hom}}$ is minor-monotone (see e.g.\ \cite[Lemma 5.8]{Curticapean15} or \cite[Lemma 2.47]{Roth19}), that is, $\#\text{\sc{cp-Hom}}(\boxplus\to {\mathcal{U}})\leq^{\mathsf{FPT}} \#\text{\sc{cp-Hom}}(\mathcal{W}\to {\mathcal{U}})$. Moreover,  this reduction is tight in the sense that the lower bound for $\#\text{\sc{cp-Hom}}(\boxplus\to {\mathcal{U}})$ as established in the proof of Theorem~\ref{thm:homs_warmup} transfers. Concretely, we have that $\#\text{\sc{cp-Hom}}(\mathcal{W}\to {\mathcal{U}})$ is $\#\mathrm{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(k)\cdot |G|^{o(\mathsf{tw}(W_{k,k}))}$ for any function $f$.

Let us now construct the reduction $\#\text{\sc{cp-Hom}}(\mathcal{W}\to {\mathcal{U}}) \leq^{\mathsf{FPT}} \#\text{\sc{cp-Hom}}(\mathcal{H}\to\mathcal{G})$.
Let $r\in \mathbb{N}_0$ as given by Lemma~\ref{lem:nd_subdivision_strong}. We use the fact that $\mathcal{H}$ having unbounded treewidth implies that it contains as minors all planar graphs, that is, for every planar graph $F$, there is a graph $H\in\mathcal{H}$ such that $F$ is a minor of $H$~\cite{RobertsonS86-ExGrid}. 
In particular, $\mathcal{H}$ contains all walls $W_{k,k}$ as minors. 
A graph $J$ is said to be a ``topological minor'' of a graph $H$ if there is a subdivision of $J$ that is isomorphic to a subgraph of $H$. 
Since walls have degree at most $3$, 
the fact that $\mathcal{H}$ contains all walls as minors implies that it also contains all walls as topological minors (see e.g. \cite[Proposition 1.7.3]{Diestel17}).  

Now let $W_{k,k}$ and $(G,c)$ be an input instance of $\#\text{\sc{cp-Hom}}(\mathcal{W}\to {\mathcal{U}})$.  Let the edges of $W_{k,k}$ be $e_1,\ldots,e_\ell$ where 
$\ell=|E(W_{k,k})|$ 
denotes the number of edges of $W_{k,k}$
and this edges are ordered arbitrarily.  By Lemma~\ref{lem:erdos_posa_walls},   every subdivision of $W_{h(k,r),h(k,r)}$ contains as a subgraph a subdivision of $W_{k,k}$ in which each edge is subdivided a (positive) multiple of $r$ times. 
Since $\mathcal{H}$ contains $W_{k,k}$ as a topological minor,
there is a subdivision of $W_{k,k}$
that is isomorphic to a subgraph~$W'$ 
of a graph in $\mathcal{H}$. Since $\mathcal{H}$ is monotone (closed under taking subgraphs),  there exists $W'\in \mathcal{H}$ and positive integers $d_1,\dots,d_\ell$ such that $W'$ is obtained from $W_{k,k}$ by subdividing $e_i$  $d_ir$ times, for each $i\in[\ell]$.   

We will now construct from $(G,c)$ a
graph $G'$ and a surjective homomorphism~$c'$
from~$G'$ to~$W'$. 
For each edge $e=\{u,v\}$ of $G$ we proceed as follows. Since $c$ is a   homomorphism from~$G$ to~$W_{k,k}$, we have that $\{c(u),c(v)\}=e_i$ for some $i\in[\ell]$. By the definition of $W'$,   $e_i$ was replaced by a path $c(u),x_1,\dots,x_{d_ir},c(v)$.
Hence, we replace the edge $e$ in $G$ by a path $u,w_1,w_2,\dots,w_{d_ir},v$, where the $w_j$ are fresh vertices. Furthermore, we extend the colouring $c$ to the colouring $c'$ by setting $c'(w_j):=x_j$ for each $j\in[d_ir]$. 
Since $c$ is surjective, so is $c'$. 
Also,

\[\#\homs{(W_{k,k},\mathsf{id}_{W_{k,k}})}{G,c} = \#\homs{(W',\mathsf{id}_{W'})}{(G',c')} \,.\]
By querying the oracle for $\#\text{\sc{cp-Hom}}(\mathcal{H}\to\mathcal{G})$ on the instance $((W',\mathsf{id}_{W'}),(G',c'))$ we can thus conclude our reduction.
This immediately implies $\#\mathrm{W}[1]$-hardness of $\#\text{\sc{cp-Hom}}(\mathcal{H}\to\mathcal{G})$. For the conditional lower bound, we observe that $W'$ has the same treewidth as $W_{k,k}$ since it is a subdivision of $W_{k,k}$, and that the size of $(G',c')$ is clearly bounded by $f(k)\cdot |G|^{O(1)}$ --- note that the $f$ depends on $\mathcal{H}$ which is, however, fixed.
Finally, we obtain the statement of the theorem by reducing to the uncoloured version (Lemma~\ref{lem:hom_colreduction}).
\end{proof}

Finally, we point out that Theorem~\ref{thm:main_homs_intro} is an immediate consequence of Theorem~\ref{thm:main_homs} and Theorem~\ref{thm:sparsity}.

\noindent\textbf{Remark:} We conclude this section by pointing out that a strengthening of Theorem~\ref{thm:main_homs} to hereditary pattern classes $\mathcal{H}$ is not possible. Consider, for example, the case in which $\mathcal{H}$ contains all complete graphs and $\mathcal{G}$ is the class of all bipartite graphs. Although $\mathcal{H}$ is hereditary and of unbounded treewidth, and $\mathcal{G}$ is monotone and somewhere dense, it is easy to see that $\#\textsc{Hom}(\mathcal{H} \to \mathcal{G})$ is trivial, since we can always output zero if $H\in\mathcal{H}$ has at least $3$ vertices.

When it comes to a sufficient and necessary condition for tractability in case of hereditary classes of patterns, we conjecture that \emph{induced grid minor size} might be the right candidate. However, even for very special cases, such as classes of degenerate host graphs (which are somewhere dense and monotone), it is still open whether induced grid minor size is the correct answer~\cite{BressanR21}. Thus, we leave the classification for hereditary classes of patterns as an open problem for further research. 


\section{Counting Subgraphs}\label{sec:subgraphs}
We begin with the analysis of the problem of counting $k$-matchings. Recall that a $k$-matching in a graph $G$ is a set of $M\subseteq E(G)$ with $|M|=k$ and $e_1\cap e_2 = \emptyset$ for all $e_1\neq e_2$ in $M$. In other words, a $k$-matching in $G$ is a set of $k$ pairwise non-incident edges of $G$. Given a class of graph $\mathcal{G}$, the problem $\#\textsc{Match}(\mathcal{G})$ asks, on input a positive integer $k$ and a graph $G\in \mathcal{G}$, to compute the number of $k$-matchings in $G$; the parameter is $k$. We remark that $\#\textsc{Match}(\mathcal{G})=\#\textsc{Sub}(\mathcal{M} \to \mathcal{G})$ where $\mathcal{M}$ is the set of all $1$-regular graphs.

For our analysis, we rely on the Tensor product of $H$-coloured graphs as used in~\cite{RothSW21Icalp}. 
\begin{definition}\label{def:tensor}
Let $H$ be a graph, and let $(G_1,c_1)$ and $(G_2,c_2)$ be $H$-coloured graphs. We define the \emph{Tensor product} $(G_1,c_1) \times (G_2,c_2):= (\hat{G},\hat{c})$ as follows:
\begin{enumerate}
    \item[(T1)]  $V(\hat{G}):= \{(v_1,v_2) \in V(G_1) \times V(G_2)~|~c_1(v_1)=c_2(v_2) \}$.
    \item[(T2)]  $\{(u_1,u_2),(v_1,v_2)\}\in E(\hat{G})$ if and only if $\{u_1,v_1 \}\in E(G_1)$ and $\{u_2,v_2 \}\in E(G_2)$.
    \item[(T3)] For each vertex $(v_1,v_2)\in V(\hat{G})$ we set $\hat{c}(v_1,v_2):= c_1(v_1)$ ( $=c_2(v_2)$ by (T1)).
\end{enumerate}
\end{definition}

The crucial property of the Tensor product is given in the following lemma.\footnote{\label{fmark1}Proofs of Lemma~\ref{lem:tensor_linear_subgraphs} and Lemma~\ref{lem:MH_nonsingular} can be found in Section 3.1 in the full version~\cite{RothSW21Arxiv} of~\cite{RothSW21Icalp}.}

\begin{lemma}[\cite{RothSW21Icalp}]\label{lem:tensor_linear_subgraphs}
Let $H$ be a graph, and let $(F,c_F)$, $(G_1,c_1)$ and $(G_2,c_2)$ be $H$-coloured graphs. We have
\[\#\homs{(F,c_F)}{(G_1,c_1) \times (G_2,c_2)} = \#\homs{(F,c_F)}{(G_1,c_1)} \cdot \#\homs{(F,c_F)}{(G_2,c_2)}  \,.\]
\end{lemma}

The final ingredient we need is the non-singularity of a certain matrix, the entries of which count homomorphisms between fractured graphs. Formally, let $H$ be a graph. We define the square matrix $M_H$, the rows and columns of which are indexed by the fractures of $H$, and the entries of which satisfy
\begin{equation}\label{eq:MHdef}
    M_H[\rho,\sigma]:= \#\homs{(\fracture{H}{\rho},c_\rho)}{(\fracture{H}{\sigma},c_\sigma)}\,,
\end{equation}
where $c_\rho$ and $c_\sigma$ are the canonical $H$-colourings of the fractured graphs $\fracture{H}{\rho}$ and $\fracture{H}{\sigma}$ (see Definition~\ref{def:canonical_col} and Observation~\ref{obs:canonical_col}). By ordering the columns and rows of $M_H$ along a certain lattice, the following property was established in previous work.\footnote{See Footnote~\ref{fmark1}.}

\begin{lemma}[\cite{RothSW21Icalp}]\label{lem:MH_nonsingular}
For each graph $H$, the matrix $M_H$ is non-singular.
\end{lemma}

Our goal is to establish hardness of $\#\textsc{Match}(\mathcal{G})$ for each monotone and somewhere dense class $\mathcal{G}$. If $\mathcal{G}$ is closed under \emph{uncoloured} Tensor products\footnote{The adjacency matrix of the Tensor product of two uncoloured graphs $G$ and $F$ is the Kronecker product of the adjacency matrices of $G$ and $F$.}, then the hardness result can be achieved by applying the reduction in the breakthrough result of Curticapean, Dell and Marx~\cite{CurticapeanDM17} verbatim. However,  this reduction fails if $\mathcal{G}$ is not closed under uncoloured Tensor products, and we wish to point out that this closure property is very restrictive: Consider for example the class $\mathcal{G}$ of square-free graphs, i.e., graphs that do not contain a $4$-cycle as a subgraph. This class is clearly monotone and, since it contains the $3$-subdivision of every graph, it is also somewhere dense by Lemma~\ref{lem:nd_subdivisions}. However, it is not closed under (uncoloured) Tensor products: Let $P_2 \in \mathcal{G}$ be the path containing two edges. Then the Tensor product of $P_2$ with itself contains a $4$-cycle.

The main insight of this section is a weakened closure property for monotone and somewhere dense graph classes established in the lemma below; in combination with the characterisation of somewhere dense graph classes via $r$-subdivisions (Lemma~\ref{lem:nd_subdivisions}) the statement informally asserts that any monotone and somewhere dense class is closed under Tensor products of subdivisions of \emph{coloured} graphs.

\begin{figure}[t]
        \centering
        \begin{tikzpicture}[scale=0.6]
            \centering
            \begin{scope}
            
                \node[vertex] (U1) at (0, -0) {};
                \node[vertex] (U2) at (0, -4) {};
                \node[vertex] (V1) at (-4, 0) {};
                \node[vertex] (V2) at (-4, -4) {};
                \node[vertex] (V11) at (-3.5, -0.5) {};
                \node[vertex] (U21) at (-0.5, -3.5) {};
               
                \draw (U1) -- (V1); \draw (U1) -- (U2); \draw (V2) -- (V1); \draw (V2) -- (U2); 
                \draw (U21) -- (V2); \draw (U21) -- (U1); \draw (V11) -- (V2); \draw (V11) -- (U1);
                
                \node (e1) at (-2.7, .1) {};
                \node (e2) at (0.7, -2.1) {};
               
               
                \node at (-2,-2) {\large $G$};




                \node[vertex] (U1) at (8.5, 0) {};
                \node[vertex] (U2) at (8.5, -4) {};
                \node[vertex] (V1) at (4.5, 0) {};
                \node[vertex] (V2) at (4.5, -4) {};
               \draw (U1) -- (V1); \draw (U1) -- (U2); \draw (V2) -- (V1); \draw (V2) -- (U2);
              

                \node (e1) at (3.3, .1) {};
                \node (e2) at (6.7, -2.1) {};
               
                \node at (6.5,-2) {\large $H$};
               
            \end{scope}
            
            \begin{scope}[yshift =-5cm]
            
                \node[vertex] (U1) at (0, -0) {};
                \node[vertex] (U2) at (0, -4) {};
                \node[vertex] (V1) at (-4, 0) {};
                \node[vertex] (V2) at (-4, -4) {};
                \node[vertex] (V11) at (-3.5, -0.5) {};
                \node[vertex] (U21) at (-0.5, -3.5) {};
                
                \node[inner sep =1.75pt, fill] (M) at (-2, 0) {};
                \node[inner sep =1.75pt, fill] (M) at (-2, -2/7) {};
                
                \node[inner sep =1.75pt, fill] (M) at (-2, -4) {};
                \node[inner sep =1.75pt, fill] (M) at (-2, -4 +2/7) {};
                
                \node[inner sep =1.75pt, fill] (M) at (0, -2) {};
                \node[inner sep =1.75pt, fill] (M) at (-2/7, -2) {};
                
                \node[inner sep =1.75pt, fill] (M) at (-4, -2) {};
                \node[inner sep =1.75pt, fill] (M) at (-4+2/7, -2) {};
               
                \draw (U1) -- (V1); \draw (U1) -- (U2); \draw (V2) -- (V1); \draw (V2) -- (U2); 
                \draw (U21) -- (V2); \draw (U21) -- (U1); \draw (V11) -- (V2); \draw (V11) -- (U1);
                
                \node (e1) at (-2.7, .1) {};
                \node (e2) at (0.7, -2.1) {};
               
               
               
                
                \node at (-2,-2) {\large $G^1$};




                \node[vertex] (U1) at (6, 0) {};
                \node[vertex] (U2) at (6, -4) {};
                \node[vertex] (V1) at (2, 0) {};
                \node[vertex] (V2) at (2, -4) {};
                \draw (U1) -- (V1); \draw (U1) -- (U2); \draw (V2) -- (V1); \draw (V2) -- (U2);
                \node[inner sep =1.75pt, fill] (M) at (4, 0) {};
                
                \node[inner sep =1.75pt, fill] (M) at (4, -4) {};
                
                \node[inner sep =1.75pt, fill] (M) at (6, -2) {};
                
                \node[inner sep =1.75pt, fill] (M) at (2, -2) {};

               
               
                
                \node at (4,-2) {\large $H^1$};
                
               
                \node[vertex] (U1) at (11, 0) {};
                \node[vertex] (U2) at (11, -3.5) {};
                \node[vertex] (U22) at (10.5, -4) {};
                \node[vertex] (V1) at (7, 0) {};
                \node[vertex] (V2) at (7, -4) {};
                
                \node[inner sep =1.75pt, fill] (M1) at (9, 0) {};
                
                \node[inner sep =1.75pt, fill] (M2) at (9.25, -4) {};
                \node[inner sep =1.75pt, fill] (M12) at (8.75, -4) {};
                
                \node[inner sep =1.75pt, fill] (M3) at (11, -2) {};
                
                \node[inner sep =1.75pt, fill] (M4) at (7, -2) {};

               
               
       
               \draw (U1) -- (V1); \draw (U1) -- (U2); \draw (V2) -- (V1); \draw (V2) -- (M12); \draw (M2) -- (U22);
               
               \node at (9,-2) {\large $\fracture{H^1}{\rho}$};
        
               
            \end{scope}
           
            \begin{scope}[xshift =11cm, yshift=-0.5cm]
              \node[vertex] (U1) at (10, 0) {};
                \node[vertex] (U2) at (10, -7.5) {};
                \node[vertex] (U22) at (9.5, -8) {};
                \node[vertex] (W2) at (9, -6.5) {};
                \node[vertex] (W22) at (8.5, -7) {};
                \node[vertex] (V1) at (2, 0) {};
                \node[vertex] (W1) at (3, -1) {};
                \node[vertex] (V2) at (2, -8) {};
                
                \node[inner sep =1.75pt, fill] (M1) at (6, 0) {};
                \node[inner sep =1.75pt, fill] (M1N1) at (6, -4/7) {};
                
                \node[inner sep =1.75pt, fill] (M2) at (6.25, -8) {};
                \node[inner sep =1.75pt, fill] (M2N1) at (6.25, -191/26) {};
                \node[inner sep =1.75pt, fill] (M2N2) at (5.75, -193/26) {};
                
                \node[inner sep =1.75pt, fill] (M12) at (5.75, -8) {};
                
                \node[inner sep =1.75pt, fill] (M3) at (10, -4) {};
                \node[inner sep =1.75pt, fill] (M3N1) at (61/6.5, -4) {};
                
                \node[inner sep =1.75pt, fill] (M4) at (2, -4) {};
                \node[inner sep =1.75pt, fill] (M4N1) at (2+4/7, -4) {};

                \node (e1) at (3.3, .1) {};
                \node (e2) at (6.7, -2.1) {};
       
               \draw (U1) -- (V1); \draw (U1) -- (U2); \draw (V2) -- (V1); \draw (V2) -- (M12); \draw (M2) -- (U22);
               
               \draw (M3N1) -- (W2); \draw (M3N1) -- (U1); \draw (M1N1) -- (U1); \draw (M1N1) -- (W1); \draw (M4N1) -- (W1);
               \draw (M4N1) -- (V2); \draw (M2N2) -- (V2); \draw (M2N1) -- (W22);
               
               \node at (6,-4) { $(G^1,c^1) \times (\fracture{H^1}{\rho},c_\rho)$};
            \end{scope}
         \end{tikzpicture}
        \caption{Depiction of the Tensor product of the $H^1$-coloured graphs $(G^1,c^1)$ and  $(\fracture{H^1}{\rho},c_\rho)$.} 
        \label{fig:main_tensor_subs}
    \end{figure}

\begin{lemma}\label{lem:main_tensor_subs}
Let $r\geq 0$ be a constant non-negative integer, let $H$ be a $k$-edge graph without isolated vertices, and let $(G,c)$ be an $H$-coloured graph with $n$ vertices. Let $\rho$ be a fracture of~$H^r$. Then the tensor product  
$(G^r,c^r) \times (\fracture{H^r}{\rho},c_\rho)$
is a subgraph of the $r$-subdivision of a complete graph of order $O(k n)$.
\end{lemma}

The constant hidden in the $O()$ in Lemma~\ref{lem:main_tensor_subs} may depend on the fixed integer~$r$, but it does not otherwise depend on~$H$, $k$, $G$, $c$, or $\rho$.



\begin{proof}
Let $T$ be the tensor product 
$T:=(G^r,c^r) \times (\fracture{H^r}{\rho},c_\rho)$.
The construction of~$T$ is illustrated in Figure~\ref{fig:main_tensor_subs}.
The lemma follows immediately from Claims~1, 2, and 3 below.

\noindent{\bf Claim 1.} $|V(T)| = O(k n)$.
Claim~1 follows immediately from the fact that  $G^r$ is a subgraph of the $r$-subdivision of the complete graph~$K_n$.  
 
\noindent{\bf Claim 2.}
 Let $x$ and $y$ be distinct vertices of~$T$, each  with degree at least $3$. Then the length of any simple path from $x$ to $y$ is multiple of $r+1$.

Next we prove Claim~2.
Recall that $T$ is $H^r$-coloured via the colouring $\hat{c}$ from Definition~\ref{def:tensor} and that $V(H^r)$ can be partitioned into $V(H)$ and a set $S$ of $k r$ fresh subdivision vertices. Let $(u,v)$ be a vertex of $T$ such that $\hat{c}(u,v) = s\notin V(H)$, that is, $(u,v)$ is coloured with a subdivision vertex $s$. 
    
We will first show that $(u,v)$ has degree at most $2$ in~$T$.   To this end, let $s_1$ and $s_2$ be the two neighbours of $s$ in $H^r$.  By the construction of $(G^r,c^r)$, $u$ must have 
exactly two neighbours $u_1$ and $u_2$ in~$G^r$. Furthermore, $c^r(u_1)= s_1$ and $c^r(u_2)=s_2$.  Since $s$ has degree $2$ in~$H^r$, there are only two possibilities for $\rho_s$.
\begin{itemize}
\item  Case 1: $\rho_s=\{B\}$ where $B$ is the block $\{\{s,s_1\},\{s,s_2\}\}$: In this case $s^B$ is the only vertex of $\fracture{H}{\rho}$ that is coloured by $c_\rho$ with $s$. Since $\hat{c}(u,v) = s$ implies $c_\rho(v)=s$, we conclude that $v=s^B$. Hence $(u,v)$ has exactly two neighbours in~$T$,  $(u_1,s_1^{B_1})$ and $(u_2,s_2^{B_2})$, where $B_1$ and $B_2$ are the blocks of $\rho_{s_1}$ and $\rho_{s_2}$ that contain the edges $\{s,s_1\}$ and $\{s,s_2\}$, respectively.
\item Case 2: $\rho_s=\{B,B'\}$ where $B$ is the block 
$B=\{\{s,s_1\}\}$ and $B'$ is the block $B'=\{\{s,s_2\}\}$.
In this case,   $s^B$ and $s^{B'}$ are the only two vertices of $\fracture{H}{\rho}$ that are coloured by $c_\rho$ with $s$. Since $\hat{c}(u,v) = s$ implies $c_\rho(v)=s$, we conclude that  $v\in \{s^B,s^{B'}\}$. Suppose wlg that $v=S^B$ (the other case is symmetric).  Then the only neighbour of~$(u,v)$ in~$T$ is   $(u_1,s_1^{B_1})$, where $B_1$ is the block of $\rho_{s_1}$ that contains the edge $\{s,s_1\}$.
    \end{itemize}
    
After considering the two cases, we conclude that the only vertices $(u,v)$ of degree at least $3$ in $T$  satisfy   $\hat{c}(u,v) \in V(H)$, implying that $c^r(u)\in V(H)$ and thus, by the definition of $c^r$,  that $u\in V(G)$ so $u$ is not a subdivision vertex. 

Claim~2 follows since the length of every simple path between two non-subdivision vertices $u_1$ and $u_2$ in $G^r$ is a multiple of $(r+1)$, and since $T$ can be obtained from $(G^r,c^r)$ by splitting vertices.
This concludes the proof of Claim 2. The lemma is immediate from
Claims~1, 2 and 3.

{\bf Claim 3.} 
Let $F$ be a graph such that the following holds: For every pair of vertices $u,v\in V(F)$ with degree at least $3$, the length of any simple path from $u$ to $v$ is a multiple of $(r+1)$. Then $F$ is a subgraph of the $r$-subdivision of a complete graph of order $O(|V(F)|)$.
  
We conclude the proof of the Lemma by proving Claim~3. 
We say that a path~$P$ in~$F$ is ``extendable'' if its internal vertices have degree~$2$, one endpoint $s_P$
(called its ``startpoint'') has degree~$1$ and the other endpoint has degree at least~$3$. 
If $P$ has length $\ell_P$, 
then its ``entension length'' is the smallest non-negative integer~$\ell'_P$ such that $\ell_P+\ell'_P$ is a multiple of~$r+1$.
Let $F'$ be the graph formed from~$F$ by considering 
every extendable path~$P$ and adding a new length-$\ell'_P$ path from $s_P$ (adding $\ell'_P$ fresh vertices to make up this path). Clearly, $F$ is a sub-graph of~$F'$. 

By construction, the graph $F'$ has the following property: For every pair of non-isolated vertices $u'$ and $v'$ of $F'$, if both $u'$ and $v'$ have degree not equal to $2$, then the length of every simple path from $u'$ to $v'$ is a multiple of $(r+1)$.
    
We conclude that $F'$ is a subgraph of the $r$-subdivision of the complete graph of order at most $O(|V(F')|) =  O(|V(F)|)$ (since $r$ is a constant).  Since $F$ is a subgraph of $F'$, 
this concludes the proof of Claim~3 and hence the proof of the lemma. \end{proof}

Towards proving hardness of $\#\textsc{Match}(\mathcal{G})$, we will first consider an edge-coloured intermediate problem: 
\begin{definition}[$\#\textsc{ColMatch}(\mathcal{G})$]
Let $\mathcal{G}$ be a class of graphs. The problem $\#\textsc{ColMatch}(\mathcal{G})$ asks, on input a positive integer $k$ and a graph $G\in\mathcal{G}$ the edges of which are coloured with $k$ distinct colours, to compute the number of \emph{colourful} $k$-matchings in $G$, that is, the number of $k$-matchings containing each edge-colour precisely once. The problem is parameterised by $k$.
\end{definition}

\begin{lemma}\label{lem:main_colmatch}
Let $\mathcal{G}$ be a monotone somewhere dense class of graphs. Then the problem $\#\textsc{ColMatch}(\mathcal{G})$ is $\#\mathsf{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(k)\cdot |G|^{o(k/\log k)}$ for any function $f$.
\end{lemma}
\begin{proof}
    Since $\mathcal{G}$ is monotone and somewhere dense we can apply Lemma~\ref{lem:nd_subdivisions} to obtain $r\in\mathbb{N}_0$ such that for every graph $G$ we have that $G^r\in\mathcal{G}$.

    Let $\mathcal{H}$ be a class of $3$-regular expander graphs. We will reduce from $\#\text{\sc{cp-Hom}}(\mathcal{H}\to {\mathcal{U}})$. We note that both treewidth and the number of edges of $3$-regular expanders grow linearly in the number of vertices~(see e.g.\ \cite{GroheM09}), that is, for $H\in\mathcal{H}$ we have $|E(H)|\in\Theta(|V(H)|)$ and $\mathsf{tw}(H)\in \Theta(|V(H)|)$. Consequently, Theorems~\ref{thm:cphomshard} and~\ref{thm:cybt} imply that $\#\text{\sc{cp-Hom}}(\mathcal{H}\to {\mathcal{U}})$ is $\#\mathsf{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(|H|)\cdot |G|^{o(|H|/\log |H|)}$ for any function $f$.
    
    For our reduction, let $H\in\mathcal{H}$ and $(G,c)$ be a given input of $\#\text{\sc{cp-Hom}}(\mathcal{H}\to {\mathcal{U}})$. We start by constructing $H^r$ and $(G^r,c^r)$ --- note that this can clearly be done in polynomial time. Furthermore, setting $k:=|E(H^r)|$ we have that $k\in O(|H|)$ since $r$ is a constant.
    Now, by Lemma~\ref{lem:hom_subdiv}, we have
    \[\#\homs{(H,\mathsf{id}_H)}{(G,c)}=\#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}\,.\]
    For what follows, we view surjectively $H^r$-coloured graphs $(\Tilde{G},\Tilde{c})$ also as $k$-edge-coloured graphs: Any edge $e=\{u,v\}$ is mapped to the colour $\{\Tilde{c}(u),\Tilde{c}(v)\}$. This allows us to invoke the results of~\cite{RothSW21Icalp} and we obtain the following:\footnote{In the terminology of~\cite{RothSW21Icalp}, the number of colourful $k$-matchings in a $k$-edge-coloured graph $\hat{G}$ is denoted by $\#\coledgesubs{\Phi,k}{\hat{G}}$, where $\Phi$ is the graph property of being a matching. The identities (\ref{eq:main_subs_1}) and (\ref{eq:main_subs_2}) are then immediate consequences of Lemma~3.1 and Corollary~3.3 in the full version~\cite{RothSW21Arxiv} of~\cite{RothSW21Icalp}.}
    
    There is a unique function $a$ from fractures of $H^r$ to rationals 
    such that, for every surjectively $H^r$-coloured graph $(\Tilde{G},\Tilde{c})$, the number of edge-colourful $k$-matchings of $(\Tilde{G},\Tilde{c})$ is equal to
    \begin{equation}\label{eq:main_subs_1}
        \sum_\rho a(\rho)\cdot \#\homs{(\fracture{H^r}{\rho},c_\rho)}{(\Tilde{G},\Tilde{c})}\,,
    \end{equation}
    where the sum is over all fractures of $H^r$. Additionally, $a$ satisfies
    \begin{equation}\label{eq:main_subs_2}
       a(\top) =  \prod_{v\in V(H^r)} (-1)^{\mathsf{deg}(v)-1} \cdot (\mathsf{deg}(v)-1)! \,,
    \end{equation}
    where $\top$ is the coarsest fracture, that is, for each $v\in V(H^r)$ the partition $\top_v$ only contains a singleton block (and therefore $\fracture{H^r}{\top}=H^r$). In particular, it is easy to see that \[a(\top)=\pm 2^{|V(H)|}\neq 0\,.\]
    
    Now, in the reduction, we wish to query our oracle to obtain the number of edge-colourful $k$-matchings in the graphs $(G^r,c^r) \times (\fracture{H^r}{\sigma},c_\sigma)$ for each fracture $\sigma$ of $H^r$. However, since our oracle is for $\#\textsc{ColMatch}(\mathcal{G})$ we are only allowed to pose queries the (underlying uncoloured) graphs of which are contained in $\mathcal{G}$. Fortunately, we can rely on Lemma~\ref{lem:main_tensor_subs} which asserts that all those graphs are subgraphs of the $r$-subdivision of a complete graph. Our choice of $r$ and the fact that $\mathcal{G}$ is monotone (see Lemma~\ref{lem:nd_subdivisions}) makes sure that all those graphs are indeed contained in $\mathcal{G}$. 
    
    Consequently, using our oracle and (\ref{eq:main_subs_1}), we can obtain for each fracture $\sigma$ of $H^r$ the term
    \begin{align*}
        ~&\sum_\rho a(\rho)\cdot \#\homs{(\fracture{H^r}{\rho},c_\rho)}{(G^r,c^r) \times (\fracture{H^r}{\sigma},c_\sigma)} \\
        =&\sum_\rho a(\rho)\cdot \#\homs{(\fracture{H^r}{\rho},c_\rho)}{(G^r,c^r)} \cdot \#\homs{(\fracture{H^r}{\rho},c_\rho)}{(\fracture{H^r}{\sigma},c_\sigma)}\,,
    \end{align*}
    where the equality holds by the linearity of the Tensor product of $H^r$-coloured graphs (see Lemma~\ref{lem:tensor_linear_subgraphs}).
    Setting $\mathsf{coeff}(\rho):=a(\rho)\cdot \#\homs{(\fracture{H^r}{\rho},c_\rho)}{(G^r,c^r)}$, we observe that this constitutes a system of linear equations with coefficients $\mathsf{coeff}(\rho)$ and with matrix $M_{H^r}$ (\ref{eq:MHdef}). By Lemma~\ref{lem:MH_nonsingular} we have that $M_H$ is non-singular and thus we can solve the system and obtain, in particular, the coefficient
    \[\mathsf{coeff}(\top) =a(\top)\cdot \#\homs{(\fracture{H^r}{\top},c_\top)}{(G^r,c^r)} = a(\top)\cdot \#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)} \,.\]
    Finally, since $a(\top)\neq 0$, we can divide by $a(\top)$ and recover $\#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}$ as desired. This concludes the proof.
\end{proof}

Obtaining the same result for the uncoloured version of counting $k$-matchings is an easy consequence.
\begin{theorem}\label{thm:main_matchings}
Let $\mathcal{G}$ be a monotone somewhere dense class of graphs. Then the problem $\#\textsc{Match}(\mathcal{G})$ is $\#\mathsf{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(k)\cdot |G|^{o(k/\log k)}$ for any function $f$.
\end{theorem}
\begin{proof}
The lower bounds hold for $\#\textsc{ColMatch}(\mathcal{G})$ as shown in the previous lemma. Now, reducing counting edge-colourful $k$-matchings to counting (uncoloured) $k$-matchings follows by a well-known and straight-forward application of the principle of inclusion and exclusion (see, for instance, \cite[Lemma~1.34]{Curticapean15}). We emphasize that the obtained reduction only requires oracle queries for subgraphs of the input graph, hence it is admissible in our setting (as $\mathcal{G}$ is monotone) and we obtain 
\[\#\textsc{ColMatch}(\mathcal{G}) \leq^{\mathsf{FPT}} \#\textsc{Match}(\mathcal{G}) \,,\]
which yields $\#\mathrm{W}[1]$-hardness. Finally, the reduction does not change the parameter $k$, hence the conditional lower bound under ETH transfers to the uncoloured setting as well.
\end{proof}

We present two immediate corollaries.

\begin{corollary}[Theorem~\ref{thm:intro_match}, restated]\label{xxx}
Let $\mathcal{G}$ be a monotone class of graphs and assume that ETH is true. Then $\#\textsc{Match}(\mathcal{G})$ is fixed-parameter tractable if and only if $\mathcal{G}$ is nowhere dense. In particular, if $\mathcal{G}$ is nowhere dense, the problem can be solved in time $f(k)\cdot|V(G)|^{1+o(1)}$ for some computable function~$f$. Otherwise, there is no function $f$ for which the problem can be solved in time $f(k)\cdot |G|^{o(k/\log k)}$. 
\end{corollary}
\begin{proof}
    Follows by Theorem~\ref{thm:sparsity} and Theorem~\ref{thm:main_matchings}.
\end{proof}

Corollary~\ref{xxx} cannot be strengthened to achieve polynomial time tractability of $\#\textsc{Match}(\mathcal{G})$ for nowhere dense and monotone $\mathcal{G}$, unless $\#\mathrm{P}=\mathrm{P}$: It was recently shown by Curticapean and Xia that counting perfect matchings (i.e., $k=n/2$-matchings) in $K_8$-minor-free graphs\footnote{The class of $K_8$-minor-free graphs is clearly monotone, but also nowhere dense by Lemma~\ref{lem:nd_subdivisions}: Clearly it does not contain the $r$-subdivisions of cliques larger than $7$.} is $\#\mathrm{P}$-hard~\cite{CurticapeanX22}.

\begin{corollary}[Theorem~\ref{thm:subs_monotone_intro}, restated]
Let $\mathcal{H}$ and $\mathcal{G}$ be monotone graph classes and assume that ETH is true. Then $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is fixed-parameter tractable if and only if $\mathcal{H}$ is of bounded matching number or $\mathcal{G}$ is nowhere dense. Otherwise, the problem is $\#\mathrm{W}[1]$-complete and cannot be solved in time \[f(|V(H)|)\cdot |G|^{o(|V(H)|/ \log(|V(H)|))}\]
for any function $f$.
\end{corollary}
\begin{proof}
   Fixed-parameter tractability for bounded matching number of $\mathcal{H}$ follows by the dichotomy result of Curticapean and Marx~\cite{CurticapeanM14} (and, implicitly, from earlier work of Williams and Williams~\cite{WilliamsW13}). Fixed-parameter tractability for nowhere dense $\mathcal{G}$ holds by Theorem~\ref{thm:sparsity}. Finally, if $\mathcal{H}$ is monotone and of unbounded matching number it must contain all matchings and thus $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is a generalisation of $\#\textsc{Match}(\mathcal{G})$. If $\mathcal{G}$ is somewhere dense, the lower bounds holds for $\#\textsc{Match}(\mathcal{G})$  as shown in Theorem~\ref{thm:main_matchings}.
\end{proof}

In the next step, our goal is to extend and refine the above dichotomy to \emph{hereditary} pattern classes $\mathcal{H}$. To this end, let us recall the following invariants (see Definition~\ref{def:invariants}):
\begin{itemize}
    \item $\omega(G)$ denotes the clique number of $G$
    \item $\beta(G)$ denotes the biclique number of $G$.
    \item $\beta_{\mathsf{ind}}(G)$ denotes the induced biclique number of $G$.
    \item ${\mathrm{m}}(G)$ denotes the matching number of $G$.
    \item $\m_{\mathsf{ind}}(G)$ denotes the induced matching number of $G$.
\end{itemize}

 \begin{table}[t]
    \begin{tabularx}{\textwidth}{l|cccc}
          \begin{tabular}{c}
             $~$
        \end{tabular}&\begin{tabular}{c}
             $\mathcal{G}$
             n.\ dense
        \end{tabular} &\begin{tabular}{c}
             $\mathcal{G}$
             s.\ dense\\
             $\omega(\mathcal{G})=\infty$
        \end{tabular}& \begin{tabular}{c}
             $\mathcal{G}$
             s.\ dense\\
             $\omega(\mathcal{G})< \infty$\\  
             ${\beta}(\mathcal{G})=\infty$
        \end{tabular}&\begin{tabular}{c}
             $\mathcal{G}$
             s.\ dense\\
             $\omega(\mathcal{G})< \infty$\\ 
             ${\beta}(\mathcal{G})< \infty$
        \end{tabular}\\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
             ${\mathrm{m}}(\mathcal{H})< \infty$
        \end{tabular} & P & P & P & P \\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
             $\m_{\mathsf{ind}}(\mathcal{H})= \infty$
        \end{tabular} & FPT & hard & hard & hard \\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
            $\m_{\mathsf{ind}}(\mathcal{H})< \infty$\\
            $\beta_{\mathsf{ind}}(\mathcal{H})= \infty$
        \end{tabular} & P & hard$^\dagger$ & hard$^\dagger$ & P \\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
             $\m_{\mathsf{ind}}(\mathcal{H}),\beta_{\mathsf{ind}}(\mathcal{H})< \infty$\\
            $\omega(\mathcal{H})=\infty$
        \end{tabular} & P & hard$^\dagger$ & P & P 
        \end{tabularx}
     \caption[caption]{\small The complexity of $\#\textsc{Sub}(\mathcal{H}\to \mathcal{G})$ for hereditary $\mathcal{H}$ and monotone $\mathcal{G}$. The entries P and FPT stand for polynomial-time tractability and fixed-parameter tractability, respectively. The entry ``hard'' implies both, $\#\mathrm{W}[1]$-hardness as well as the absence of an algorithm running in time $f(k)\cdot n^{o(k/ \log(k))}$ for any function $f$, unless ETH fails. Here $k$ denotes the number of vertices of the pattern, and $n$ denotes the size of the host.\\
     Note that the cases for $\mathcal{G}$ and $\mathcal{H}$ are exhaustive: This is immediate for $\mathcal{G}$. For $\mathcal{H}$, exhaustiveness follows from the fact that ${\mathrm{m}}(\mathcal{H})=\infty$ implies that at least one of $\m_{\mathsf{ind}}(\mathcal{H})$, $\beta_{\mathsf{ind}}(\mathcal{H})$ and $\omega(\mathcal{H})$ must be unbounded as well (see Theorem~\ref{thm:ramsey_match}).\\
     Finally, we point out that the unique fixed-parameter tractability result in 
    
the table     
     is a ``real FPT'' case: Unless $\mathrm{P}=\#\mathrm{P}$ it cannot be strengthened to yield polynomial-time tractability (Remark~\ref{rem:realFPT}).\\
     $~$\\
     \footnotesize{$\dagger$ Tight conditional lower bound: Not solvable in time $f(k)\cdot n^{o(k)}$, unless ETH fails.}}
      \label{tab:resultsSubsHereditary}
\end{table}

\begin{theorem}[Theorem~\ref{thm:subs_hereditary_intro}, restated]
Let $\mathcal{H}$ and $\mathcal{G}$ be graph classes such that $\mathcal{H}$ is hereditary and $\mathcal{G}$ is monotone. Then the complexity of $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$ is exhaustively classified as shown in Table~\ref{tab:resultsSubsHereditary}.
\end{theorem}
\begin{proof}
    The first row is due to Curticapean and Marx~\cite{CurticapeanM14}, and the FPT result in the first column follows from Theorem~\ref{thm:sparsity}. 
    The intractability results in the second row follow from Theorem~\ref{thm:main_matchings} and the fact that $\m_{\mathsf{ind}}(\mathcal{H})=\infty$ implies that $\mathcal{H}$ contains all matchings (since it is hereditary).
    For the second column, we observe that $\omega(\mathcal{G})=\infty$ and $\mathcal{G}$ being monotone implies that $\mathcal{G}$ is, in fact, the class of all graphs. Hence the second column is also a consequence of the dichotomy of Curticapean and Marx~\cite{CurticapeanM14}.\footnote{\label{fn:2}The tight conditional lower bounds in the second column follow from the fact that the respective entries subsume counting $k$-cliques in arbitrary graphs, and counting $k$-by-$k$ bicliques in bipartite graphs. The tight bound of the former was shown in~\cite{Chenetal05,Chenetal06}, and the tight bound of the latter was implicitly shown in~\cite{CurticapeanM14}, and explicitly in~\cite{DorflerRSW22}; while~\cite{DorflerRSW22} studies \emph{induced} subgraphs in bipartite graphs, we note that all bicliques in a bipartite graph must be induced.}
    
In the rest of this proof 
we discuss the remaining entries
\begin{itemize}
    \item the four entries in the bottom right corner of the table, and
    \item the last two entries in the first column
\end{itemize}

  
 
{\noindent \bf Entry in Row 3, Column 3:
If ${\beta(\mathcal{G})}=\beta_{\mathsf{ind}}(\mathcal{H})=\infty$, then $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$ is hard.}
The proof is as follows. 
Since $\mathcal{H}$ is hereditary, it  contains all bicliques. Since $\mathcal{G}$ is monotone, it contains all bipartite graphs. Hence $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$ is at least as hard as counting $k$-by-$k$ bicliques in bipartite graphs, which is known to be hard~\cite{CurticapeanM14}.\footnote{See Footnote~\ref{fn:2} for the tight conditional lower bound.}

{\noindent \bf Entry in Row 3, Column 4:
If $\m_{\mathsf{ind}}(\mathcal{H})$, $\omega(\mathcal{G})$, and $\beta(\mathcal{G})$ are all bounded, then $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$ is solvable in polynomial time.} 
The proof is as follows.
Let $\omega_G$, and $\beta_G$ be the constant bounds on $\omega(\mathcal{G})$, and ${\beta}(\mathcal{G})$, respectively.
    Let $H\in\mathcal{H}$ and $G\in\mathcal{G}$ be the input of $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$. If $\omega(H)>\omega_G$ then we output $0$. Similarly, if $\beta_{\mathsf{ind}}(H)>{\beta}_G$, we can output $0$. Hence assume that $\omega(H)\leq \omega_G$ and $\beta_{\mathsf{ind}}(H)\leq {\beta}_G$.
    Now, by Theorem~\ref{thm:ramsey_match}, there is a (monotonically increasing) function $R$ such that the matching number of $H$ is bounded from above by $R(\m_{\mathsf{ind}}(H),\omega(H),\beta_{\mathsf{ind}}(H))$. Thus,  
    \[{\mathrm{m}}(H) \leq R(\m_{\mathsf{ind}}(H),\omega(H),\beta_{\mathsf{ind}}(H)) \leq R(\m_{\mathsf{ind}}(H),\omega_G,\beta_G) = O(1) \,.\]
    Hence we can 
solve $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$
using the polynomial-time algorithm for patterns of bounded matching number in~\cite{CurticapeanM14}.
 
 
{\noindent \bf Entries in Row 4, Columns 3 and 4:
If $\m_{\mathsf{ind}}(\mathcal{H})$, $\beta_{\mathsf{ind}}(\mathcal{H})$, and $\omega(\mathcal{G})$ are all bounded, then $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$ is solvable in polynomial time. }
The proof is as follows.
Let $\omega_G$ be the constant bound on $\omega(\mathcal{G})$. Let $H\in\mathcal{H}$ and $G\in\mathcal{G}$ be the input of $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$. If $\omega(H)>\omega_G$ then we output $0$. Hence assume that $\omega(H)\leq \omega_G$ and
therefore, similarly to the previous case,
\[{\mathrm{m}}(H) \leq R(\m_{\mathsf{ind}}(H),\omega(H),\beta_{\mathsf{ind}}(H)) \leq R(\m_{\mathsf{ind}}(H),\omega_G,\beta_{\mathsf{ind}}(H)) \in O(1) \,,\]
allowing us to 
solve $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$
using the polynomial-time algorithm for patterns of bounded matching number in~\cite{CurticapeanM14}.
 
{\noindent \bf Entries in Rows 3 and 4 of Column 1. In these cases $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$ can be solved in polynomial time.
} 
In these cases we first show that 
$\omega(\mathcal{G})$ and $\beta(\mathcal{G})$  are bounded.
Then the 
same arguments that were used in Rows~3 and~4 of
Column~4 apply.
We use proof-by-contradiction
to show that 
$\omega(\mathcal{G})$ and $\beta(\mathcal{G})$  are bounded.
We start with the observation
that $\mathcal{G}$ is monotone.
Thus, if $\omega(\mathcal{G})$ is unbounded, then $\mathcal{G}$  contains (the $0$-subdivisions of) every clique.
Also, if $\beta(\mathcal{G})$ is unbounded, then $\mathcal{G}$ contains all bipartite graphs and thus the $1$-subdivisions of every clique. In both cases, Lemma~\ref{lem:nd_subdivisions} would imply that $\mathcal{G}$ is somewhere dense, contradicting the fact that it is nowhere dense.
\end{proof}

We conclude this section with the following remark.
\begin{remark}\label{rem:realFPT}
Let $\mathcal{H}$ and $\mathcal{G}$ be the classes of graphs of degrees bounded by $2$ and $3$, respectively. Then $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$ subsumes the $\#\mathrm{P}$-hard problem of counting Hamiltonian cycles in $3$-regular graphs. Since both classes are monotone (and thus also hereditary), since $\m_{\mathsf{ind}}(\mathcal{H})=\infty$, and since classes of bounded degree graphs are nowhere dense (see e.g.\ \cite{GroheKS17}), this shows that the unique FPT entry in Table~\ref{tab:resultsSubsHereditary} cannot be strengthened to polynomial-time tractability, unless $\#\mathrm{P}=\mathrm{P}$.
\end{remark}






\section{Counting Induced Subgraphs}
While we relied on fractured graphs in Section~\ref{sec:subgraphs}, our classification for counting induced subgraphs will rely on
subgraphs induced by sets of edges.
Given a graph $F$ and a set $A \subseteq E(F)$ 
we use $F[A]$ for the graph with vertex set $V(F)$ and edge set~$A$. For what follows, observe that for any subset $A\subseteq E(F)$,
the identity function on $V(F)$, which we denote by~$\mathsf{id}_F$, is a surjective $F$-colouring of $F[A]$. Given a class of graphs $\mathcal{G}$, the problem $\#\textsc{IndSet}(\mathcal{G})$ asks, on input a positive integer $k$ and a graph $G\in \mathcal{G}$, to compute the number of independent sets of size $k$ (also called $k$-\emph{independent sets}) in $G$.
We start with the following simple variation of Lemma~\ref{lem:main_tensor_subs} that applies to 
subgraphs induced by sets of edges (rather than to fractured graphs). 


\begin{lemma}\label{fact:main_tensor_es}
Let $r\geq 0$ be a constant non-negative integer, let $H$ be a $k$-edge graph without isolated vertices, and let $G$ be an $H$-coloured graph with $n$ vertices. Let $A$ be a subset of $E(H^r)$. Then the tensor product $(G^r,c^r) \times (H^r[A],\mathsf{id}_{H^r})$
is a subgraph of the $r$-subdivision of a complete graph.
\end{lemma}
\begin{proof}
Note first that $(G^r,c^r) \times (H^r,\mathsf{id}_{H^r})=(G^r,c^r)$, which is by construction a subgraph of the $r$-subdivision of $K_n$. Finally, for every $A\subseteq E(H^r)$, the graph $(G^r,c^r) \times (H^r[A],\mathsf{id}_{H^r})$ is obtained from $(G^r,c^r) \times (H^r,\mathsf{id}_{H^r})$ by deleting edges --- specifically, for all edges $e=\{u,v\} \in E(H^r)\setminus A$, we delete from $G^r$ all edges between the vertices coloured (by $c^r$) with $u$ and the vertices coloured with $v$. Thus, $(G^r,c^r) \times (H^r[A],\mathsf{id}_{H^r})$ is a subgraph of the $r$-subdivision of $K_n$ as well.
\end{proof}

In case of counting (not necessarily induced) subgraphs, the problem of counting edge-colourful $k$-matchings, i.e., $\#\textsc{ColMatch}(\mathcal{G})$ was the key subproblem in our hardness proofs. In the current case of counting induced subgraphs, we will instead rely on the problem of counting vertex-colourful independent sets:

\begin{definition}[$\#\textsc{ColIndSet}(\mathcal{G})$]
Let $\mathcal{G}$ be a class of graphs. We define the problem $\#\textsc{ColIndSet}(\mathcal{G})$ which asks, on input a positive integer $k$ and a graph $G\in\mathcal{G}$ the vertices of which are coloured with $k$ distinct colours, to compute the number of \emph{colourful} $k$-independent sets in $G$, that is, the number of $k$-independent sets containing each vertex-colour precisely once. The problem is parameterised by $k$.
\end{definition}

Our goal is to show that $\#\textsc{ColIndSet}(\mathcal{G})$ is intractable whenever $\mathcal{G}$ is monotone and somewhere dense. To this end, our reduction will rely on solving a system of linear equations, the matrix of which is defined as follows: Let $H$ be a graph. We define a square matrix $N_H$ the rows and columns of which are indexed by the edge-subsets of $H$, and the entries of which satisfy
\begin{equation}\label{def:N_H}
    N_H[A,B] := \#\homs{(H[A],\mathsf{id}_H)}{(H[B],\mathsf{id}_H)}\,.
\end{equation}
Similarly to the matrix $M_H$ in the previous section, the following was established in prior work:
\begin{lemma}[\cite{DorflerRSW22}]\label{lem:N_H_triangular}
For each graph $H$, the matrix $N_H$ is non-singular.
\end{lemma}

We are now able to proceed by establishing intractability of $\#\textsc{ColIndSet}(\mathcal{G})$.

\begin{lemma}
Let $\mathcal{G}$ be a monotone somewhere dense class of graphs class. Then 
$\#\textsc{ColIndSet}(\mathcal{G})$ is $\#\mathsf{W}[1]$-complete and, assuming ETH, cannot be solved in time $f(k)\cdot |G|^{o(k/\log k)}$ for any function $f$.
\end{lemma}
\begin{proof}
The set-up for the proof is similar to that of Lemma~\ref{lem:main_colmatch}: First, using that $\mathcal{G}$ is monotone and somewhere dense, we obtain by Lemma~\ref{lem:nd_subdivisions} a constant $r\in\mathbb{N}_0$ such that for every graph $G$, the graph $G^r$ is contained in $\mathcal{G}$. 
Second, we let $\mathcal{H}$ be a class of $3$-regular expander graphs and we reduce from $\#\text{\sc{cp-Hom}}(\mathcal{H} \to {\mathcal{U}})$, which, by Theorems~\ref{thm:cphomshard} and~\ref{thm:cybt}, is $\#\mathrm{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(|H|)\cdot |G|^{o(|H|/\log |H|)}$ for any function $f$.
Third, given as input $H\in \mathcal{H}$ and $(G,c)$, our reduction proceeds by constructing $H^r$, $G^r$, and $c^r$ which, by Lemma~\ref{lem:hom_subdiv} satisfy
\[\#\homs{(H,\mathsf{id}_H)}{(G,c)}=\#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}\,.\]

At this point, the strategy of the proof diverges from the proof of Lemma~\ref{lem:main_colmatch}. First, we set $k=|V(H^r)|$ and observe that $k\in O(|H|)$ since $r$ is a constant. Our goal is to use the oracle for $\#\textsc{ColIndSet}(\mathcal{G})$ to compute $\#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)}$. To avoid confusion, we emphasize that we view surjectively $H^r$-coloured graphs $(\Tilde{G},\Tilde{c})$ also as $k$-vertex coloured graphs with colouring $\Tilde{c}$ in the remainder of the proof. This allows us to invoke~\cite[Lemma 8]{DorflerRSW22} and we obtain the following:\footnote{In the terminology of~\cite{DorflerRSW22}, the number of colourful $k$-independent sets in a surjectively $H^r$-coloured graph $\hat{G}$ is denoted by $\#\mathsf{cp}\text{-}\mathsf{IndSub}(\Phi \to_{H^r} \hat{G})$, where $\Phi$ is the graph property of being an independent set.}

There is a unique function $\hat{a}$ from edge-subsets of $H^r$ to rationals such that for every surjectively $H^r$-coloured graph $(\Tilde{G},\Tilde{c})$, the number of vertex-colourful $k$-independent sets in $(\Tilde{G},\Tilde{c})$ is equal to
\begin{equation}\label{eq:colIS1}
    \sum_A \hat{a}(A) \cdot \#\homs{(H^r[A],\mathsf{id}_{H^r})}{(\Tilde{G},\Tilde{c})}\,,
\end{equation}
where the sum is over all subsets of edges of $H^r$. Additionally $\hat{a}$ satisfies  
\begin{equation}\label{eq:colIS2}
    \hat{a}(E(H^r)) = \pm \hat{\chi} \neq 0\,, 
\end{equation}
where $\hat{\chi}$ is the so-called alternating enumerator for the graph property of being an independent set --- we omit the definition since the only property needed for $\hat{\chi}$ is it being easily computable and non-zero (see~\cite{DorflerRSW22}).

Now, in the main step of the reduction, we wish to query our oracle to obtain the number of vertex-colourful $k$-independent sets in the graphs $(G^r,c^r) \times (H^r[B],\mathsf{id}_{H^r})$ for each edge-subset $B\subseteq E(H^r)$ of $H^r$. However, since our oracle is for $\#\textsc{ColIndSet}(\mathcal{G})$ we are only allowed to pose queries the (underlying uncoloured) graphs of which are contained in $\mathcal{G}$. Fortunately, we can rely on Lemma~\ref{fact:main_tensor_es} which asserts that all those graphs are subgraphs of the $r$-subdivision of a complete graph. Our choice of $r$ and the fact that $\mathcal{G}$ is monotone (see Lemma~\ref{lem:nd_subdivisions}) makes sure that all those graphs are indeed contained in $\mathcal{G}$. 

Consequently, using our oracle and (\ref{eq:colIS1}), we can obtain for each edge-subset $B$ of $H^r$ the term
    \begin{align*}
        ~&\sum_A \hat{a}(A)\cdot \#\homs{(H^r[A],\mathsf{id}_{H^r})}{(G^r,c^r) \times (H^r[B],\mathsf{id}_{H^r})} \\
        =&\sum_A \hat{a}(A)\cdot \#\homs{(H^r[A],\mathsf{id}_{H^r})}{(G^r,c^r)} \cdot \#\homs{(H^r[A],\mathsf{id}_{H^r})}{(H^r[B],\mathsf{id}_{H^r})}\,,
    \end{align*}
    where the equality holds by the linearity of the tensor product of $H^r$-coloured graphs (see Lemma~\ref{lem:tensor_linear_subgraphs}).
    Similarly to the proof of Lemma~\ref{lem:main_colmatch}, this induces a system of linear equations. The corresponding matrix is $N_{H^r}$ which is non-singular by Lemma~\ref{lem:N_H_triangular}. Since $\hat{a}(E(H^r))\neq 0$~(\ref{eq:colIS2}), solving this system enables us to compute 
    \[\#\homs{(H^r[E(H^r)],\mathsf{id}_{H^r})}{(G^r,c^r)} =\#\homs{(H^r,\mathsf{id}_{H^r})}{(G^r,c^r)} \,,\]
    concluding the proof.
\end{proof}


\begin{theorem}\label{thm:main_is}
Let $\mathcal{G}$ be a monotone somewhere dense class of graphs. Then the problem $\#\textsc{IndSet}(\mathcal{G})$ is $\#\mathsf{W}[1]$-hard and, assuming ETH, cannot be solved in time $f(k)\cdot |G|^{o(k/\log k)}$ for any function $f$.
\end{theorem}
\begin{proof}
Similar to the proof of Theorem~\ref{thm:main_matchings}: The known reduction from counting vertex-colourful $k$-independent sets to counting (uncoloured) $k$-independent sets via inclusion-exclusion (see, for instance, \cite[Lemma~1.34]{Curticapean15}) only requires oracle queries for subgraphs of the input graph. The theorem thus follows since $\mathcal{G}$ is monotone and somewhere dense and since $\#\textsc{ColIndSet}(\mathcal{G})$ is hard by the previous lemma.
\end{proof}

We present two immediate corollaries.

\begin{corollary}[Theorem~\ref{thm:intro_is}, restated]\label{xxxIS}
Let $\mathcal{G}$ be a monotone class of graphs and assume that ETH is true. Then $\#\textsc{IndSet}(\mathcal{G})$ is fixed-parameter tractable if and only if $\mathcal{G}$ is nowhere dense. In particular, if $\mathcal{G}$ is nowhere dense, the problem can be solved in time $f(k)\cdot|V(G)|^{1+o(1)}$ for some computable function~$f$. Otherwise, there is no function $f$ for which the problem can be solved in time $f(k)\cdot |G|^{o(k/\log k)}$. 
\end{corollary}
\begin{proof}
    Follows by Theorem~\ref{thm:sparsity} and Theorem~\ref{thm:main_is}.
\end{proof}

Corollary~\ref{xxxIS} cannot be strengthened to achieve polynomial time tractability of the problem $\#\textsc{IndSet}(\mathcal{G})$ for nowhere dense and monotone $\mathcal{G}$, unless $\#\mathrm{P}=\mathrm{P}$: Clearly, there is a polynomial-time Turing-reduction from the $\#\mathrm{P}$-hard problem of counting independent sets in graphs of degree at most $3$~\cite{Greenhill00},   which constitutes a monotone and nowhere dense class of graphs.


\begin{corollary}
Let $\mathcal{H}$ and $\mathcal{G}$ be monotone graph classes and assume that ETH is true. Then $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ is fixed-parameter tractable if and only if $\mathcal{H}$ is finite or $\mathcal{G}$ is nowhere dense. Otherwise, the problem is $\#\mathrm{W}[1]$-complete and cannot be solved in time \[f(|V(H)|)\cdot |G|^{o(|V(H)|/ \log(|V(H)|))}\]
for any function $f$.
\end{corollary}
\begin{proof}
   The problem is clearly solvable in polynomial-time (and thus fixed-parameter tractable) if $\mathcal{H}$ is finite since the
   brute-force algorithm runs in time $|G|^{|H|}$.   
   Fixed-parameter tractability for nowhere dense $\mathcal{G}$ holds by Theorem~\ref{thm:sparsity}. Finally, if $\mathcal{H}$ is monotone and infinite, it contains all independent sets, and thus $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ is a generalisation of $\#\textsc{IndSet}(\mathcal{G})$. If $\mathcal{G}$ is somewhere dense, the lower bounds holds for $\#\textsc{IndSet}(\mathcal{G})$  as shown in Theorem~\ref{thm:main_is}.
\end{proof}

In the last part of the paper, we refine the previous corollary to hereditary classes of pattern graphs. To this end, we recall that $\omega$ denotes the clique number and $\alpha$ denotes the independence number.

\begin{table}[t]
   \begin{tabularx}{\textwidth}{l|ccc}
          \begin{tabular}{c}
             $~$
        \end{tabular}&\begin{tabular}{c}
             $\mathcal{G}$
             nowhere dense\\
             $~$
        \end{tabular} &\begin{tabular}{c}
             $\mathcal{G}$
             somewhere dense\\
             $\omega(\mathcal{G})=\infty$
        \end{tabular}& \begin{tabular}{c}
             $\mathcal{G}$
             somewhere dense\\
             $\omega(\mathcal{G})< \infty$ \&  
             ${\alpha}(\mathcal{G})=\infty$
        \end{tabular}\\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
             $\mathcal{H}$ finite
        \end{tabular} & P & P & P  \\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
             $\alpha(\mathcal{H})= \infty$
        \end{tabular} & FPT & \begin{tabular}{c}
             $\#\mathrm{W}[1]$-hard\\ not in $f(k)\cdot n^{o(k)}$
        \end{tabular} & \begin{tabular}{c}
             $\#\mathrm{W}[1]$-hard\\ not in $f(k)\cdot n^{o(k/\log k)}$
        \end{tabular}  \\
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \hline
        & \\[\dimexpr-\normalbaselineskip+5pt]
        \begin{tabular}{l}
            $\alpha(\mathcal{H})< \infty$\\
            $\omega(\mathcal{H})= \infty$
        \end{tabular} & P & \begin{tabular}{c}
             $\#\mathrm{W}[1]$-hard\\ not in $f(k)\cdot n^{o(k)}$
        \end{tabular} & P  
        \end{tabularx}
     \caption[caption]{\small The complexity of $\#\textsc{IndSub}(\mathcal{H}\to \mathcal{G})$ for hereditary $\mathcal{H}$ and monotone $\mathcal{G}$. The entries P and FPT stand for polynomial-time tractability and fixed-parameter tractability, respectively. The entry ``hard'' implies both, $\#\mathrm{W}[1]$-hardness as well as the absence of an algorithm running in time $f(k)\cdot n^{o(k/ \log(k))}$ for any function $f$, unless ETH fails. Here $k$ denotes the number of vertices of the pattern, and $n$ denotes the size of the host.
     Note that the cases for $\mathcal{G}$ and $\mathcal{H}$ are exhaustive by Ramsey's Theorem (see Theorem~\ref{thm:ramsey}).\\
     Finally, we point out that the unique fixed-parameter tractability result in the table     
     is a ``real FPT'' case: Unless $\mathrm{P}=\#\mathrm{P}$ it cannot be strengthened to yield polynomial-time tractability (following from the aforementioned $\#\mathrm{P}$-hardness result of counting independent sets in graphs of degree at most $3$).}
      \label{tab:resultsIndSubsHereditary}
\end{table}

\begin{theorem}[Theorem~\ref{thm:intro_is}, restated]
Let $\mathcal{H}$ and $\mathcal{G}$ be graph classes such that $\mathcal{H}$ is hereditary and $\mathcal{G}$ is monotone. Then the complexity of $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ is exhaustively classified as shown in Table~\ref{tab:resultsIndSubsHereditary}.
\end{theorem}
\begin{proof}
   The first row is trivial since $\mathcal{H}$ is finite and the brute-force algorithm applies. The FPT result follows from Theorem~\ref{thm:sparsity}. The intractability results in the second column hold since $\mathcal{G}$ being monotone and $\mathcal{G}=\infty$ imply that $\mathcal{G}$ is the set of all graphs. Thus, since $\mathcal{H}$ is hereditary, the cases $\alpha(\mathcal{H})=\infty$ and $\omega(\mathcal{H})=\infty$ subsume the problems of counting $k$-independent sets and $k$-cliques, respectively, in unrestricted host graphs. Both are canonical $\#\mathrm{W}[1]$-hard problems and cannot be solved in time $f(k)\cdot n^{o(k)}$, unless ETH fails~\cite{Chenetal05,Chenetal06}.\footnote{The lower bound in~\cite{Chenetal05,Chenetal06} applies to counting $k$-cliques, and we note that counting $k$-cliques and counting $k$-independent sets are interreducible by taking the complement of the host.}
   
   The intractability result in the last column follows from Theorem~\ref{thm:main_is} since $\mathcal{H}$ being hereditary and $\alpha(\mathcal{H})=\infty$ implies that $\#\textsc{IndSub}(\mathcal{H} \to \mathcal{G})$ subsumes $\#\textsc{IndSet}(\mathcal{G})$. 
   
   What remains are the first and the third entry of the last row. Note that, in both cases, we have $\omega(\mathcal{G}) \in O(1)$ and $\alpha(\mathcal{H})\in O(1)$. 
   We show that this condition easily implies polynomial-time tractability. To this end let $\omega_G$ and $\alpha_H$ be the (constant) upper bounds, respectively. 

   On input $H\in\mathcal{H}$ and $G\in\mathcal{G}$, we check whether $\omega(H)>\omega_G$, in which case we can output~$0$. Otherwise, we have that $|V(H)|\leq R(\omega_G,\alpha_H)\in O(1)$ where $R$ is Ramsey's function (see Theorem~\ref{thm:ramsey}). Thus, the brute-force algorithm runs in polynomial time for this case. 
\end{proof}

\section{Outlook}
Due to the absence of a general dichotomy~\cite{RothW20}, the following two directions are evident candidates for future analysis:

\paragraph*{Hereditary Host Graphs}
Is there a way to refine our classifications to hereditary $\mathcal{G}$? 
While such results would naturally be much stronger, we point out that a classification of general first-order (FO) model-checking and model-counting in hereditary graphs is wide open. Concretely, even if the class of allowed patterns $\mathcal{H}$ is the class of all graphs, it currently seems elusive to obtain criteria for hereditary $\mathcal{G}$ which, if satisfied, yield fixed-parameter tractability of  $\#\textsc{Sub}(\mathcal{H}\to\mathcal{G})$,  $\#\textsc{IndSub}(\mathcal{H}\to\mathcal{G})$, and $\#\textsc{Hom}(\mathcal{H}\to\mathcal{G})$ and which, if not satisfied, yield $\#\mathrm{W}[1]$-hardness of these problems. In a nutshell, the reason for this is the existence of arbitrarily dense hereditary classes of host graphs for which our subgraph counting problems, and even the much more general FO-model counting problem, become tractable; a trivial example is given by $\mathcal{G}$ being the class of all complete graphs. See~\cite{GajarskyHLOORS15,Ganianetal15,GenietT22} for recent work on specific hereditary hosts and~\cite{GajarskyHOLR20,BonnetKTW22} for general approaches to understand FO model checking on dense graphs.

\paragraph*{Arbitrary Pattern Graphs}
Can we refine our classifications to arbitrary classes of patterns $\mathcal{H}$, given that we stay in the realm of monotone classes of hosts $\mathcal{G}$? We propose the investigation of this question as the more promising direction for future research. While a sufficient and necessary criterion for the fixed-parameter tractability of, say $\#\textsc{Sub}(\mathcal{H} \to \mathcal{G})$, must depend on the set of forbidden subgraphs of $\mathcal{G}$, we conjecture that the structure of monotone somewhere dense graph classes is rich enough to allow for an explicit combinatorial description of such a criterion. In fact, for some concrete classes of host graphs, e.g.\ bipartite graphs~\cite{CurticapeanM14} and degenerate graphs~\cite{BressanR21}, such criteria have already been established.

\newpage


\bibliographystyle{plainurl}

