parameterizedproblem  Input: Output: Parameter:

# The Complexity of Pattern Counting in Directed Graphs, Parameterised by the
Outdegree111This research was funded in whole, or in part, by the Royal
Society project ”RAISON DATA” (Project reference: RP\R1\201074) and by the
Google Focused Award “Algorithms and Learning for AI” (ALL4AI). For the
purpose of Open Access, the authors have applied a CC BY public copyright
licence to any Author Accepted Manuscript version arising from this
submission. All data is provided in full in the results section of this paper.

Marco Bressan
Department of Computer Science
University of Milan
Italy  Matthias Lanzinger
Department of Computer Science
University of Oxford
United Kingdom  Marc Roth
Department of Computer Science
University of Oxford
United Kingdom

###### Abstract

We study the fixed-parameter tractability of the following fundamental
problem: given two directed graphs $\vec{H}$ and $\vec{G}$, count the number
of copies of $\vec{H}$ in $\vec{G}$. The standard setting, where the
tractability is well understood, uses only $|\vec{H}|$ as a parameter. In this
paper we take a step forward, and adopt as a parameter $|\vec{H}|+d(\vec{G})$,
where $d(\vec{G})$ is the maximum outdegree of $|\vec{G}|$. Under this
parameterization, we completely characterize the fixed-parameter tractability
of the problem in both its non-induced and induced versions through two novel
structural parameters, the _fractional cover number_ $\rho^{*}$ and the
_source number_ $\alpha_{s}$. On the one hand we give algorithms with running
time $f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{\rho^{*}\\!(\vec{H})+O(1)}$ and
$f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{\alpha_{s}(\vec{H})+O(1)}$ for
counting respectively the copies and induced copies of $\vec{H}$ in $\vec{G}$;
on the other hand we show that, unless the Exponential Time Hypothesis fails,
for any class $\vec{C}$ of directed graphs the (induced) counting problem is
fixed-parameter tractable if and only if $\rho^{*}(\vec{C})$
($\alpha_{s}(\vec{C})$) is bounded. These results explain how the orientation
of the pattern can make counting easy or hard, and prove that a classic
algorithm by Chiba and Nishizeki and its extensions (Chiba, Nishizeki SICOMP
85; Bressan Algorithmica 21) are optimal unless ETH fails.

Our proofs consist of several layers of parameterized reductions that preserve
the outdegree of the host graph. To start with, we establish a tight
connection between counting _homomorphisms_ from $\vec{H}$ to $\vec{G}$ to
#CSP, the problem of counting solutions of constraint satisfactions problems,
for special classes of patterns that we call _canonical DAGs_. To lift these
results from canonical DAGs to arbitrary directed graphs, we exploit a
combination of several ingredients: existing results for #CSPs (Marx JACM 13;
Grohe, Marx TALG 14), an extension of graph motif parameters (Curticapean,
Dell, Marx STOC 17) to our setting, the introduction of what we call _monotone
reversible minors_ , and careful analysis of quotients of directed graphs in
order to relate their adaptive width and fractional hypertree width as a
function to our novel parameters. Along the route we establish a novel bound
of the integrality gap for the fractional independence number of hypergraphs
based on adaptive width, which might be of independent interest.

##  1 Introduction

We study the complexity of the following fundamental counting problem: given
two directed graphs, $\vec{H}$ (the “pattern”) and $\vec{G}$ (the “host”),
count the number of occurrences or induced occurrences of $\vec{H}$ in
$\vec{G}$. This problem, known as _subgraph counting_ , _motif counting_ , or
_pattern counting_ , has gained great popularity because of its apparent
ubiquity in a diverse selection of fields, from social network analysis [52]
to network science [44, 43], and from database theory [27, 15, 26, 4, 30] and
data mining [1, 51] to bioinformatics [3, 48], phylogeny [36], and genetics
[49, 50]. For this reason, subgraph counting in general has received
significant attention from the theoretical community in the last two decades,
with a flurry of novel techniques and exciting results [6, 28, 21, 24, 35, 42,
23, 11, 37, 13, 7, 31].

Since subgraph counting in general is hard (think of counting cliques), it is
common to _parameterise_ the problem so as to allow for a “bad” dependence on
some quantity that is believed to be small in practice [28, 23]. The standard
parameterisation is by the size of $\vec{H}$, that is,
$|\vec{H}|=|V(\vec{H})|+|E(\vec{H})|$. In that case, one says the problem is
_fixed-parameter tractable_ , or in the class $\mathsf{FPT}$, if for some
(computable) function $f$ it admits an algorithm that runs in time
$f(|\vec{H}|)\cdot|\vec{G}|^{O(1)}$ for all $\vec{H}$ and $\vec{G}$. This
means one considers as efficient an algorithm with running time, say,
$2^{|\vec{H}|}\cdot|\vec{G}|$, but not one with running time
$|\vec{G}|^{|\vec{H}|}$. The rationale is that in practice $\vec{H}$ is often
very small compared to $\vec{G}$, thus a running time of
$2^{|\vec{H}|}\cdot|\vec{G}|$ is better than one of $|\vec{G}|^{|\vec{H}|}$.
Under this parameterisation, the tractability of the problem is well
understood: for the undirected version, both the induced and non-induced
versions are in $\mathsf{FPT}$ if and only if certain invariants of $H$ are
bounded [18, 24, 23], and it is not hard to show that the same holds for the
directed case as well (see Section 2).

While the parameterisation by $|\vec{H}|$ is standard, it is also quite
restrictive. Consider for instance the problem of counting the _induced_
copies of $\vec{H}$ in $\vec{G}$: when parameterised by $|\vec{H}|$, it is
well-known that the problem is in $\mathsf{FPT}$ if and only if the pattern
size $|\vec{H}|$ is bounded (see [18] and Appendix B). Thus, under this
parameterization, one can efficiently count the induced copies of just a
_finite_ number of patterns. Suppose instead the parameter is
$|\vec{H}|+d(\vec{G})$, where $d(\vec{G})$ is the maximum outdegree of
$\vec{G}$; the problem is then considered tractable if for some (computable)
function $f$ it admits an algorithm that runs in time
$f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{O(1)}$ for all $\vec{H}$ and
$\vec{G}$. It is not hard to see that, under this parameterization, the
problem becomes $\mathsf{FPT}$ even for _infinite_ families of patterns. Let
indeed $\vec{H}$ be the acyclic orientation of a $k$-clique: since $\vec{H}$
has only one source $s$ (a vertex of indegree $0$), one can first guess the
image of $s$ in $\vec{G}$ and then iterate over all $(k-1)$-vertex subsets in
the out-neighbourhood of $s$, which yields an algorithm with running time
$O(d(\vec{G})^{|\vec{H}|}\cdot|\vec{G}|)$. This idea was in fact extended to
counting subgraphs in degenerate host graphs, which have orientations with
bounded outdegree [8, 10, 9, 13, 32, 7] (see Section 3.4 for a detailed
discussion). Thus, adopting $|\vec{H}|+d(\vec{G})$ as a parameter can open the
door to a richer landscape of tractability.

The goal of the present work is to understand precisely what that landscape
is; that is, to understand when the aforementioned problems, parameterised by
$|\vec{H}|+d(\vec{G})$, are in $\mathsf{FPT}$ as a function of the pattern
$\vec{H}$. In addition to the aforementioned example of pattern counting in
degenerate graphs, there is another reason to consider $d(\vec{G})$ as part of
the parameter when counting directed subgraphs: several “real-world” directed
graphs that are natural “hosts” have small or constant outdegree. This is true
for many web graphs or online social network graphs, where the maximum
outdegree is much smaller than the average degree or the maximum indegree; and
it is true by construction in graphs produced by generative models such as
preferential attachment [2]. As is customary, to express the dependence on the
structure of $\vec{H}$, we formulate the problems as a function of a _class_
$\vec{C}$ of patterns — for instance, one may let $\vec{C}$ be the class of
all directed complete graphs, or of all directed trees. Let then $\vec{C}$
denote an arbitrary family of directed graphs, and for any $\vec{H}$ and
$\vec{G}$ let $\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ and
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ denote
respectively the number of copies and induced copies of $\vec{H}$ in
$\vec{G}$.

Our parameterised counting problems are formally defined as follows: The goal
of the present work is to understand which structural properties of the
elements of $\vec{C}$ determine whether
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ and
$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$ are in $\mathsf{FPT}$.

The rest of this manuscript is organised as follows. Section 2 gives a concise
overview of our results and their significance. Section 3 gives a detailed
overview of our proofs and their key technical insights. The complete proofs
of all our claims can be found in the remaining sections.

##  2 Results

We give complete complexity classifications for
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ and
$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$, into $\mathsf{FPT}$ versus
non-$\mathsf{FPT}$ cases, as a function of $\vec{C}$. These complexity
classifications, which are formally stated below, have the succinct form “The
problem is in $\mathsf{FPT}$ if and only if $p(\vec{C})$ is bounded”, where
$p$ is some parameter measuring the structural complexity of the graphs in
$\vec{C}$. The definition of those parameters is not elementary and requires
the introduction of some ancillary notation and definitions, which we are
going to do next. In order to understand _why_ those parameters are the right
ones, instead, one should take the technical tour of Section 3.

Let us then introduce our structural parameters. First, we need to define
_reachability hypergraphs_ and _contours_. Let $\vec{H}$ be a directed graph,
and let $\mathcal{S}$ be the set of its strongly connected components. Denote
by $\sim$ the equivalence relation over $V(\vec{H})$ given by $\mathcal{S}$,
and let $\vec{H}\mathbin{{/}{\sim}}$ be the quotient of $\vec{H}$ w.r.t.
$\sim$; with a little abuse of notation we let $\mathcal{S}$ be the vertex set
of $\vec{H}\mathbin{{/}{\sim}}$. A strongly connected component $S\in
V(\vec{H}\mathbin{{/}{\sim}})$ is a _source_ if it has indegree $0$ in
$\vec{H}\mathbin{{/}{\sim}}$. Let $S_{1},\ldots,S_{k}$ be the set of all such
sources. For any $S\in V(\vec{H}\mathbin{{/}{\sim}})$ let $R(S)$ be the set of
vertices reachable from $S$ in $\vec{H}$.

######  Definition 1.

The _reachability hypergraph_ of $\vec{H}$, denoted by $\mathcal{R}(\vec{H})$,
is the hypergraph with vertex set $V(\vec{H})$ and edge set
$\\{R(S_{i}):i\in[k]\\}$.

Intuitively, $\mathcal{R}(\vec{H})$ measures the complexity of $\vec{H}$ in
terms of “reachability relationships”. However, to state our classifications
correctly, we need to consider a slight modification of
$\mathcal{R}(\vec{H})$.

######  Definition 2.

The _contour_ of $\vec{H}$, denoted by $\Gamma(\vec{H})$, is the hypergraph
$\mathcal{R}(\vec{H})\setminus\cup_{i\in[k]}S_{i}$.

For instance, if $\vec{H}_{n}$ is obtained by orienting the edges of the
$1$-subdivision of the complete graph $K_{n}$ towards the original vertices,
then $\Gamma(\vec{H}_{n})=K_{n}$.

Figure 1: _(Top:)_ A directed graph $\vec{H}$, the sources of which are
highlighted in dashed boxes, its reachability hypergraph
$\mathcal{R}(\vec{H})$, and its contour $\Gamma(\vec{H})$. _(Bottom:)_ The
same constructions for the DAG $\vec{H}\mathbin{{/}{\sim}}$ obtained from
$\vec{H}$ by identifying all strongly connected components. Clearly, the
source number is invariant under taking the quotient w.r.t. $\sim$, that is,
$\alpha_{s}(\vec{H})=\alpha_{s}(\vec{H}\mathbin{{/}{\sim}})$. We will see that
the same is true for the fractional cover number, that is,
$\rho^{\ast}(\vec{H})=\rho^{\ast}(\vec{H}\mathbin{{/}{\sim}})$. Consequently,
it _always_ suffices to consider the DAG $\vec{H}\mathbin{{/}{\sim}}$ for
determining the complexity of counting copies and induced copies of $\vec{H}$.

Finally, we introduce our directed graph invariants, the _fractional cover
number_ and the _source number_. Let $\mathcal{H}$ be a hypergraph. A function
$\gamma:E(\mathcal{H})\\!\rightarrow\\![0,\infty)$ is a _fractional edge
cover_ of $\mathcal{H}$ if for every $v\in V(\mathcal{H})$

$\sum_{e\in E(\mathcal{H}):v\in e}\gamma(e)\geq 1\,.$ (1)

The weight of $\gamma$ is $\sum_{e\in E(\mathcal{H})}\gamma(e)$. The
fractional edge cover number of $\mathcal{H}$, denoted by
$\rho^{*}(\mathcal{H})$, is the smallest weight of any fractional edge cover
of $\mathcal{H}$. Then:

######  Definition 3.

The _fractional cover number_ of $\vec{H}$ is
$\rho^{*}(\vec{H})=\rho^{*}(\Gamma(\vec{H}))$. The _source number_ of
$\vec{H}$ is the number of sources in $\mathcal{S}$, denoted by
$\alpha_{s}(\vec{H})$; in other words, the number of strongly connected
components of $\vec{H}$ that are not reachable from any other connected
component.

Intuitively, both $\rho^{*}$ and $\alpha_{s}$ measure the complexity of
covering $\vec{H}$ through its sources. Our main result, the following
dichotomy theorem, says that such a “covering complexity” determines precisely
the fixed-parameter tractability of our problems. For any class $\vec{C}$ of
directed graphs let $\rho^{*}(\vec{C})=\sup_{\vec{H}\in\vec{C}}\rho^{*}(H)$
and $\alpha_{s}(\vec{C})=\sup_{\vec{H}\in\vec{C}}\alpha_{s}(H)$.

######  Theorem 4.

If the Exponential Time Hypothesis holds, then:

  1. 1.

$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})\in\mathsf{FPT}$ if and only if
$\rho^{*}(\vec{C})<\infty$

  2. 2.

$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})\in\mathsf{FPT}$ if and only if
$\alpha_{s}(\vec{C})<\infty$

Note that ETH is used only by the “only if” direction. While the statement of
Theorem 4 is simple, its proof is nontrivial — virtually all of this
manuscript is devoted to it. To put the theorem into perspective, Table 1
compares it to dichotomies for the other variants of the problem. We also
observe that Theorem 4 can be slightly strengthened: we can show the hardness
direction even for acyclic host graphs.

As a consequence of Theorem 4, we can claim the optimality (in an FPT sense)
of the well-known approach to counting the induced copies of a DAG $\vec{H}$
in a host $\vec{G}$ of bounded outdegree, used in several recent works on
counting in hosts of bounded degeneracy [8, 10, 9, 13, 32, 7]. This approach
consists in guessing the images of the sources of $\vec{H}$ in $\vec{G}$, and
has running time
$f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{\alpha_{s}(\vec{H})+O(1)}$. By Theorem
4, unless ETH fails the dependence on $\alpha_{s}(\vec{H})$ at the exponent
cannot be avoided, hence that approach is optimal in an FPT sense.

|
---
| $\\#\textsc{Sub}(C)$
---
| $\\#\textsc{DirSub}(\vec{C})$
---
| $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$
---
| FPT criterion
---
| $\mathsf{vc}(C)<\infty$
---
Curticapean, Marx [24]
| $\mathsf{vc}(\vec{C})<\infty$
---
Appendix B
| $\rho^{\ast}(\vec{C})<\infty$
---
Theorem 4
|
---
| $\\#\textsc{IndSub}(C)$
---
| $\\#\textsc{DirIndSub}(\vec{C})$
---
| $\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$
---
| FPT criterion
---
| $|C|<\infty$
---
Chen, Thurley, Weyer [18]
| $|\vec{C}|<\infty$
---
Appendix B
| $\alpha_{s}(\vec{C})<\infty$
---
Theorem 4
Table 1: Our results for $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ and
$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$ compared against
$\\#\textsc{IndSub}(\vec{C})$ and $\\#\textsc{DirIndSub}(\vec{C})$, which are
their counterparts parameterised by $|\vec{H}|$, and against
$\\#\textsc{Sub}(C)$ and $\\#\textsc{IndSub}(C)$, which are their _undirected_
counterparts parameterised by $|H|$. Here $\mathsf{vc}$ denotes the vertex
cover number; for directed graphs this is is just the vertex cover number of
the underlying undirected graph. The results for $\\#\textsc{IndSub}(\vec{C})$
and $\\#\textsc{DirIndSub}(\vec{C})$ are folklore in the community.

It shall be noted that, for $\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$, the
non-$\mathsf{FPT}$case in Theorem 4 also yields $\\#\mathsf{W[1]}$-hardness
(see Section 4 for a definition of $\\#\mathsf{W[1]}$). For
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ instead we do not prove
$\\#\mathsf{W[1]}$-hardness; the reason is that our proof uses a reduction
from certain families of $\\#\textsc{CSP}$ instances which by [40] we know to
be not in $\mathsf{FPT}$ if ETH holds, but we do not know if they are
$\\#\mathsf{W[1]}$-hard too.

When the problems in Theorem 4 are in $\mathsf{FPT}$, we can show simple
algorithms that solve them in time
$f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{p(\vec{H})+O(1)}$ where
$p\in\\{\rho^{*},\alpha_{s}\\}$. Formally, we prove:

######  Theorem 5.

For some computable function $f$ there is an algorithm solving
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ in time
$f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{\rho^{*}\\!(\vec{H})+O(1)}$. The same
holds for $\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$ with $\alpha_{s}$ in
place of $\rho^{*}$.

We point out that theorems 4 and 5 remain true in the (edge or vertex)
weighted setting, too.

A simple example shows Theorem 4 and Theorem 5 in action. Let $\Delta_{1}$ and
$\Delta_{2}$ be respectively the cyclic and acyclic orientations of $K_{3}$,
and for each $k\in\mathbb{N}$ let $\Delta_{1}^{k}$ and $\Delta_{2}^{k}$
consist of $k$ disjoint copies of respectively $\Delta_{1}$ and $\Delta_{2}$.
Finally, let $\vec{C}_{1}=\\{\Delta_{1}^{k}:k\in\mathbb{N}\\}$ and
$\vec{C}_{2}=\\{\Delta_{2}^{k}:k\in\mathbb{N}\\}$. Although the patterns are
rather elementary, establishing the tractability of
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C}_{1})$ and
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C}_{2})$ “by hand” can be laborious.
Theorem 4 and Theorem 5 answer immediately: $\rho^{*}(\Delta_{1}^{k})=0$,
since in $\Delta_{1}^{k}$ every vertex belongs to some source, hence
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C}_{1})$ is fixed-parameter tractable
and solvable in time $f(|\vec{H}|,d(\vec{G}))\cdot|\vec{G}|^{O(1)}$; but
$\rho^{*}(\Delta_{2}^{k})=k$, since $\Gamma(\Delta_{2}^{k})$ has $k$ disjoint
hyperedges, hence $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C}_{2})$ is not fixed-
parameter tractable unless ETH fails. One can also see that
$\alpha_{s}(\Delta_{1}^{k})=\alpha_{s}(\Delta_{2}^{k})=k$; therefore, by
Theorem 4, under ETH both $\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C}_{1})$
and $\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C}_{2})$ are not fixed-parameter
tractable.

Another example helps appreciating the different between our parameterization
and the standard one, as well as the necessity of $\rho^{*}$ being fractional.
Let $H_{k}$ be the graph defined as follows. The vertices of $H_{k}$ are
$U_{k}\cup D_{k}$ where $U_{k}=\\{1,\dots,2k\\}$ and $D_{k}=\\{A\subseteq
U_{k}~{}|~{}|A|=k\\}$; and for each $i\in U_{k}$, there is an edge between $i$
and $D\in D_{k}$ if and only if $i\in D$. Let $C$ be the class of all $H_{k}$.
It is not hard to show that $H_{k}$ contains the subdivision of the $k$-clique
as induced subgraph. Thus the vertex-cover number of $C$ is unbounded and,
assuming ETH, Table 1 yields that $\\#\textsc{Sub}(C)$ and
$\\#\textsc{DirSub}(\vec{C})$ are not fixed-parameter tractable for any class
$\vec{C}$ obtained by orienting the graphs in $C$. However, if we parameterise
also by the outdegree of the host, then the situation becomes much more
subtle. Let $\vec{C}$ be the class of digraphs obtained by orienting the edges
in the $H_{k}$ from $U_{k}$ to $D_{k}$; an argument similar to [33, Example
4.2] shows that $\rho^{\ast}(\vec{H}_{k})\leq 2$ for each
$\vec{H}_{k}\in\vec{C}$, thus $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ is
fixed-parameter tractable by Theorem 5. Moreover, [33, Example 4.2] show that
any non-fractional cover of $\vec{H}_{k}$ has super-constant weight; this
proves that considering the _fractional_ cover number $\rho^{*}$ is crucial;
its integral counterpart cannot work.

We conclude this section with a result of independent interest developed in
our proofs. Let $\mathcal{H}$ be a hypergraph. The independence number
$\alpha(\mathcal{H})$ of $\mathcal{H}$ is the size of the largest subset of
$V(\mathcal{H})$ such that no two of its elements are contained in a common
edge. The natural relaxation of this definition yields the _fractional_
independence number $\alpha^{*}(\mathcal{H})$. Our result is that the ratio
between $\alpha^{*}(\mathcal{H})$ and $\alpha(\mathcal{H})$, i.e. the
integrality gap of $\alpha$, is bounded by the _adaptive width_ 222Note that
adaptive width is equivalent to submodular width [40]. of $\mathcal{H}$ [39].

######  Theorem 6.

Every hypergraph $\mathcal{H}$ satisfies
$\alpha(\mathcal{H})\geq\frac{1}{2}+\frac{\alpha^{\ast}(\mathcal{H})}{4\operatorname{aw}(\mathcal{H})}$.

##  3 Technical Overview

This section gives an overview of the tools and techniques behind the results
of Section 2. The overview focuses on
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$, but similar arguments apply to
$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$. Before digging into the most
technical part, let us give the high-level idea of our proof strategy.

At the root of all our results is a standard connection between copies and
homomorphisms, explained in Section 3.1. It is well known indeed that
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ can be expressed
as a linear combination of homomorphism counts,
$\sum_{\vec{F}}a_{\vec{H}}(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$,
where $a_{\vec{H}}(\vec{F})>0$ and $\vec{F}$ ranges over a certain set of
_quotients_ of $\vec{H}$. Here, a quotient of $\vec{H}$ is a directed graph
obtained from $\vec{H}$ by contracting (not necessarily connected) vertex
subsets into single vertices (see Section 4 for the formal definition). It is
also known that the complexity of computing
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ equals, up to
$f(|\vec{H}|)$ factors, that of computing the hardest
$\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$ term. Therefore we
can reduce $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ _to_ and _from_ its
homomorphism counting version $\\#\textsc{DirHom}_{\mathrm{d}}(\vec{Q})$,
where $\vec{Q}$ consists of certain quotients of $\vec{C}$. Armed with these
results, we proceed as follows.

First, in Section 3.2 we prove that $\rho^{*}(\vec{C})<\infty$ implies
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})\in\mathsf{FPT}$. To this end we
prove that if $\vec{F}$ is a quotient of $\vec{H}$ then the _fractional
hypertreewidth_ of the contour of $\vec{F}$ satisfies
$\mathsf{fhtw}(\Gamma(\vec{F}))\leq\rho^{*}(\vec{H})$. Therefore,
$\mathsf{fhtw}(\Gamma(\vec{Q}))\leq\rho^{*}(\vec{C})<\infty$. We then show
that computing $\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$ can
be reduced in FPT time to counting the homomorphisms from $\Gamma(\vec{F})$ to
a hypergraph $\mathcal{G}$ obtained from $\vec{F}$ and $\vec{G}$. As
hypergraph homomorphism counting is in $\mathsf{FPT}$ when the pattern has
bounded fractional hypertreewdith, this proves the claim.

Next, in Section 3.3 we prove that $\rho^{*}(\vec{C})=\infty$ implies
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})\notin\mathsf{FPT}$, or ETH fails. To
start with, we suppose $\vec{C}$ contains only _canonical DAGs_ , directed
graphs of a particularly simple type. We can prove that the aforementioned
problem of counting homomorphisms between hypergraphs can be reduced to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ if the considered hypergraph
patterns belong to the contours of $\vec{C}$. By existing results this implies
that, unless ETH fails,
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})\notin\mathsf{FPT}$ whenever the
contours of $\vec{C}$ have unbounded _adaptive width_ [41]. It remains to lift
these results from canonical DAGs to abitrary DAGs and, ultimately, to
arbitrary directed graphs. To this end, we introduce what we call _monotone
reversible minors_ (MRMs). Intuitively, $\vec{H}^{\prime}$ is an MRM of
$\vec{H}$ if there exists an FPT reduction from counting copies
$\vec{H}^{\prime}$ to counting copies of $\vec{H}$, and if $\vec{H}^{\prime}$
preserves some parameters of interest (like $\rho^{*}$). We show that _every_
directed graph $\vec{H}$ has an MRM $\vec{H}^{\prime}$ that is a canonical
DAG, so counting $\vec{H}$ is at least as hard as counting $\vec{H}^{\prime}$.
Next, we show that counting copies of $\vec{H}^{\prime}$ is hard. To this end
we show that, if $\rho^{*}(\vec{H}^{\prime})$ is large, then its reduct
$\Gamma(\vec{H}^{\prime})$ has large adaptive width or large independence
number. By employing arguments from the homomorphism connection above and from
[13], this implies that counting the copies of $\vec{H}^{\prime}$ is hard
unless ETH fails, which concludes our proof.

In what follows we use standard terminology as much as possible; in any case,
all concepts and terms are defined formally in Section 4.

###  3.1 The Directed Homomorphism Basis

The first ingredient of our work is the so-called _homomorphism basis_
introduced by Curticapean, Dell, and Marx [23], which establishes a common
connection between (undirected) parameterised pattern counting problems.
Although the original framework is for undirected graphs, it can be equally
well be formulated for the directed case, as we are going to do. Let $\vec{H}$
be a digraph. There is a function ${\mathsf{sub}}_{\vec{H}}$ of finite support
from digraphs to rationals such that for each digraph $\vec{G}$:

$\displaystyle\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$
$\displaystyle=\sum_{\vec{F}}{\mathsf{sub}}_{\vec{H}}(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$
(2)

This identity follows by well-known transformations based on inclusion-
exclusion and Möbius inversion (see e.g. Chapter 5.2.3. in Lovász [38]). It is
also well known that ${\mathsf{sub}}_{\vec{H}}(\vec{F})\neq 0$ if and only if
$\vec{F}$ is a quotient of $\vec{H}$.

These facts allow us to construct a reduction from the parameterized problem
of computing $\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ to
the parameterized problem of computing
$\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ and vice versa.
More precisely, one can show that computing
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ is precisely as
hard (in FPT-equivalence terms) as computing the hardest term
$\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$ in the summation
of (2). One direction is obvious — the time to compute
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ is the sum of the
times to compute all terms
$\\#\mbox{$\mathsf{Sub}(\vec{F}\\!\rightarrow\\!\vec{G})$}$, whose number is a
function of $\vec{H}$. The other direction is nontrivial, and was established
for multiple variants of subgraph counting over the past years [15, 23, 26,
46, 7]. Rather than extending those results to yet another variant (directed
graphs), we observe that the constructive version of Dedekind’s Theorem on the
linear independence of characters yields a general interpolation method that
subsumes all those results, including the one for directed graphs. We prove
what follows (see Theorem 36 for a more complex but complete version):

######  Theorem 7 (Simplified Version).

Let $(\mathrm{G},\ast)$ be a semigroup. Let furthermore
$(\varphi_{i})_{i\in[k]}$ with
$\varphi_{i}:\mathrm{G}\\!\rightarrow\\!\mathbb{Q}$ be pairwise distinct and
non-zero semigroup homomorphisms of $(\mathrm{G},\ast)$ into
$(\mathbb{Q},\cdot)$, that is, $\varphi_{i}(g_{1}\ast
g_{2})=\varphi_{i}(g_{1})\cdot\varphi_{i}(g_{2})$ for all $i\in[k]$ and
$g_{1},g_{2}\in\mathrm{G}$. Let $\phi:\mathrm{G}\\!\rightarrow\\!\mathbb{Q}$
be a function

$\phi:g\mapsto\sum_{i=1}^{k}a_{i}\cdot\varphi_{i}(g)\,,$ (3)

where the $a_{i}$ are rational numbers. Then there is an efficient algorithm
$\hat{\mathbb{A}}$ which is equipped with oracle access to $\phi$ and which
computes the coefficients $a_{1},\dots,a_{k}$.

In our setting, Theorem 7 yields what follows. First, let $\mathrm{G}$ be the
set of all digraphs and $*$ be the directed tensor product; one can check that
$(\mathrm{G},*)$ is indeed a semigroup. Second, for any fixed $\vec{H}$
consider the function
$\vec{G}\mapsto\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$; one
can check this is a semigroup homomorphism into $\mathbb{Q}$. Using Theorem 7,
we can prove:

######  Lemma 8.

There exists a deterministic algorithm $\mathbb{A}$ with the following
specifications:

  * •

The input of $\mathbb{A}$ is a pair $(\vec{{G}}^{\prime},\iota)$ where
$\vec{{G}}^{\prime}$ is a digraph and
$\iota:\mathrm{G}\\!\rightarrow\\!\mathbb{Q}$.

  * •

$\mathbb{A}$ is equipped with oracle access to the function

$\vec{G}\mapsto\sum_{\vec{F}}\iota(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}\,,$

where the sum is over all (isomorphism classes of) digraphs.

  * •

The output of $\mathbb{A}$ is the list with elements
$(\vec{F},\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{{G}}^{\prime})$})$
for each $\vec{F}$ with $\iota(\vec{F})\neq 0$.

  * •

For some computable function $f$ the running time of $\mathbb{A}$ is bounded
by $f(|\iota|)\cdot|\vec{{G}}^{\prime}|^{O(1)}$

  * •

The outdegree of every digraph $\vec{G}$ on which $\mathbb{A}$ invokes the
oracle is at most $f(|\iota|)\cdot d(\vec{{G}}^{\prime})$ where
$d(\vec{{G}}^{\prime})$ is the maximum outdegree of $\vec{{G}}^{\prime}$.

To understand the meaning of Lemma 8, let
$\iota(\vec{F})={\mathsf{sub}}_{\vec{H}}(\vec{F})$ for all
$\vec{F}\in\mathrm{G}$, see (2). Then Lemma 8 says that, if $\mathbb{A}$ has
oracle access to $\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\cdot)$}$,
then $\mathbb{A}$ can compute
$\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G}^{\prime})$}$
efficiently and by computing
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ only for $\vec{G}$
of outdegree not larger than that of $\vec{G}^{\prime}$. This yields a
parameterised reduction from $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$, where $\vec{C}^{\prime}$
is the set of all digraphs $\vec{F}$ such that
${\mathsf{sub}}_{\vec{H}}(\vec{F})\neq 0$ for some $\vec{H}\in\vec{C}$. As
stated above, ${\mathsf{sub}}_{\vec{H}}(\vec{F})\neq 0$ if and only if
$\vec{F}$ is a quotient of $\vec{H}$. We conclude that computing
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ is at least as
hard as computing $\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$
for each $\vec{F}$ that is a quotient of $\vec{H}$. In other words we have a
parameterised reduction from $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$ where $\vec{C}^{\prime}$
is the set of all quotients of $\vec{C}$. Together with the converse reduction
(see above) this tells us that $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ is
_precisely as hard as_ $\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$
where $\vec{C}^{\prime}$ is the set of all quotients of $\vec{C}$. Thus,
classifying the complexity of $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ boils
down to understanding the complexity of
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$ where $C^{\prime}$ is
again the set of all quotients of $\vec{C}$. Answering this question turns out
to be the most challenging task in this work.

###  3.2 Upper bounds: a reduction to #CSP

To understand the complexity of
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$ where $\vec{C}$ is the set
of all quotients of $\vec{C}$, we take two steps. First, we show that the
problem can be reduced to #CSP, the problem of counting the solutions to a
constraint satisfaction problem. Second, we show that the fractional cover
number of $\vec{C}$ bounds the fractional hypertree width of the #CPS
instances obtained from $\vec{C}^{\prime}$, which makes the problem fixed-
parameter tractable by existing results.

####  3.2.1 A reduction to #CSP

Let $\vec{H}$ and $\vec{G}$ be digraphs and let $d$ be the maximum outdegree
of $\vec{G}$. Let furthermore $k=|\vec{H}|$ and $n=|\vec{G}|$. Recall that a
source $S$ of $\vec{H}$ is a strongly connected component of $\vec{H}$ such
that $S$ cannot be reached from any other strongly connected component. Let
$S_{1},\dots,S_{\ell}$ be the sources of $\vec{H}$, and let $s_{i}\in S_{i}$
for each $i\in[\ell]$. Finally, let $R_{i}$ be the set of all vertices of
$\vec{H}$ that can be reached from $s_{i}$ via a directed path — note that
$S_{i}$ is fully contained in $R_{i}$. Clearly each arc of $\vec{H}$ is fully
contained in at least one of the $R_{i}$. Writing $\vec{H}[R_{i}]$ for the
subgraph of $\vec{H}$ induced by $R_{i}$, one can see that every map
$\varphi:V(\vec{H})\\!\rightarrow\\!V(\vec{G})$ satisfies:

$\varphi\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}\;\Leftrightarrow\;\forall
i\in[\ell]:\varphi|_{R_{i}}\in\mbox{$\mathsf{Hom}(\vec{H}[R_{i}]\\!\rightarrow\\!\vec{G})$}\,,$
(4)

where $\varphi|_{R_{i}}$ is the restriction of $\varphi$ on $R_{i}$. In other
words, $\varphi$ is a homomorphism if and only if it induces a partial
homomorphism from $\vec{H}[R_{i}]$ for each $i\in[\ell]$.

The observation above allows us to reduce the computation of
$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$ to counting the solutions of a
certain constraint satisfaction problem. Start by fixing an arbitrary order
over $V(\vec{H})$, so that every $R_{i}$ appears as an ordered tuple. Now, for
each $i\in[\ell]$, we enumerate all partial homomorphisms
$\varphi|_{R_{i}}\in\mbox{$\mathsf{Hom}(\vec{H}[R_{i}]\\!\rightarrow\\!\vec{G})$}$.
It is well known that this can be done in time $f(k,d)\cdot n^{O(1)}$: simply
guess the image $v$ of $s_{i}$ in $V(\vec{G})$, and perform a brute force
search over the $d^{O(k)}$ vertices of $\vec{G}$ reachable from $v$ in $k$
steps [20, 12, 7]. Now for every $i\in[\ell]$ consider the set of all (the
images of) the maps in $\mathsf{Hom}(\vec{H}[R_{i}]\\!\rightarrow\\!\vec{G})$.
This is a set of ordered tuples of vertices of $\vec{G}$, i.e., a relation
over $V(\vec{G})$. We denote this relation by $\mathrm{R}_{i}$. It is not hard
to see that the homomorphisms from $\vec{H}$ to $\vec{G}$ are precisely those
maps from $V(\vec{H})$ to $V(\vec{G})$ that for every $i\in[\ell]$ send
$R_{i}$ to an element of $\mathrm{R}_{i}$, and that counting those maps is an
instance of a counting constraint satisfaction problem (#CSP).

####  3.2.2 Bounding the cost of solving #CSP over quotients

Recall the reachability hypergraph $\mathcal{R}(\vec{H})$ of $\vec{H}$: the
hypergraph whose vertex set is $V(\vec{H})$ and whose edge set is
$\\{R_{i}:i\in[\ell]\\}$. A well-known result due to Grohe and Marx [33]
states that counting the solutions to the CSP instance above is fixed-
parameter tractable whenever $\mathcal{R}(\vec{H})$ has bounded fractional
hypertreewidth, where the parameter is $|\vec{H}|$; in fact, [33] shows that
there is an algorithm that solves the problem in time
$f(k,d)\cdot|V(\vec{G})|^{\mathsf{fhtw}(\mathcal{R})+O(1)}$. Now recall from
Section 2 the fractional cover number $\rho^{\ast}(\vec{H})$ of $\vec{H}$. We
prove:

######  Lemma 9.

Let $\vec{H}$ be a digraph, let $\vec{F}$ be a quotient graph of $\vec{H}$,
and let $\mathcal{R}(\vec{F})$ be the reachability hypergraph of $\vec{F}$.
Then $\mathsf{fhtw}(\mathcal{R}(\vec{F}))\leq\rho^{\ast}(\vec{H})$.

The intuition behind the proof of Lemma 9 is that (i) taking the quotient of a
digraph cannot increase its fractional cover number, and (ii) the fractional
hypertreewidth of a hypergraph is bounded by its fractional edge cover number
(which is the fractional cover number of $\vec{H}$).

Together with the observations above, this implies that we can compute
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ in time
$f(|\vec{H}|,d(\vec{g}))\cdot|\vec{G}|^{\rho^{*}(\vec{H})}$, thus proving
Theorem 5 and the tractability part of Theorem Theorem 4 for
$\\#\textsc{DirSub}_{\mathrm{d}}$. It remains to prove the intractability part
of Theorem 4, which we do in the next sections.

Let us again consider $\vec{H}=\Delta_{1}^{k}$ as a toy example, that is,
$\vec{H}$ is the disjoint union of $k$ triangles, each of which is cyclically
oriented. We can use the principle of inclusion and exclusion to reduce the
computation of $\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ to
the computation of terms
$\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$ where $\vec{F}$ is
a quotient of $\vec{H}$. Now, it can easily be observed that each quotient of
$\vec{H}$ is a disjoint union of strongly connected components
$S_{1},\dots,S_{\ell}$. Unfolding our general reduction to $\\#\textsc{CSP}$,
for each of the strongly connected components $S$, we only have to guess the
image $v$ of one vertex $s\in S$ in $\vec{G}$. Then the image of each
additional vertex in $S$ must be reachable from $v$ by a directed path of
length at most $k$. Since the outdegree of $\vec{G}$ is at most $d$, there are
thus at most $d^{O(k)}$ possibilities for the images of the remaining
vertices. Thus, for each strongly connected components $S$, we can compute
$\\#\mbox{$\mathsf{Hom}(\vec{F}[S]\\!\rightarrow\\!\vec{G})$}$ in time
$d^{O(k)}\cdot|\vec{G}|$. Finally, we have
$\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}=\prod_{i=1}^{\ell}\\#\mbox{$\mathsf{Hom}(\vec{F}[S_{i}]\\!\rightarrow\\!\vec{G})$}$.

###  3.3 Lower bounds

The goal of this section is to prove that, roughly speaking, if
$\rho^{*}(\vec{H})$ is large then $\vec{H}$ has a quotient $\vec{F}$ such that
computing $\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}$ is hard
when parameterized by $|\vec{F}|+d(\vec{G})$. To this end we seek a reduction
from #CSP to $\\#\textsc{DirHom}_{\mathrm{d}}$, i.e., in the opposite
direction of Section 3.2. However, while that direction was relatively easy,
since every digraph can be easily encoded as a set of relations, the direction
we seek here is significantly harder. Indeed, it is not clear at all how an
instance of #CSP can be “encoded” as a pair of directed graphs
$(\vec{H},\vec{G})$ if we can choose $\vec{H}$ only from the class $\vec{C}$
for which we want to prove hardness.

####  3.3.1 Encoding #CSP instances via canonical DAGs

To bypass the obstacle above, we start by considering classes of _canonical
DAGs_. A digraph $\vec{H}$ is a canonical DAG if it is acyclic and every
vertex is either a source (i.e., it has indegree $0$) or a sink (i.e., it has
outdegree $0$). Note that this implies that $\vec{H}$ is bipartite, with (say)
all sources on the left and all sinks on the right. If $\vec{C}$ is a class of
canonical DAGs, then it is easy to reduce #CSP to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ while preserving all parameters. To
see why, let $(\mathcal{H},\mathcal{G})$ be a pair of hypergraphs (the
instance of #CSP). Define $\vec{H}$ by letting
$V(\vec{H})=V(\mathcal{H})\cup\\{x_{e}:e\in E(\mathcal{H})\\}$, and adding
$(x_{e},u)$ to $E(\vec{H})$ for every $e\in E(\vec{\mathcal{H}})$ and every
$u\in e$. Define $\vec{G}$ similarly as a function of $\mathcal{G}$. One can
then show, using the _color-prescribed_ version of homomorphism counting
(defined in Section 4), that
$\\#\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!\mathcal{G})$}$ can be
computed in FPT time with $|\mathcal{H}|$ as a parameter if we can compute
$\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ in FPT time with
$|\vec{H}|+d(\vec{G})$ as a parameter.

Recall then the _contour_ $\mathcal{R}(\vec{H})$ of $\vec{H}$ from Section 2.
It is immediate to see that, if $\vec{H}$ is a canonical DAG obtained from
$\mathcal{H}$ as described above, then $\mathcal{R}(\vec{H})=\mathcal{H}$.
This is precisely the intuitive role of the contour — to encode the structure
of the reachability sets of $\vec{H}$ (ignoring sources). Indeed, using
contours we can then state our main reduction. Let $\vec{C}$ be a class of
canonical DAGs, and let $\\#\textsc{CSP}(\Gamma(\vec{C}))$ be the restriction
of $\\#\textsc{CSP}$ to instances whose left-hand hypergraph (i.e.,
$\mathcal{H}$) is isomorphic to a contour of $\Gamma(\vec{C})$. Using as a
starting point a reduction due to Chen et al. [19], we prove that
$\\#\textsc{CSP}(\Gamma(\vec{C}))$ reduces to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ via parameterised Turing
reductions. Now, under ETH,
$\\#\textsc{CSP}(\Gamma(\vec{C}))\notin\mathsf{FPT}$ when the adaptive width
of $\Gamma(\vec{C})$ is unbounded [40], unless ETH fails. By the reduction
above, then, we obtain:

######  Lemma 10.

$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})\notin\mathsf{FPT}$ for every class
$\vec{C}$ of canonical DAGs whose contours have unbounded adaptive width,
unless ETH fails.

We now seek to lift this result from canonical DAGs to arbitrary directed
graphs.

####  3.3.2 Lifting hardness to arbitrary digraphs via Monotone Reversible
Minors

Starting from Lemma 10, we prove a hardness result for
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ for general classes of digraphs
$\vec{C}$. To this end we need to reduce from
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$ where $\vec{C}^{\prime}$
is a class of canonical DAGs, so that we can apply Lemma 10; clearly, the
reduction must imply that $\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$
has unbounded adaptive width.

Towards this end we introduce a kind of graph minors for digraphs, which we
call _monotone reversible (MR) minors_. A digraph $\vec{H}^{\prime}$ is a MR
minor of $\vec{H}$ if it is obtained from $\vec{H}$ by a sequence of the
following operations:

  * •

deleting a sink, i.e., a strongly connected component from which no other
vertices can be reached

  * •

deleting a loop

  * •

contracting an arc

Note that, unlike standard minors, deletion of arbitrary vertices and
arbitrary arcs are not allowed. This allows us to prove:

######  Lemma 11.

Let $\vec{C}$ be a class of digraphs and let $\vec{D}$ be a class of MR minors
of $\vec{C}$. Then there exists a parameterised Turing reduction from
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{D})$ to
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$.

Lemma 11 explains the “reversible” part of MR minors—we can efficiently
“revert” the operations that yielded a MR of a digraph; for the “monotone” see
the next section. The heart of the proof of Lemma 11 proves the claim for the
color-prescribed version of the problems; this implies the reduction for the
original problems via standard interreducibility arguments arguments. As a
consequence of Lemma 11 we obtain:

######  Lemma 12.

Let $\vec{C}$ be a recursively enumerable class of digraphs and let
$\vec{C}^{\prime}$ be a class of canonical DAGs that are MR minors of digraphs
in $\vec{C}$. If $\Gamma(\vec{C}^{\prime})$ has unbounded adaptive width then
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})\notin\mathsf{FPT}$, unless ETH
fails.

####  3.3.3 Lifting hardness from homomorphisms to subgraphs

Recall the arguments of Section 3.1: to prove that
$\\#\textsc{DirSub}(\vec{C})$ is hard when $\rho^{*}(\vec{C})=\infty$, we
essentially have to prove that every digraph $\vec{H}$ with high fractional
cover number $\rho^{*}(\vec{H})$ has a quotient $\vec{F}$ that is hard. By the
arguments of the previous section, to show that such a quotient $\vec{F}$ is
hard it is enough to show that $\vec{F}$ has an MR minor $\vec{F}^{\prime}$
which is a canonical DAG whose contour $\Gamma(\vec{F}^{\prime})$ has high
adaptive width. We indeed prove that such a quotient exists. To this end, we
consider two cases. Recall that $\alpha(\mathcal{H})$ and
$\alpha^{*}(\mathcal{H})$ denote respectively the independence number and the
fractional independence number of a hypergraph $\mathcal{H}$.

  * (a)

$\alpha(\Gamma(\vec{H}))$ is large. In this case we can show that $\vec{H}$
contains a large matching whose edges are “isolated enough” for us to
construct a quotient $\vec{F}$ that admits, as MR minor, the $1$-subdivision
$\vec{F}^{\prime}$ of a large complete graph, where the arcs of
$\vec{F}^{\prime}$ are directed away from the subdivision vertices. It is easy
to see that $\vec{F}^{\prime}$ is a canonical DAG, and that
$\Gamma(\vec{F}^{\prime})$ is the complete graph itself, which has large
adaptive width.

  * (b)

$\alpha(\Gamma(\vec{H}))$ is small. We then choose as quotient $\vec{F}$ the
graph $\vec{H}$ itself. Recall that, by definition,
$\rho^{*}(\vec{H})=\rho^{*}(\mathcal{R}(\vec{H}))$. By LP duality the
fractional cover number equals the fractional independence number, that is,
$\rho^{*}(\mathcal{R}(\vec{H}))=\alpha^{*}(\mathcal{R}(\vec{H}))$. Using
Theorem 6, we deduce that the adaptive width of $\mathcal{R}(\vec{H})$ is
within constant factors of $\alpha^{*}(\mathcal{R}(\vec{H}))$, and thus of
$\rho^{*}(\vec{H})$. By carefully exploiting this fact, we can explicitly
construct an MR minor $\vec{F}^{\prime}$ of $\vec{H}$ that is both a canonical
DAG and has high adaptive width.

Thus, in both cases we can show that if $\rho^{*}(\vec{H})$ is large then
$\vec{H}$ admits an MR minor that is a canonical DAG of large treewidth.
Formally, we obtain:

######  Lemma 13.

Let $\vec{C}$ be a class of digraphs such that $\rho^{*}(\vec{C})=\infty$.
Then the class $\vec{C}^{\prime}$ of all canonical DAGs that are MR minors of
quotients of $\vec{C}$ has unbounded adaptive width.

As a consequence, this implies that
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})\notin\mathsf{FPT}$ whenever
$\rho^{*}(\vec{C})=\infty$, unless ETH fails. This concludes the overview of
the proof of the lower bounds for $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$.

Before proceeding with the next section, we wish to point out that, in the
course of our proofs, we will also see that for computing the fractional cover
number and the source count of a directed graph $\vec{H}$, it is _always_
sufficient to consider the DAG $\vec{H}\mathbin{{/}{\sim}}$ (see Figure 1). In
other words, the complexity of $\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ and
$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$ solely depends on the structure
of the DAGs obtained by contracting the strongly connected components of the
patterns in $\vec{C}$.

###  3.4 Related Work and Outlook

Our results are closely related to the recent surge of works on pattern
counting in degenerate graphs [8, 10, 9, 13, 32, 7]: An undirected graph $G$
has degeneracy $d$ if there is an acyclic orientation $\vec{G}$ of $G$ with
outdegree at most $d$. In the context of pattern counting in degenerate
graphs, one is given undirected graphs $H$ and $G$, and the goal is to compute
the number of copies (resp. induced copies) of $H$ in $G$, parameterised by
the size of the pattern $H$ and the degeneracy $d$ of $G$. These problems have
been completely classified with respect to linear time tractability [7] and
with respect to fixed-parameter tractability [13].

The crucial difference to the results in this work is that, in our setting,
the orientations of $H$ and $G$ are already fixed. Notably, this increases the
set of tractable instances when compared to the degenerate setting: For
example, counting copies of an undirected graph $H$ in an undirected graph
$G$, parameterised by $|H|$ and the degeneracy $d$ of $G$, is FPT if and only
if the induced matching number of $H$ is small [13]. Now fix acyclic
orientations $\vec{H}$ and $\vec{G}$ of $H$ and $G$ such that the outdegree of
$\vec{G}$ is at most $d$. One might think that the directed problem also is
FPT if and only if $H$ (i.e., the underlying undirected graph of $\vec{H}$)
has small induced matching number. However, this is not true: We have shown in
this work that we can count copies of a digraph $\vec{H}$ in a digraph
$\vec{G}$ in FPT time (parameterised by $|\vec{H}|$ and $d(\vec{G})$) if and
only if the fractional cover number of $\vec{H}$ is small — we will see that
this holds even if the host $\vec{G}$ is a DAG. While $H$ having small induced
matching number certainly implies that the fractional cover number of
$\vec{H}$ is small, the other direction does not hold: For example, if
$\vec{H}$ contains a source that is adjacent to all non-sources, then the
fractional cover number is $1$, although the induced matching number can be
arbitrarily large.

This work also sheds some new light on the problem of counting homomorphisms
into degenerate graphs: Bressan [12] has shown that we can count homomorphisms
from $H$ to $G$ in FPT time (parameterised by $|H|$ and the degeneracy of $G$)
if the so-called _dag treewidth_ of $H$ is small; it is currently open whether
the other direction holds as well [13, 7]. The dag treewidth of $H$ is just
the maximum (non-fractional) hypertreewidth of the reachability hypergraph of
any acyclic orientation of $\vec{H}$. Our reduction to $\\#\textsc{CSP}$
implies that it is sufficient for the reachability hypergraphs to have small
fractional hypertreewidth, which yields a fractional version of dag treewidth.
However, it is not clear whether unbounded dag treewidth and unbounded
fractional dag treewidth are equivalent, the reason for which is the fact that
all acyclic orientations have to be considered. We leave this as an open
problem for future work.

##  4 Preliminaries

Given a set $S$, we set $S^{2}=S\times S$, and we write $S^{(2)}$ for the set
of all unordered pairs of distinct elements of $S$. Let $f:A\times
B\\!\rightarrow\\!C$ be a function and let $a\in A$. We write
$f(a,\ast):B\\!\rightarrow\\!C$ for the function that maps $b\in B$ to
$f(a,b)$.

###  4.1 Graphs and Directed Graphs

We denote graphs by $F,G,H$, and directed graphs by $\vec{F},\vec{G},\vec{H}$.
Graphs and digraphs are encoded via adjacency lists, and we write $|G|$ (resp.
$|\vec{G}|$) for the length of the encoding. In the remainder of the paper we
will call directed graphs just “digraphs”. We use $\\{u,v\\}$ for undirected
edges, and $(u,v)$ for directed edges, which we also call _arcs_. Furthermore,
we will use $C$ to denote classes of graphs, and $\vec{C}$ to denote classes
of digraphs. Our graphs do not contain multi-edges; however, we allow forward-
backward arcs $(u,v)$ and $(v,u)$ in digraphs. Additionally, our undirected
graphs do not contain loops (edges from a vertex to itself) unless stated
otherwise. For technical reasons, we will allow loops in digraphs.333We will
see and state explicitly, that all of our hardness results will also entail
corresponding hardness in the restricted case of digraphs without loops.

A directed acyclic graph (DAG) is a digraph without directed cycles. A
_source_ of a DAG is a vertex with in-degree $0$, and a _sink_ of a DAG is a
vertex with outdegree $0$ (and an isolated vertex is simultaneously a source
and and a sink). Given a directed (not necessarily acyclic) graph $\vec{H}$
and a vertex $v\in V(\vec{H})$, we write $R(v)$ for the set of vertices
reachable from $v$ by a directed path; this includes $v$ itself. Given a set
of vertices $S\subseteq V(\vec{H})$, we set

$\displaystyle R(S):=\bigcup_{v\in S}R(v)\,.$

Let $H$ be a graph and $\sigma$ a partition of $V(H)$. The _quotient graph_ of
$H$ w.r.t. $\sigma$, denoted by $H/\sigma$, is defined as follows:
$V(H/\sigma)$ consists of the blocks of $\sigma$, and $\\{B_{1},B_{2}\\}\in
E(H/\sigma)$ if and only if $\\{v_{1},v_{2}\\}\in E(H)$ for some $v_{1}\in
B_{1}$ and $v_{2}\in B_{2}$. If $H/\sigma$ does not contain loops then it is
called a _spasm_ [23]. These definitions can be adapted in the obvious way for
digraphs.

######  Definition 14 (The DAG $\vec{H}\mathbin{{/}{\sim}}$).

Let $\vec{H}$ be a digraph and let $x,y\in V(\vec{H})$. We denote by $\sim$
the equivalence relation over $V(\vec{H})$ whose classes are the strongly
connected components of $\vec{H}$. We denote by $\vec{H}\mathbin{{/}{\sim}}$
the DAG obtained by deleting loops from the quotient of $\vec{H}$ with respect
to the partition of $V(\vec{H})$ given by $\sim$.

Next we introduce some notions that will be used in our classifications.

######  Definition 15 (Directed split).

The _directed split_ $\vec{H}^{2}$ of a graph $H$ is the digraph obtained from
the $1$-subdivision of $H$ by orienting all edges towards $V(H)$.

##### Homomorphisms and Colourings

A _homomorphism_ from $H$ to $G$ is a map $\varphi:V(H)\\!\rightarrow\\!V(G)$
such that $\\{\varphi(u),\varphi(v)\\}\in E(G)$ whenever $\\{u,v\\}\in E(H)$.
The set of all homomorphisms from $H$ to $G$ is denoted by
$\mathsf{Hom}(H\\!\rightarrow\\!G)$. An _$H$ -colouring_ of $G$ is a
homomorphism $c\in\mbox{$\mathsf{Hom}(G\\!\rightarrow\\!H)$}$. An
$H$-_coloured_ graph is a pair $(G,c)$ where $G$ is a graph and $c$ an
$H$-colouring of $G$. A homomorphism
$\varphi\in\mbox{$\mathsf{Hom}(H\\!\rightarrow\\!G)$}$ is color-prescribed (by
$c$) if $c(\varphi(v))=v$ for all $v\in V(H)$. We write
$\mathsf{Hom}(H\\!\rightarrow\\!(G,c))$ for the set of all homomorphisms from
$H$ to $G$ color-prescribed by $c$. These definitions can be adapted for
digraphs in the obvious way; we emphasise that a homomorphism $\varphi$
between digraphs must preserve the direction of the arcs, i.e.,
$(\varphi(u),\varphi(v))\in E(\vec{G})$ whenever $(u,v)\in E(\vec{H})$.

##### Subgraphs and Induced Subgraphs

A _subgraph_ of a graph $G=(V,E)$ is a graph with vertices $\hat{V}\subseteq
V$ and edges $\hat{E}\subseteq\hat{V}^{(2)}\cap E$. We write
$\mathsf{Sub}(H\\!\rightarrow\\!G)$ for the set of all subgraphs of $G$ that
are isomorphic to $H$. Similarly, a subgraph of a digraph $\vec{G}=(V,E)$ is a
digraph with vertices $\hat{V}\subseteq V$ and arcs
$\hat{E}\subseteq\hat{V}^{2}\cap E$, and we denote by
$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$ the set of all subgraphs of
$\vec{G}$ that are isomorphic to $\vec{H}$.

Given a subset of vertices $S$ of a graph $H$, we write $H[S]$ for the graph
_induced_ by $S$, that is $V(H[S]):=S$ and $E(H[S]):=E(H)\cap S^{(2)}$. The
subgraph $\vec{H}[S]$ of a digraph induced by a vertex set $S$ is defined
correspondingly: $V(\vec{H}[S]):=S$ and $E(\vec{H}[S]):=E(\vec{H})\cap S^{2}$.
We write $\mbox{$\mathsf{IndSub}(H\\!\rightarrow\\!G)$}:=\\{S\subseteq
V(G)~{}|~{}G[S]\cong H\\}$ for the set of all induced subgraphs of $G$ that
are isomorphic to $H$. Again, the notion
$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\vec{G})$ is defined similarly for
digraphs.

###  4.2 Hypergraphs

A hypergraph is a pair $\mathcal{H}=(V,E)$ where $V$ is a finite set and
$E\subseteq 2^{V}\setminus\\{\emptyset\\}$. The elements of $E$ are called
hyperedges or simply edges. Given $X\subseteq V$, the subhypergraph of
$\mathcal{H}$ induced by $X$ is the hypergraph $\mathcal{H}[X]$ with vertex
set $X$ and edge set $\\{e\cap X:e\in\mathcal{E}\\}\setminus\\{\emptyset\\}$.
The _arity_ of a hypergraph $\mathcal{G}$, denoted by $a(\mathcal{G})$ is the
maximum cardinality of a hyperedge. We denote hypergraphs with the symbols
$\mathcal{H},\mathcal{G},\ldots$.

######  Definition 16 (Reachability Hypergraph).

Let $\vec{H}$ be a digraph, let $S_{1},\dots,S_{k}\subseteq V(\vec{H})$ be the
sources of $\vec{H}\mathbin{{/}{\sim}}$, and for each $i\in[k]$ let $s_{i}\in
S_{i}$. The _reachability hypergraph_ $\mathcal{R}(\vec{H})$ of $\vec{H}$ has
vertex set $V(\vec{H})$ and edge set $\\{e_{i}=R(s_{i}):i\in[k]\\}$.

Note that $\mathcal{R}(\vec{H})$ is well defined, since $S_{i}$ is a strongly
connected component of $\vec{H}$ and so the choice of $s_{i}\in S_{i}$ is
irrelevant. If $\vec{H}$ is a DAG, then $\mathcal{R}(\vec{H})$ is the
reachability hypergraph in the usual sense.

The following special case of DAGs, defined via reachability hypergraphs, will
turn out to be crucial for our lower bounds.

######  Definition 17 (Canonical DAGs).

Let $\mathcal{R}$ be a reachability hypergraph. For every $e\in
E(\mathcal{R})$ fix some $s_{e}\in V(\mathcal{R})$ such that $s_{e}$ is
contained only in $e$. The _canonical DAG_ $\vec{H}$ of $\mathcal{R}$ is
defined by $V(\vec{H})=V(\mathcal{R})$ and $E(\vec{H})=\\{(s_{e},v):e\in
E(\mathcal{R}),v\in e\setminus\\{s_{e}\\}\\}$.

Note that if $\vec{H}$ is a canonical DAG of $\mathcal{R}$ then $\mathcal{R}$
is the reachability hypergraph of $\vec{H}$. If a DAG $\vec{H}$ is the
canonical DAG of its own reachability hypergraph, then we just say $\vec{H}$
is a canonical DAG. Equivalently, a DAG $\vec{H}$ is a canonical DAG if every
vertex is either a source or a sink.

######  Definition 18 (Contour).

Let $\vec{H}$ be a digraph, let $S_{1},\dots,S_{k}\subseteq V(\vec{H})$ be the
sources of $\vec{H}\mathbin{{/}{\sim}}$, and for each $i\in[k]$ let $s_{i}\in
S_{i}$. The _contour_ $\Gamma(\vec{H})$ of $\vec{H}$ is the hypergraph
obtained from $\mathcal{R}(\vec{H})$ by deleting $S_{i}$ from $e_{i}$ for each
$i\in[k]$.

##### Invariants and Width Measures

In what follows, we are using the notation of [33] and [40], and we recall the
most important definitions.

######  Definition 19 (Tree decompositions).

Let $\mathcal{H}$ be a hypergraph. A _tree decomposition_ of $\mathcal{H}$ is
a pair of a tree $\mathcal{T}$ and a set of subsets of $V(\mathcal{H})$,
called _bags_ , $\mathcal{B}=\\{B_{t}\\}_{t\in V(\mathcal{T})}$ such that the
following conditions are satisfied:

  1. 1.

$\bigcup_{t\in V(\mathcal{T})}B_{t}=V(\mathcal{H})$.

  2. 2.

For every hyperedge $e\in E(\mathcal{H})$ there is a bag $B_{t}$ such that
$e\subseteq B_{t}$.

  3. 3.

For every vertex $v\in V(\mathcal{H})$, the subgraph
$\mathcal{T}[\\{t~{}|~{}v\in B_{t}\\}]$ of $\mathcal{T}$ is connected.

######  Definition 20 ($f$-width).

Let $\mathcal{H}$ be a hypergraph, let
$f:2^{V(\mathcal{H})}\rightarrow\mathbb{R}_{+}$, and let
$(\mathcal{T},\mathcal{B})$ be a tree decomposition of $\mathcal{H}$. The
$f$-_width_ of $(\mathcal{T},\mathcal{B})$ is defined as follows:

${f}\mathchar 45\relax\mathsf{width}(\mathcal{T},\mathcal{B}):=\max_{t\in
V(\mathcal{T})}f(B_{t})\,.$

The $f$-width of $\mathcal{H}$ is the minimum $f$-width of any tree
decomposition of $\mathcal{H}$.

For example, the _treewidth_ of a (hyper-)graph is just its $f$-width for the
function $f(B):=|B|-1$.

Given a hypergraph $\mathcal{H}$ and a vertex-subset $X$ of $\mathcal{H}$, the
_edge cover number_ $\rho_{\mathcal{H}}(X)$ of $X$ is the minimum number of
hyperedges of $\mathcal{H}$ required to cover each vertex in $X$. The _edge
cover number_ of $\mathcal{H}$, denoted by $\rho(\mathcal{H})$, is defined as
$\rho_{\mathcal{H}}(V(\mathcal{H}))$.

A _fractional_ version of the edge cover number of defined similarly: Given
$\mathcal{H}$ and $X$ as above, a function
$\gamma:E(\mathcal{H})\rightarrow[0,\infty]$ is a fractional edge cover of $X$
if for each $v\in X$ we have $\sum_{e:v\in e}\gamma(e)\geq 1$. The fractional
edge cover number $\rho_{\mathcal{H}}^{\ast}(X)$ of $X$ is defined to be the
minimum of $\sum_{e\in E(\mathcal{H})}\gamma(e)$ among all fractional edge
covers $\gamma$ of $X$. The _fractional edge cover number_ of $\mathcal{H}$,
denoted by $\rho^{\ast}(\mathcal{H})$, is defined as
$\rho^{\ast}_{\mathcal{H}}(V(\mathcal{H}))$.

######  Definition 21 (Generalised and Fractional Hyper-Treewidth).

The generalised hyper-treewidth of $\mathcal{H}$, denoted by
$\mathsf{htw}(\mathcal{H})$, is the $\rho_{\mathcal{H}}$-width of
$\mathcal{H}$. The fractional hyper-treewidth of $\mathcal{H}$, denoted by
$\mathsf{fhtw}(\mathcal{H})$, is the $\rho_{\mathcal{H}}^{\ast}$-width of
$\mathcal{H}$.

An _independent set_ of a hypergraph $\mathcal{H}$ is a set $I$ of vertices
such that, for each $u,v\in I$ with $u\neq v$, there is no hyperedge
containing $u$ and $v$. The _independence number_ of $\mathcal{H}$, denoted by
$\alpha(\mathcal{H})$, is the size of a maximum independent set of
$\mathcal{H}$. A _fractional independent set_ of a hypergraph $\mathcal{H}$ is
a mapping $\alpha^{\ast}:V(\mathcal{H})\rightarrow[0,1]$ such that for each
$e\in E(\mathcal{H})$ we have

$\sum_{v\in e}\alpha^{\ast}(v)\leq 1\,.$

The _fractional independence number_ of $\mathcal{H}$, denoted by
$\alpha^{\ast}(\mathcal{H})$ is the maximum of $\sum_{v\in e}\alpha^{\ast}(v)$
among all fractional independent sets $\alpha^{\ast}$. For a subset $X$ of
vertices in $V(\mathcal{H})$, we set $\alpha^{\ast}(X)=\sum_{v\in
X}\alpha^{\ast}(v)$. We remark that, by LP duality, the fractional
independence number and the fractional edge cover number are equal (see,
[47]):

######  Fact 22.

Let $\mathcal{H}$ be a hypergraph. We have
$\alpha^{\ast}(\mathcal{H})=\rho^{\ast}(\mathcal{H})$.

We continue with the notion of adaptive width, which is equivalent444Here,
“equivalent” means that a class of hypergraphs has bounded adaptive width if
and only if it has bounded submodular width. to submodular width as shown by
Marx [40].

######  Definition 23 (Adaptive width).

Let $\mathcal{H}$ be a hypergraph. The _adaptive width_ of $\mathcal{H}$ is

$\operatorname{aw}(\mathcal{H}):=\sup\left\\{\alpha^{\ast}\text{-width}(\mathcal{H})\mid\alpha^{\ast}\text{
is a fractional independent set of }\mathcal{H}\right\\}\,.$

######  Lemma 24 ([40]).

Let $\mathcal{C}$ be a class of hypergraphs. Then

$\displaystyle~{}~{}\mathcal{C}\text{ has unbounded adaptive width}$
$\displaystyle\Rightarrow$ $\displaystyle~{}~{}\mathcal{C}\text{ has unbounded
fractional hyper-treewidth}$ $\displaystyle\Rightarrow$
$\displaystyle~{}~{}\mathcal{C}\text{ has unbounded generalised hyper-
treewidth}\,.$

Furthermore, all of the above implications are strict, that is, there are
classes $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ such that $\mathcal{C}_{1}$
has bounded adaptive width but unbounded fractional hyper-treewidth, and
$\mathcal{C}_{2}$ has bounded fractional hyper-treewidth but unbounded
generalised hyper-treewidth.

Throughout this paper, we will be interested in the independence number
$\alpha$, the fractional independence number $\alpha^{\ast}$, and the adaptive
width $\operatorname{aw}$ of the contours of digraphs $\vec{H}$. The following
lemma shows that it is equivalent to consider the contour of
$\vec{H}\mathbin{{/}{\sim}}$ for those invariants.

######  Lemma 25.

Let $\vec{H}$ be a digraph. We have

  1. 1.

$\alpha(\Gamma(\vec{H}))=\alpha(\Gamma(\vec{H}\mathbin{{/}{\sim}}))$.

  2. 2.

$\alpha^{\ast}(\Gamma(\vec{H}))=\alpha^{\ast}(\Gamma(\vec{H}\mathbin{{/}{\sim}}))$
and
$\rho^{\ast}(\Gamma(\vec{H}))=\rho^{\ast}(\Gamma(\vec{H}\mathbin{{/}{\sim}}))$.

  3. 3.

$\operatorname{aw}(\Gamma(\vec{H}))=\operatorname{aw}(\Gamma(\vec{H}\mathbin{{/}{\sim}}))$.

###### Proof.

Recall that $\vec{H}\mathbin{{/}{\sim}}$ is obtained from $\vec{H}$ by
contracting each strongly connected component into a single vertex. In the
reachability hypergraph, and thus in the contour, this corresponds to
identifying blocks of vertices $B=\\{v_{1},\dots,v_{\ell}\\}$ satisfying that
all vertices in $B$ are contained in the same (non-empty) set of hyperedges,
that is, there is a non-empty set of hyperedges $E_{B}$ such that for each
$i\in[\ell]$, the set of hyperedges containing $v_{i}$ is $E_{B}$.

Hence it is sufficient to show that identifying the vertices in $B$ — we call
the resulting vertex $v_{B}$ — does not change any of the invariants $\alpha$,
$\alpha^{\ast}$, and $\operatorname{aw}$. For what follows, let us write
$\mathcal{H}$ for the contour $\Gamma(\vec{H})$ of $\vec{H}$, and let us write
$\mathcal{H}^{\prime}$ for the hypergraph obtained from $\mathcal{H}$ obtained
by contracting $B$ to $v_{B}$. Furthermore, let $E^{\prime}_{B}$ be the set of
hyperedges that contain $v_{B}$ and observe that $E^{\prime}_{B}$ can be
obtained from $E_{B}$ by contracting $B$ to $v_{B}$ for each edge $e\in
E_{B}$.

  1. 1.

Goal: $\alpha(\mathcal{H})=\alpha(\mathcal{H}^{\prime})$. Let $S\subseteq
V(\mathcal{H})$ be a maximum independent set of $\mathcal{H}$. Note that at
most one vertex in $B$ can be contained in $S$. If no vertex of $S$ is
contained in $B$, then $S$ is an independent set of $\mathcal{H}^{\prime}$.
Otherwise, assume $v_{i}\in S$ for some $i\in[\ell]$. Then
$S^{\prime}:=(S\setminus\\{v_{i}\\})\cup\\{v_{B}\\}$ is an independent set of
$\mathcal{H}^{\prime}$. This shows that
$\alpha(\mathcal{H})\leq\alpha(\mathcal{H}^{\prime})$.

For the other direction, let $S^{\prime}$ be a maximum independent set of
$\mathcal{H}^{\prime}$. If $v_{B}\in S^{\prime}$, then we set
$S:=(S^{\prime}\setminus\\{v_{B}\\})\cup\\{v_{1}\\}$. Otherwise, we set
$S:=S^{\prime}$. Clearly, $S$ is an independent set of $\mathcal{H}$ and thus
$\alpha(\mathcal{H})\geq\alpha(\mathcal{H}^{\prime})$.

  2. 2.

Goal: $\alpha^{\ast}(\mathcal{H})=\alpha^{\ast}(\mathcal{H}^{\prime})$ (Note
that this is equivalent to
$\rho^{\ast}(\mathcal{H})=\rho^{\ast}(\mathcal{H}^{\prime})$ by Fact 22). Let
$\mu$ be a fractional independent set of $\mathcal{H}$ of maximum weight.
Define

$\mu^{\prime}(v):=\begin{cases}\sum_{i=1}^{\ell}\mu(v_{i})&v=v_{B}\\\
\mu(v)&v\neq v_{B}\end{cases}\,.$

We claim that $\mu^{\prime}$ is a fractional independent set of
$\mathcal{H}^{\prime}$. Let $e^{\prime}\in E(\mathcal{H}^{\prime})$ and let
$e$ be the corresponding edge in $\mathcal{H}$, that is, $e=e^{\prime}$ if
$e^{\prime}\notin E^{\prime}_{B}$, and $e^{\prime}$ is obtained from $e$ by
contracting $B$ into $v_{B}$ otherwise. Depending on whether $e\in E_{B}$ we
have that either $B\subseteq e$ or $B\cap e=\emptyset$. In both cases, by
definition of $\mu^{\prime}$, we have that $\sum_{v^{\prime}\in
e^{\prime}}\mu^{\prime}(v^{\prime})=\sum_{v\in e}\mu(v)\leq 1$. Thus
$\mu^{\prime}$ is a fractional independent set of $\mathcal{H}^{\prime}$.
Since, clearly, $\mu^{\prime}$ has the same total weight as $\mu$, we have
that $\alpha^{\ast}(\mathcal{H})\leq\alpha^{\ast}(\mathcal{H}^{\prime})$.

For the other direction, let $\mu^{\prime}$ be a fractional independent set of
$\mathcal{H}^{\prime}$ of maximum weight. Define

$\mu(v):=\begin{cases}\mu^{\prime}(v_{B})&v=v_{1}\\\ 0&v\in
B\setminus\\{v_{1}\\}\\\ \mu^{\prime}(v)&v\notin B\end{cases}\,.$

We claim that $\mu$ is a fractional independent set of $\mathcal{H}$.
Similarly as in the first direction, let $e\in E(\mathcal{H})$ and let
$e^{\prime}$ be the corresponding edge in $\mathcal{H}^{\prime}$. Again,
depending on whether $e\in E_{B}$, we have that either $B\subseteq e$ or
$B\cap e=\emptyset$, and in both cases, by definition of $\mu$, we have
$\sum_{v\in e}\mu(v)=\sum_{v^{\prime}\in
e^{\prime}}\mu^{\prime}(v^{\prime})\leq 1$. Thus $\mu$ is a fractional
independent set of $\mathcal{H}$. Since, clearly, $\mu$ has the same total
weight as $\mu^{\prime}$, we have that
$\alpha^{\ast}(\mathcal{H})\geq\alpha^{\ast}(\mathcal{H}^{\prime})$.

  3. 3.

Goal:
$\operatorname{aw}(\mathcal{H})=\operatorname{aw}(\mathcal{H}^{\prime})$. Any
tree decomposition $(\mathcal{T},\mathcal{B})$ of $\mathcal{H}$ can be
transformed to a tree decomposition
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of $\mathcal{H}^{\prime}$ as
follows: In each bag that contains a vertex in $B$, we delete all vertices in
$B$ and add $v_{B}$. Clearly, the union over all bags in
$\mathcal{B}^{\prime}$ is the set of all vertices of $\mathcal{H}^{\prime}$,
and each hyperedge of $\mathcal{H}^{\prime}$ is fully contained in some bag.
For the last condition necessary for
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ being a tree decomposition of
$\mathcal{H}^{\prime}$, we have to show that for each $v^{\prime}\in
V(\mathcal{H}^{\prime})$, the subgraph $\mathcal{T}^{\prime}_{v}$ of
$\mathcal{T}$ consisting of the bags containing $v^{\prime}$ is connected. If
$v^{\prime}\neq v_{B}$ then this property immediately follows from
$(\mathcal{T},\mathcal{B})$ being a tree decomposition. For $v=v_{B}$ we use
that $\mathcal{T}_{v_{i}}$ is connected for each $i\in[\ell]$ since
$(\mathcal{T},\mathcal{B})$ is a tree decomposition of $\mathcal{H}$. Now
$\mathcal{T}^{\prime}_{v_{B}}$ corresponds, by definition of
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$, to the union of all the
$\mathcal{T}_{v_{i}}$. However, since $E_{B}\neq\emptyset$, there is a
hyperedge $e$ of $\mathcal{H}$ fully containing $B$. Since $e$ must be fully
contained in a bag of $(\mathcal{T},\mathcal{B})$, all of the
$\mathcal{T}_{v_{i}}$ overlap in at least one vertex, and thus
$\mathcal{T}^{\prime}_{v_{B}}$ is connected, proving that
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ is indeed a tree decomposition
of $\mathcal{H}^{\prime}$. For what follows, let $\tau$ denote the function
that maps a tree decomposition $(\mathcal{T},\mathcal{B})$ of $\mathcal{H}$ to
a tree decomposition $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of
$\mathcal{H}^{\prime}$ as defined above.

In the other direction, each tree decomposition
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of $\mathcal{H}^{\prime}$ can be
made a tree decomposition of $\mathcal{H}$ by substituting $v_{B}$ with the
vertices in $B$. In this direction, it is clear that this yields a tree
decomposition $(\mathcal{T},\mathcal{B})$ of $\mathcal{H}$. For what follows,
let $\tau^{\prime}$ denote the function that maps a tree decomposition
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of $\mathcal{H}^{\prime}$ to a
tree decomposition $(\mathcal{T},\mathcal{B})$ of $\mathcal{H}$ as defined
above.

Now let $\operatorname{aw}(\mathcal{H})=a$. We prove that
$\operatorname{aw}(\mathcal{H}^{\prime})\leq a$. Let $\mu^{\prime}$ be a
fractional independent set of $\mathcal{H}^{\prime}$. We have to show that
there is a tree decomposition $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of
$\mathcal{H}^{\prime}$ with $\mu^{\prime}\mathchar
45\relax\mathsf{width}(\mathcal{T}^{\prime},\mathcal{B}^{\prime})\leq a$. To
this end, let $\mu$ be the fractional independent of $\mathcal{H}$ obtained
from $\mu$ as in 2. Since $\operatorname{aw}(\mathcal{H})=a$, there exists a
tree decomposition $(\mathcal{T},\mathcal{B})$ of $\mathcal{H}$ with
$\mu\mathchar 45\relax\mathsf{width}(\mathcal{T},\mathcal{B})\leq a$. Let
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime}):=\tau(\mathcal{T},\mathcal{B})$.
By definition of $\tau$ and $\mu$, the $\mu^{\prime}\mathchar
45\relax\mathsf{width}$ of $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ is at
most the $\mu\mathchar 45\relax\mathsf{width}$ of $(\mathcal{T},\mathcal{B})$,
which is at most $a$, concluding the first direction.

For the second direction, let
$\operatorname{aw}(\mathcal{H}^{\prime})=a^{\prime}$. We prove that
$\operatorname{aw}(\mathcal{H})\leq a^{\prime}$ similarly as in the first
direction: Starting with a fractional independent set $\mu$ of $\mathcal{H}$,
we consider $\mu^{\prime}$ as constructed in 2, and we obtain a tree
decomposition $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of
$\mathcal{H}^{\prime}$ with $\mu^{\prime}\mathchar
45\relax\mathsf{width}(\mathcal{T}^{\prime},\mathcal{B}^{\prime})\leq
a^{\prime}$. We set
$(\mathcal{T},\mathcal{B}):=\tau^{\prime}(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$
and observe that by definition of $\tau^{\prime}$ and $\mu^{\prime}$, the
$\mu\mathchar 45\relax\mathsf{width}$ of $(\mathcal{T},\mathcal{B})$ is at
most the $\mu^{\prime}\mathchar 45\relax\mathsf{width}$ of
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$, which is at most $a^{\prime}$,
concluding the second direction and thus the proof.

∎

###  4.3 Relational Structures

A _signature_ $\tau$ is a (finite) tuple of relation symbols
$(R_{i})_{i\in[\ell]}$ with arities $(a_{i})_{i\in[\ell]}$. The arity of
$\tau$, denoted by $\mathsf{a}(\tau)$ is the maximum of the $a_{i}$. A
_relational structure_ $\mathcal{A}$ of signature $\tau$ is a tuple
$(V,R_{1}^{\mathcal{A}},\dots,R_{\ell}^{\mathcal{A}})$ where $V$ is a finite
set of elements, called the _universe_ of $\mathcal{A}$, and
$R_{i}^{\mathcal{A}}$ is a relation on $V$ of arity $a_{i}$ for each
$i\in[\ell]$. We emphasize that $R_{i}^{\mathcal{A}}$ is not necessarily
symmetric, and that tuples might contain repeated elements. We will mainly use
the symbols $\mathcal{A}$ and $\mathcal{B}$ to denote relational structures.
Further, we assume that a structure $\mathcal{A}$ is encoded in the standard
way, i.e., the universe and the relations are encoded as lists. We denote by
$|\mathcal{A}|$ the length of the encoding of $\mathcal{A}$.

Given two relational structures $\mathcal{A}$ and $\mathcal{B}$ over the same
signature $\tau$ with universes $U$ and $V$, a _homomorphism_ from
$\mathcal{A}$ to $\mathcal{B}$ is a mapping $\varphi:U\rightarrow V$ such
that, for each $i\in[\mathsf{a}(\tau)]$ and for each tuple $t\in U^{a_{i}}$ we
have

$t\in R_{i}^{\mathcal{A}}\Rightarrow\varphi(t)\in R_{i}^{\mathcal{B}}\,.$

We write $\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$ for the set
of homomorphisms from $\mathcal{A}$ to $\mathcal{B}$.

The hypergraph $\mathcal{H}(\mathcal{A})$ of $\mathcal{A}$ has as vertices the
universe $V$ of $\mathcal{A}$, and for each tuple $t=(v_{1},\dots,v_{a})$ of
elements of $V$, we add an hyperedge $e_{t}=\\{v_{1},\dots,v_{a}\\}$ if and
only if $t$ is an element of a relation of $\mathcal{A}$. To avoid notational
clutter, we will define the treewidth, the hypertreewidth, the fractional
hypertreewidth and the submodular width of a structure as the respective width
measure of its hypergraph. Similarly, a tree decomposition of a structure
refers to a tree decomposition of its hypergraph.

###  4.4 Parameterised and Fine-Grained Complexity Theory

A _parameterised counting problem_ is a pair $(P,\kappa)$ of a counting
problem $P:\\{0,1\\}^{\ast}\\!\rightarrow\\!\mathbb{N}$ and a computable
function $\kappa:\\{0,1\\}^{\ast}\\!\rightarrow\\!\mathbb{N}$, called the
_parameterisation_. Consider for example the parameterised clique counting
problem:

An algorithm for a parameterised (counting) problem is called a _fixed-
parameter tractable_ (FPT) algorithm if there is a computable function $f$
such that, on input $x$, its running time can be bounded by
$f(\kappa(x))\cdot|x|^{O(1)}$. A parameterised (counting) problem is called
_fixed-parameter tractable_ if it can be solved by an FPT algorithm.

A _parameterised Turing-reduction_ from $(P,\kappa)$ to
$(P^{\prime},\kappa^{\prime})$ is an FPT algorithm for $(P,\kappa)$ with
oracle access to $P^{\prime}$, additionally satisfying that there is a
computable function $g$ such that, on input $x$, the parameter
$\kappa^{\prime}(y)$ of any oracle query is bounded by $g(\kappa(x))$. We
write $(P,\kappa)\leq^{\mathrm{fpt}}_{\mathrm{T}}(P^{\prime},\kappa^{\prime})$
if a parameterised Turing-reduction exists.

We say that $(P,\kappa)$ is $\\#\mathsf{W[1]}$_-hard_ if
$\\#\textsc{Clique}\leq^{\mathrm{fpt}}_{\mathrm{T}}(P,\kappa)$. The class
$\\#\mathsf{W[1]}$ can be considered a parameterised counting equivalent of
$\mathrm{NP}$, and we refer the interested reader to Chapter 14 in the
standard textbook of Flum and Grohe [29] for a comprehensive introduction. It
is known that $\\#\mathsf{W[1]}$-hard problems are not fixed-parameter
tractable unless standard assumptions, such as ETH, fail:

######  Definition 26 (The Exponential Time Hypothesis (ETH) [34]).

The Exponential Time Hypothesis (ETH) asserts that $3$-SAT cannot be solved in
time $\mathsf{exp}(o(n))$, where $n$ is the number of variables.

######  Theorem 27 (Chen et al. [16, 17]).

Assume that ETH holds. Then there is no function $f$ such that
$\\#\textsc{Clique}$ can be solved in time $f(k)\cdot|G|^{o(k)}$.

Note that the previous theorem rules out an FPT algorithm for
$\\#\textsc{Clique}$ (and thus all $\\#\mathsf{W[1]}$-hard problems), unless
ETH fails.

####  4.4.1 Parameterised Counting Problems

The following parameterized problems are central to the present work. In what
follows $\vec{C}$ denotes a class of directed graphs, and $\mathcal{C}$
denotes a class of hypergraphs.

It was shown by Grohe and Marx [33] that the decision version of
$\\#\textsc{CSP}(\mathcal{C})$ can be solved in polynomial time if the
fractional hypertreewidth of $\mathcal{C}$ is bounded. More precisely, they
discovered an algorithm that solves the decision problem in time

$(|\mathcal{A}|+|\mathcal{B}|)^{r+O(1)}\,,$

assuming that a tree decomposition of $\mathcal{A}$ of $\rho^{\ast}$-width at
most $r$ is given (see Theorem 3.5 and Lemma 4.9 in [33]); recall that the
$\rho^{\ast}$-width of a tree decomposition is the maximum fractional edge
cover number of a bag. In particular, they show that the partial solutions of
each bag can be enumerated in time $(|\mathcal{A}|+|\mathcal{B}|)^{r+O(1)}$.
Thus the dynamic programming algorithm that solves the decision version
immediately extends to counting. Finally, since computing such an optimal tree
decomposition can be done in time only depending on $\mathcal{A}$, we obtain
the following overall running time for the counting problem:

######  Theorem 28.

Let $\mathcal{A}$ and $\mathcal{B}$ be relational structures over the same
signature and let $r$ be the fractional hypertreewidth of $\mathcal{A}$. There
is a computable function $f$ such that we can compute
$\\#\mbox{$\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$}$ in time

$f(|\mathcal{A}|)\cdot|\mathcal{B}|^{r+O(1)}\,.$

In particular, $\\#\textsc{CSP}(\mathcal{C})$ is fixed-parameter tractable if
$\mathcal{C}$ has bounded fractional hypertreewidth.

##  5 The Directed Homomorphism Basis and Dedekind’s Theorem

In this section, we will revisit the interpolation technique for evaluating
linear combinations of homomorphism counts due to Curticapean, Dell and Marx
[23], and we will extend their framework from undirected graphs to digraphs.
We wish to point out that most of the results presented in this section are
easy consequences and generalisations of methods known in the literature [38,
15, 23, 26]; and we only provide the details for reasons of self-containment.
For the purpose of this section, we assume that finitely supported functions
$\iota$ from digraphs to rationals are encoded as a list of elements
$(\vec{F},\iota(\vec{F}))$ for all $\vec{F}$ with $\iota(\vec{F})\neq 0$. We
write $|\iota|$ for the encoding length of $\iota$.

To begin with, given a digraph $\vec{H}$, recall that
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\star)$}$ and
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}$ denote the
functions that map a digraph $\vec{G}$ to
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ and
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\vec{G})$}$, respectively.

For our reductions, we express both functions
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\star)$}$ and
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}$ as linear
combinations of homomorphism counts from digraphs. We start with
$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\star)$}$ and point out that,
similarly to the argument in [23], the existence of the following
transformation follows from Möbius Inversion over the partition lattice as
shown by Lovász (see Chapter 5.2.3 in [38]).555In fact, Lemma 29 and Lemma 32
are special cases of more general transformations for counting answers to
conjunctive queries with disequalities and negations [26].

######  Lemma 29.

Let $\vec{H}$ be a digraph. There exists a (unique and computable) function
${\mathsf{sub}}_{\vec{H}}$ from digraphs to rationals such that

$\\#\mbox{$\mathsf{Sub}(\vec{H}\\!\rightarrow\\!\star)$}=\sum_{\vec{F}}{\mathsf{sub}}_{\vec{H}}(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\star)$}\,,$

where the sum is over all (isomorphism classes of) digraphs $\vec{F}$.
Moreover, the function ${\mathsf{sub}}_{\vec{H}}$ has finite support, and
satisfies ${\mathsf{sub}}_{\vec{H}}(\vec{F})\neq 0$ if and only if $\vec{F}$
is a quotient graph of $\vec{H}$.

A similar transformation is known for
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}$ which relies on
_arc supergraphs_.

######  Definition 30 (Arc supergraphs).

Let $\vec{H}_{1}=(V_{1},E_{2})$ and $\vec{H}_{2}=(V_{2},E_{2})$ be digraphs
without loops. We say that $\vec{H}_{2}$ is an _arc supergraph_ of
$\vec{H}_{1}$ if $V_{1}=V_{2}$ and $E_{1}\subseteq E_{2}$.

In the first step, using the inclusion-exclusion principle,
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}$ can be cast as a
linear combination of subgraph counts (the proof is analogous to the
undirected setting; see [23] and [38, Chapter 5.2.3]):

######  Lemma 31.

Let $\vec{H}$ be a digraph. There exists a (unique and computable) function
${\mathsf{indsub}}^{\ast}_{\vec{H}}$ from digraphs to rationals such that

$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}=\sum_{\vec{F}^{\prime}}{\mathsf{indsub}}^{\ast}_{\vec{H}}(\vec{F}^{\prime})\cdot\\#\mbox{$\mathsf{Sub}(\vec{F}^{\prime}\\!\rightarrow\\!\star)$}\,,$

where the sum is over all (isomorphism classes of) digraphs
$\vec{F}^{\prime}$. Moreover, the function
${\mathsf{indsub}}^{\ast}_{\vec{H}}$ has finite support and satisfies
${\mathsf{indsub}}^{\ast}_{\vec{H}}(\vec{F}^{\prime})\neq 0$ if and only if
$\vec{F}^{\prime}$ is an arc supergraph of $\vec{H}$.

In combination, the previous two lemmas allow us to cast
$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}$ as a linear
combination of homomorphism counts.

######  Lemma 32.

Let $\vec{H}$ be a digraph. There exists a (unique and computable) function
${{\mathsf{indsub}}}_{\vec{H}}$ from digraphs to rationals such that

$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}=\sum_{\vec{F}}{{\mathsf{indsub}}}_{\vec{H}}(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\star)$}\,,$

where the sum is over all (isomorphism classes of) digraphs $\vec{F}$.
Moreover, ${{\mathsf{indsub}}}_{\vec{H}}$ satisfies the following conditions:

  1. 1.

${{\mathsf{indsub}}}_{\vec{H}}$ has finite support.

  2. 2.

If ${{\mathsf{indsub}}}_{\vec{H}}(\vec{F})\neq 0$ then $\vec{F}$ is a quotient
of an arc supergraph of $\vec{H}$.

  3. 3.

If $\vec{F}$ is an arc supergraph of $\vec{H}$, then
${{\mathsf{indsub}}}_{\vec{H}}(\vec{F})\neq 0$.

###### Proof.

We first apply the transformation from induced subgraphs to subgraphs as in
Lemma 31, second, we apply the transformation from subgraphs to homomorphisms
as in Lemma 29. We obtain

$\\#\mbox{$\mathsf{IndSub}(\vec{H}\\!\rightarrow\\!\star)$}=\sum_{\vec{F}^{\prime}}{\mathsf{indsub}}^{\ast}_{\vec{H}}(\vec{F}^{\prime})\cdot\sum_{\vec{F}}{\mathsf{sub}}_{\vec{F}^{\prime}}(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\star)$}\,.$
(5)

The coefficients ${\mathsf{indsub}}_{\vec{H}}$ are then obtained by collecting
for isomorphic terms, that is

${\mathsf{indsub}}_{\vec{H}}(\vec{F})=\sum_{\vec{F}^{\prime}}{\mathsf{indsub}}^{\ast}_{\vec{H}}(\vec{F}^{\prime})\cdot{\mathsf{sub}}_{\vec{F}^{\prime}}(\vec{F})\,.$
(6)

Note that 1 and 2 follow immediately from the properties of ${\mathsf{sub}}$
and ${\mathsf{indsub}}^{\ast}$. It remains to show 3: To this end, let
$\vec{F}$ be an _arc supergraph_ of $\vec{H}$. Then, for each arc supergraph
$\vec{F}^{\prime}$ of $\vec{H}$, the only quotient graph of $\vec{F}^{\prime}$
that can be isomorphic to $\vec{F}$ is $\vec{F}^{\prime}$ itself, since all
other quotients have fewer vertices. By Lemma 29 we hence have that arc
supergraphs $\vec{F}$ and $\vec{F}^{\prime}$ of $\vec{H}$ satisfy that
${\mathsf{sub}}_{\vec{F}^{\prime}}(\vec{F})\neq 0$ implies
$\vec{F}\cong\vec{F}^{\prime}$. Finally, Lemma 31 asserts that
${\mathsf{indsub}}^{\ast}_{\vec{H}}(\vec{F}^{\prime})\neq 0$ if and only if
$\vec{F}^{\prime}$ is an arc supergraph of $\vec{H}$. Thus, using that
$\vec{F}$ is an arc supergraph of $\vec{H}$, we have that (6) simplifies to
${\mathsf{indsub}}_{\vec{H}}(\vec{F})={\mathsf{indsub}}^{\ast}_{\vec{H}}(\vec{F})$,
which is non-zero by Lemma 31. This concludes the proof. ∎

A Remark on loops: Readers familiar with [23] might notice that the quotient
graphs in Lemma 29 and the arc supergraphs in Lemma 32 may have loops although
loops are forbidden in [23]. The reason for this is the fact that we allow
digraphs to contain loops, whereas undirected graphs in [23] are not allowed
to contain loops. However, we emphasize that our hardness results will also
apply to the restricted case of digraphs without loops. This will be made
explicit in the respective sections.

Next we show that the interpolation method in [23] for evaluating linear
combinations of homomorphism counts transfers to the directed setting as well.
The algorithm will be the same as in [23]; however, our correctness proof will
be both more concise and more general at the same time by relying on a
classical result of Dedekind.

######  Lemma 33.

There exists a deterministic algorithm $\mathbb{A}$ with the following
specification:

  * •

The input of $\mathbb{A}$ is a pair of a digraph $\vec{{G}}^{\prime}$ with
outdegree $d$ and a function $\iota$ from digraphs to rationals of finite
support.

  * •

$\mathbb{A}$ is equipped with oracle access to the function

$\vec{G}\mapsto\sum_{\vec{F}}\iota(\vec{F})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}\,,$

where the sum is over all (isomorphism classes of) digraphs.

  * •

The output of $\mathbb{A}$ is the list with elements
$(\vec{F},\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{{G}}^{\prime})$})$
for each $\vec{F}$ with $\iota(\vec{F})\neq 0$.

Additionally, for some computable function
$f:\mathbb{N}\\!\rightarrow\\!\mathbb{N}$ the running time of $\mathbb{A}$ is
bounded by $f(|\iota|)\cdot|\vec{{G}}^{\prime}|^{O(1)}$ and the outdegree of
every oracle query $\vec{G}$ is at most $f(|\iota|)\cdot d$.

Similar algorithms exist for the restricted cases of digraphs without loops
and DAGs.

The proof of the previous lemma requires some additional set-up. For what
follows, we let $\vec{\mathcal{U}}^{\circ}$ be the class of all digraphs, and
we let $\vec{\mathcal{U}}$ be the class of all digraphs without loops, and we
let $\vec{\mathcal{D}}$ be the class of all DAGs. Next, consider the following
operation on digraphs:

######  Definition 34 (Tensor product).

The tensor product $\vec{G}\otimes\vec{F}$ of two digraphs $\vec{G}$ and
$\vec{F}$ is the digraph with $V(\vec{G}\otimes\vec{F})=V(\vec{G})\times
V(\vec{F})$ and with $((a,b),(c,d))\in E(\vec{G}\otimes\vec{F})$ iff $(a,c)\in
E(\vec{G})$ and $(b,d)\in E(\vec{F})$.

A _semigroup_ is a pair of a set $\mathrm{G}$ and an associative operation
$\ast$ on $\mathrm{G}$. Now observe that the tensor product of digraphs is
clearly associative, that is,
$\vec{G}\otimes(\vec{F}\otimes\vec{H})\cong(\vec{G}\otimes\vec{F})\otimes\vec{H}$
given by the isomorphism $(u,(v,w))\mapsto((u,v),w)$. Observe further that the
tensor product of two digraphs without loops does not contain loops, and that
the tensor product of two DAGs is again a DAG. Consequently, we obtain three
semigroups:

######  Observation 35.

$(\vec{\mathcal{U}}^{\circ},\otimes)$, $(\vec{\mathcal{U}},\otimes)$, and
$(\vec{\mathcal{D}},\otimes)$ are semigroups.

The fact that the tensor product induces a semigroup will allow us to invoke
constructive version of Dedekind’s Theorem on the linear independence of
characters from Artin [5, Theorem 12].666Note that Artin states Dedekind’s
Theorem for the case of $(\mathrm{G},\ast)$ being a group, rather than a
semigroup. However, the proof only needs associativity of the operation $\ast$
and thus applies for the more general case of semigroups as well. Since Artin
does not state the constructive version explicitly - it only follows from
their proof - we provide a self-contained argument in Appendix A for the
reader’s convenience.

######  Theorem 36.

Let $(\mathrm{G},\ast)$ be a semigroup. Let $(\varphi_{i})_{i\in[k]}$ with
$\varphi_{i}:\mathrm{G}\\!\rightarrow\\!\mathbb{Q}$ be pairwise distinct
semigroup homomorphisms of $(\mathrm{G},\ast)$ into $(\mathbb{Q},\cdot)$, that
is, $\varphi_{i}(g_{1}\ast g_{2})=\varphi_{i}(g_{1})\cdot\varphi_{i}(g_{2})$
for all $i\in[k]$ and $g_{1},g_{2}\in\mathrm{G}$. Let
$\phi:G\\!\rightarrow\\!\mathbb{Q}$ be a function

$\phi:g\mapsto\sum_{i=1}^{k}a_{i}\cdot\varphi_{i}(g)\,,$ (7)

where the $a_{i}$ are rational numbers. Suppose furthermore that the following
functions are computable:

  1. 1.

The operation $\ast$.

  2. 2.

The mapping $(i,g)\mapsto\varphi_{i}(g)$.

  3. 3.

A mapping $i\mapsto g_{i}$ such that $\varphi_{i}(g_{i})\neq 0$.

  4. 4.

A mapping $(i,j)\mapsto g_{i,j}$ such that
$\varphi_{i}(g_{i,j})\neq\varphi_{j}(g_{i,j})$ whenever $i\neq j$.

Then there is a constant $B$ only depending on the $\varphi_{i}$ (and not on
the $a_{i}$), and an algorithm $\hat{\mathbb{A}}$ such that the following
conditions are satisfied:

  * •

$\hat{\mathbb{A}}$ is equipped with oracle access to $\phi$.

  * •

$\hat{\mathbb{A}}$ computes $a_{1},\ldots,a_{k}$.

  * •

Each oracle query $\hat{g}$ only depends on the $\varphi_{i}$ (and not on the
$a_{i}$).

  * •

The running time of $\hat{\mathbb{A}}$ is bounded by
$O\left(B\cdot\sum_{i=1}^{k}\log a_{i}\right)$

We aim to apply Theorem 36 to prove Lemma 33. However, this requires us to
establish the following properties:

######  Lemma 37.

The following conditions are satisfied:

  1. 1.

For every $\vec{H}\in\vec{\mathcal{U}}^{\circ}$ the function
$\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\star)$}$ is a homomorphism
from $(\vec{\mathcal{U}}^{\circ},\otimes)$ into $(\mathbb{Q},\cdot)$, that is,
$\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G}\otimes\vec{F})$}=\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}\cdot\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{F})$}$
for all $\vec{G},\vec{F}\in\vec{\mathcal{U}}^{\circ}$.

  2. 2.

$\\#\mbox{$\mathsf{Hom}(\vec{H}_{1}\\!\rightarrow\\!\star)$}\neq\\#\mbox{$\mathsf{Hom}(\vec{H}_{2}\\!\rightarrow\\!\star)$}$
whenever $\vec{H}_{1}\in\vec{\mathcal{U}}^{\circ}$ and
$\vec{H}_{2}\in\vec{\mathcal{U}}^{\circ}$ are non-isomorphic.

The same holds true in the restricted cases of digraphs without loops and
DAGs, that is, the same holds true if $\vec{\mathcal{U}}^{\circ}$ is
substituted by $\vec{\mathcal{U}}$ or $\vec{\mathcal{D}}$.

###### Proof.

The first claim is immediate since, by definition of $\otimes$, each
$\varphi\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G}\otimes\vec{F})$}$
decomposes (via projection) to
$\varphi_{1}\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ and
$\varphi_{2}\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{F})$}$, which
induces a bijection.

For the second claim we follow a classical argument by Lovász (see Chapter 5.4
in [38]). For any two $\vec{F},\vec{G}\in\vec{\mathcal{U}}^{\circ}$ define:

$\displaystyle\\#\mathsf{Sur}(\vec{F}\\!\rightarrow\\!\vec{G}):=\\{\varphi\in\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G})$}~{}|~{}\varphi\text{
is vertex-surjective}\\}$ (8)

For any $S\subseteq V(\vec{G})$ let $\vec{G}[S]$ be the subgraph of $\vec{G}$
induced by $S$. By inclusion and exclusion:

$\displaystyle\\#\mathsf{Sur}(\vec{F}\\!\rightarrow\\!\vec{G})$
$\displaystyle=\sum_{S\subseteq V(\vec{G})}(-1)^{|V(\vec{G})\setminus
S|}\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\vec{G}[S])$}$ (9)

Now assume for contradiction that
$\\#\mbox{$\mathsf{Hom}(\vec{H}_{1}\\!\rightarrow\\!\star)$}=\\#\mbox{$\mathsf{Hom}(\vec{H}_{2}\\!\rightarrow\\!\star)$}$
for two non-isomorphic $\vec{H}_{1},\vec{H}_{2}\in\vec{\mathcal{U}}^{\circ}$.
Then for $\vec{G}=H_{1}$ (9) yields
$\\#\mathsf{Sur}(\vec{H_{2}}\\!\rightarrow\\!\vec{H_{1}})=\\#\mathsf{Sur}(\vec{H_{1}}\\!\rightarrow\\!\vec{H_{1}})>0$,
and for $\vec{G}=\vec{H}_{2}$ it yields
$\\#\mathsf{Sur}(\vec{H_{1}}\\!\rightarrow\\!\vec{H_{2}})=\\#\mathsf{Sur}(\vec{H_{2}}\\!\rightarrow\\!\vec{H_{2}})>0$.
Hence there are surjective homomorphisms of $\vec{H}_{1}$ into $\vec{H}_{2}$
and of $\vec{H}_{2}$ into $\vec{H}_{1}$. But then $\vec{H}_{1}$ and
$\vec{H}_{2}$ are isomorphic, which yields the desired contradiction. ∎

We are now able to proof Lemma 33.

###### Proof of Lemma 33.

Let $\vec{G}^{\prime}$ and $\iota$ be the input. We apply Dedekind’s Theorem
(Theorem 36) to the semigroup $(\vec{\mathcal{U}}^{\circ},\otimes)$ and
mappings
$\varphi_{\vec{F}}:=\\#\mbox{$\mathsf{Hom}(\vec{F}\\!\rightarrow\\!\star)$}$
for the digraphs $\vec{F}$ in the support $\mathsf{supp}(\iota)$ of $\iota$,
that is, $k=|\mathsf{supp}(\iota)|$. Concretely, assume that
$\vec{F}_{1},\dots,\vec{F}_{k}$ are elements of the support of $\iota$ (the
$\vec{F}_{i}$ are pairwise non-isomorphic) and observe that we can use our
oracle to compute the following function

$\vec{H}\mapsto\sum_{i=1}^{k}\iota(\vec{F}_{i})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}_{i}\\!\rightarrow\\!\vec{G}\otimes\vec{H})$}\,.$

Using the properties of the tensor product, this rewrites to

$\vec{H}\mapsto\sum_{i=1}^{k}(\iota(\vec{F}_{i})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}_{i}\\!\rightarrow\\!\vec{G})$})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}_{i}\\!\rightarrow\\!\vec{H})$}\,.$

Now we set
$a_{i}:=\iota(\vec{F}_{i})\cdot\\#\mbox{$\mathsf{Hom}(\vec{F}_{i}\\!\rightarrow\\!\vec{G})$}$
and
$\varphi_{i}:=\\#\mbox{$\mathsf{Hom}(\vec{F}_{i}\\!\rightarrow\\!\star)$}$.
Note that Lemma 37 makes sure that the $\varphi_{i}$ are indeed pairwise
distinct semigroup homomorphisms. Next, clearly, all functions in 1. to 4. in
Theorem 36 are computable in our setting. Hence we can use Algorithm
$\hat{\mathbb{A}}$ from Theorem 36 to obtain $a_{1},\dots,a_{k}$. The number
of steps required by $\hat{\mathbb{A}}$ is bounded by
$O(B\cdot\sum_{i=1}^{k}\log a_{i})$, where $B$ does not depend on the $a_{i}$.
Thus we can bound $B$ by a function in $|\iota|$. Furthermore, we can
generously bound $\log
a_{i}\leq\log(\iota(\vec{F}_{i})\cdot|\vec{G}^{\prime}|^{|\iota|})\leq
f^{\prime}(|\iota|)\cdot\log|\vec{G}^{\prime}|$ for some computable function
$f^{\prime}$.

Next, when simulating an oracle query $\vec{H}$ posed by $\hat{\mathbb{A}}$,
we have to use our own oracle to query $\vec{G}^{\prime}\otimes\vec{H}$.
Fortunately, Theorem 36 guarantees that $\vec{H}$ only depends on the
$\varphi_{i}$, that is, on the $\vec{F}_{i}$, and thus only on $\iota$. Thus,
constructing $\vec{G}^{\prime}\otimes\vec{H}$ can be done in time
$|\vec{G}^{\prime}|^{O(1)}\cdot f^{\prime\prime}(|\iota|)$ for some computable
function $f^{\prime\prime}$. Additionally, the outdegree of
$\vec{G}^{\prime}\otimes\vec{H}$ is, by definition of the tensor product,
bounded by the outdegree of $\vec{G}^{\prime}$, i.e., $d$, times the outdegree
of $\vec{H}$, which only depends on $\iota$. Finally, having obtained the
$a_{i}$, we obtain the terms
$\\#\mbox{$\mathsf{Hom}(\vec{F}_{i}\\!\rightarrow\\!\vec{G}^{\prime})$}$ by
dividing by $\iota(\vec{F_{i}})$, which is well-defined, since all
$\iota(\vec{F}_{i})$ are non-zero.

Hence, there is a computable function $f$ such that the following two desired
properties are true:

  * •

The total running time of our algorithm is bounded by
$f(|\iota|)\cdot|\vec{G}^{\prime}|^{O(1)}$, and

  * •

the outdegree of every oracle query is bounded by $d\cdot f(|\iota|)$.

Noting that the same arguments apply in the restricted cases of digraphs
without loops and DAGs, we can conclude the proof. ∎

##  6 Counting Homomorphisms

Recall the problem $\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ from Section
4.4.1. Section 6.1 shows that, when the reachability hypergraphs of the graphs
in $\vec{C}$ have bounded fractional hypertreewidth,
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ is fixed-parameter tractable.
Section 6.2 instead gives parameterized reductions under what we call
_monotone reversible minors_ , a new and restricted version of digraph minors.
In the next sections we will leverage these results for
$\\#\textsc{DirSub}_{\mathrm{d}}(\vec{C})$ and
$\\#\textsc{DirIndSub}_{\mathrm{d}}(\vec{C})$.

###  6.1 Upper Bounds

Let $\vec{C}$ be a class of of digraphs, and let
$\mathcal{R}(\vec{C})=\\{\mathcal{R}(\vec{H}):\vec{H}\in\vec{C}\\}$. This
section proves that, if $\mathcal{R}(\vec{C})$ has bounded fractional
hypertreewidth, $\mathsf{fhtw}(\mathcal{R}(\vec{C}))<\infty$, then
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ is fixed-parameter tractable. To
this end we give a parameterized reduction from
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ to
$\\#\textsc{CSP}(\mathcal{R}(\vec{C}))$ that preserves reachability
hypergraphs, and then invoke Theorem 28.

######  Definition 38.

Let $\vec{H}$ be a digraph, let $S_{1},\ldots,S_{\ell}$ be the sources of
$\vec{H}\mathbin{{/}{\sim}}$, and fix any $s_{i}\in S_{i}$ for each
$i\in[\ell]$. Fix any ordering $\prec$ of the vertices of $\vec{H}$, and, for
each $i\in[\ell]$, let $t_{i}$ be the tuple formed by sorting $R(s_{i})$
according to $\prec$. Furthermore, let $\vec{G}$ be a digraph. The relational
structures $\mathcal{A}[\vec{H}]$ and $\mathcal{B}[\vec{H},\vec{G}]$ are
defined as follows:

  * •

$\mathcal{A}[\vec{H}]=(V(\vec{H}),R_{1}^{\mathcal{A}},\ldots,R_{\ell}^{\mathcal{A}})$,
where $R_{i}^{\mathcal{A}}=\\{t_{i}\\}$ for all $i\in[\ell]$.

  * •

$\mathcal{B}[\vec{H},\vec{G}]=(V(\vec{G}),R_{1}^{\mathcal{B}},\ldots,R_{\ell}^{\mathcal{B}})$,
where

$R_{i}^{\mathcal{B}}=\\{\phi(t_{i}):\phi\in\mbox{$\mathsf{Hom}(\vec{H}[R(s_{i})]\\!\rightarrow\\!\vec{G})$}\\}$

for all $i\in[\ell]$.

######  Lemma 39.

$\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}=\mbox{$\mathsf{Hom}(\mathcal{A}[\vec{H}]\\!\rightarrow\\!\mathcal{B}[\vec{H},\vec{G}])$}$.

###### Proof.

To avoid notational clutter, we set $e_{i}:=R(s_{i})$. Let
$\varphi\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ and fix any
$i\in[\ell]$. Clearly, the restriction of $\varphi$ to $\vec{H}[e_{i}]$ is in
$\mathsf{Hom}(\vec{H}[e_{i}]\\!\rightarrow\\!\vec{G})$. Therefore by
Definition 38 we have $\varphi(t_{i})\in R_{i}^{\mathcal{B}}$. Hence $\varphi$
is a homomorphism from $\mathcal{A}[\vec{H}]$ to
$\mathcal{B}[\vec{H},\vec{G}]$, that is,
$\varphi\in\mbox{$\mathsf{Hom}(\mathcal{A}[\vec{H}]\\!\rightarrow\\!\mathcal{B}[\vec{H},\vec{G}])$}$.

Now let
$\varphi\in\mbox{$\mathsf{Hom}(\mathcal{A}[\vec{H}]\\!\rightarrow\\!\mathcal{B}[\vec{H},\vec{G}])$}$
and fix any $i\in[\ell]$. By definition, $\varphi(t_{i})\in
R_{i}^{\mathcal{B}}$. By Definition 38 this implies
$\varphi(t_{i})=\phi(t_{i})$ for some
$\phi\in\mbox{$\mathsf{Hom}(\vec{H}[e_{i}]\\!\rightarrow\\!\vec{G})$}$, thus
$(\varphi(u),\varphi(v))\in E(\vec{G})$ for all $(u,v)\in E(\vec{H}[e_{i}])$.
Since this holds for all $i\in[\ell]$ and since
$E(\vec{H})=\cup_{i\in[\ell]}E(\vec{H}[e_{i}])$, we have
$(\varphi(u),\varphi(v))\in E(\vec{G})$ for all $(u,v)\in E(\vec{H})$. Thus
$\varphi\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$. ∎

Further, we note the following immediate consequence of the definition of
$\mathcal{A}[\vec{H}]$.

######  Observation 40.

$\mathcal{H}[\mathcal{A}[\vec{H}]]=\mathcal{R}(\vec{H})$.

Next we show that $\mathcal{A}[\vec{H}]$ and $\mathcal{B}[\vec{H},\vec{G}]$
can be constructed efficiently.

######  Lemma 41.

There exists a computable function $f$ such that, given any two DAGs $\vec{H}$
and $\vec{G}$, the relational structures $\mathcal{A}[\vec{H}]$ and
$\mathcal{B}[\vec{H},\vec{G}]$ can be computed in time $f(k,d)\cdot n^{O(1)}$
where $k=|V(\vec{H})|$, $n=|V(\vec{G})|$, and $d$ is the maximum outdegree of
$\vec{G}$. Moreover, $|\mathcal{B}[\vec{H},\vec{G}]|\leq f(k,d)\cdot
O(|\vec{G}|)$.

###### Proof.

It is straightforward that $\mathcal{A}[\vec{H}]$ can be constructed in time
only depending on $k$. For what follows, we again set $e_{i}:=R(s_{i})$.
Furthermore, set $a_{i}:=|e_{i}|$. To construct
$\mathcal{B}[\vec{H},\vec{G}]$, and more precisely every relation
$\mathcal{R}_{i}^{\mathcal{B}}$, we use the following standard technique. For
every $v\in V(\vec{G})$ let $N_{k-1}(v)$ be the set of vertices reachable from
$v$ by a directed path of length at most $k-1$. Note that for any
$\phi\in\mbox{$\mathsf{Hom}(\vec{H}[e_{i}]\\!\rightarrow\\!\vec{G})$}$ we have
that $\vec{H}[e_{i}]$ is connected and contains at most $k$ vertices.
Furthermore, each vertex in $\vec{H}[e_{i}]$ is reachable by a directed path
from $s_{i}$. Thus $\phi(t_{i})$ contains only vertices of $N_{k-1}(v)$ where
$v=\phi(s_{i})$.

Therefore to list all $\phi(t_{i})$ with
$\phi\in\mbox{$\mathsf{Hom}(\vec{H}[e_{i}]\\!\rightarrow\\!\vec{G})$}$ we take
every $v\in V(\vec{G})$ in turn, we compute $N_{k-1}(v)$, and for every
$a_{i}$-tuple $z_{i}\in(N_{k-1}(v))^{a_{i}-1}$ whose first element is $v$, we
add $z_{i}$ if and only if the map $\phi$ defined by $\phi(t_{i})=z_{i}$
preserves all edges of $\vec{H}[e_{i}]$, which holds if and only if
$\phi\in\mbox{$\mathsf{Hom}(\vec{H}[e_{i}]\\!\rightarrow\\!\vec{G})$}$.
Finally, recalling that $d$ is the outdegree of $\vec{G}$, we have
$|N_{k-1}(v)|\leq\sum_{j=0}^{k-1}d^{j}$, which only depends on $k$ and $d$. It
is thus immediate to see that we can compute all
$\mathcal{R}_{i}^{\mathcal{B}}$ in time $f(k,d)\cdot n^{O(1)}$, and that the
overall size of $\mathcal{B}[\vec{H},\vec{G}]$ is bounded by $f(k,d)\cdot
O(|\vec{G}|)$, for some computable function $f$. ∎

######  Theorem 42.

For some computable function $f$ there is an algorithm that, given any pair of
digraphs $(\vec{H},\vec{G})$, computes
$\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}$ in time
$f(|\vec{H}|,d)\cdot|\vec{G}|^{r+O(1)}$, where $d$ is the maximum outdegree of
$\vec{G}$ and $r=\mathsf{fhtw}(\mathcal{R}(\vec{H}))$. Therefore
$\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})\in\mathsf{FPT}$ if
$\mathsf{fhtw}(\mathcal{R}(\vec{C}))<\infty$.

###### Proof.

Given an instance $(\vec{H},\vec{G})$, let $n=|V(\vec{G})|$ and
$k=|V(\vec{H})|$. We compute $\mathcal{A}[\vec{H}]$ and
$\mathcal{B}[\vec{H},\vec{G}]$ as in Lemma 41. In particular, we obtain
$|\mathcal{B}[\vec{H},\vec{G}]|\leq g(k,d)\cdot O(|\vec{G}|)$ for some
computable function $g$. Finally, by Lemma 39, we have
$\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!\vec{G})$}=\mbox{$\mathsf{Hom}(\mathcal{A}[\vec{H}]\\!\rightarrow\\!\mathcal{B}[\vec{H},\vec{G}])$}$,
the latter of which can be computed, by Theorem 28, in time

$f^{\prime}(|\mathcal{A}[\vec{H}]|)\cdot|\mathcal{B}[\vec{H},\vec{G}]|^{r+O(1)}\leq
f^{\prime}(|\mathcal{A}[\vec{H}]|)\cdot
g(k,d)^{r+O(1)}\cdot|\vec{G}|^{r+O(1)}$

for some computable function $f^{\prime}$. Since $|\mathcal{A}[\vec{H}]|$
depends only on $k$ and not on $n$, the proof is concluded. ∎

###  6.2 Coloured Homomorphisms and Reductions via MR Minors

We start by introducing _monotone reversible (MR) minors_ of a digraph
$\vec{H}$.

######  Definition 43 (Monotone Reversible Minors).

Let $\vec{H}$ be a digraph and consider the following operations:

  * _Sink deletion:_ delete all vertices in $T$ for some sink $T$ of $\vec{H}\mathbin{{/}{\sim}}$. The resulting graph is denoted by $\vec{H}\setminus T$.

  * _Contraction:_ identify $u$ and $v$ for some $uv\in E(\vec{H})$. We emphasise that a contraction does not yield a loop. The resulting graph is denoted by $\vec{H}/(u,v)$.

  * _Loop deletion:_ delete a loop $(u,u)$. The resulting graph is denoted by $\vec{H}\setminus(u,u)$.

A _monotone reversible minor_ (“MR minor”) of $\vec{H}$ is a digraph that can
be obtained from $\vec{H}$ by a sequence of sink deletions, contractions and
loop deletions.

######  Observation 44.

Let $\vec{H}$ be a digraph.

  1. (M1)

If $\vec{H}$ does not have loops, then no MR minor of $\vec{H}$ does.

  2. (M2)

$\vec{H}\mathbin{{/}{\sim}}$ is an MR minor of $\vec{H}$.

We show that the parameterized complexity of $\\#\textsc{DirHom}_{\mathrm{d}}$
is monotone (i.e., nonincreasing) under taking MR minors. The following three
lemmas establish the fact separately for sink deletions, for contractions, and
for loop deletion. For technical reasons, we will prove this property for the
colour-prescribed variant; we will be able to remove the colours in our
hardness reductions later.

######  Lemma 45.

There exists an algorithm $\mathbb{A}_{1}$ that satisfies the following
constraints:

  1. 1.

$\mathbb{A}_{1}$ expects as input a digraph $\vec{H}$, a sink $T$ of
$\vec{H}\mathbin{{/}{\sim}}$, and a surjectively $\vec{H}\setminus T$-coloured
digraph $(\vec{G}^{\prime},c^{\prime})$ of outdegree $d^{\prime}$.

  2. 2.

The running time of $\mathbb{A}_{1}$ is bounded by
$\mathsf{poly}(|\vec{H}|,|\vec{G}^{\prime}|)$.

  3. 3.

$\mathbb{A}_{1}$ outputs a surjectively $\vec{H}$-coloured digraph
$(\vec{G},c)$ of size at most $O(|H|\cdot|\vec{G}^{\prime}|)$ such that the
outdegree of $\vec{G}$ is bounded by $d^{\prime}+|\vec{H}|$, and

$\\#\mbox{$\mathsf{Hom}(\vec{H}\setminus
T\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$}=\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$}\,.$

###### Proof.

Let $T=\\{t_{1},\dots,t_{k}\\}$. For every $i\in[k]$ let $V_{i}$ be the set of
vertices $v\in V(\vec{H})\setminus T$ such that $(v,t_{i})\in E(\vec{H})$.
Note that, since $T$ is a sink in $\vec{H}\mathbin{{/}{\sim}}$, there are no
arcs from $T$ to $V(\vec{H})\setminus T$ in $\vec{H}$.

We construct $(\vec{G},c)$ from $(\vec{G}^{\prime},c^{\prime})$ as follows:
First, we add to $\vec{G}^{\prime}$ the set $T$ and all arcs in $T^{2}\cap
E(\vec{H})$. Second, for every $i\in[k]$, we add to $\vec{G}$ all arcs from
$c^{\prime-1}(V_{i})$ to $t_{i}$ — note that $c^{\prime-1}(V_{i})$ is the set
of vertices of $\vec{G}^{\prime}$ that are coloured by $c^{\prime}$ with a
vertex in $V_{i}$. Finally, we let $c$ agree with $c^{\prime}$ on all vertices
of $\vec{G}^{\prime}$, and we set $c(t_{i})=t_{i}$ for all $i\in[k]$. Clearly,
this construction can be done in time
$\mathsf{poly}(|\vec{H}|,|\vec{G}^{\prime}|)$, and the resulting $(\vec{G},c)$
is of size at most $O(|H|\cdot|\vec{G}^{\prime}|)$. Furthermore, the outdegree
of $\vec{G}$ is bounded by $d^{\prime}+|\vec{H}|$. By construction, and the
fact that $c^{\prime}$ is a vertex-surjective homomorphism from
$\vec{G}^{\prime}$ to $\vec{H}\setminus T$, it is also immediate that $c$ is a
vertex-surjective homomorphism from $\vec{G}$ to $\vec{H}$. Finally, consider
the function $b$ that maps a colour-prescribed homomorphism
$\varphi\in\mbox{$\mathsf{Hom}(\vec{H}\setminus
T\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$}$ to the function $\psi$
that agrees with $\varphi$ on $V(\vec{H}\setminus T)$ and that maps $t_{i}$ to
$t_{i}$ for each $i\in[k]$. By construction, it is easy to see that $b$ must
be a bijection from $\mathsf{Hom}(\vec{H}\setminus
T\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$ to
$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$. This concludes the proof.
∎

######  Lemma 46.

There exists an algorithm $\mathbb{A}_{2}$ that satisfies the following
constraints:

  1. 1.

$\mathbb{A}_{2}$ expects as input a digraph $\vec{H}$, an arc $(u,v)$ of
$\vec{H}$, and a surjectively $\vec{H}/(u,v)$-coloured digraph
$(\vec{G}^{\prime},c^{\prime})$ of outdegree $d^{\prime}$.

  2. 2.

The running time of $\mathbb{A}_{2}$ is bounded by
$\mathsf{poly}(|\vec{H}|,|\vec{G}^{\prime}|)$.

  3. 3.

$\mathbb{A}_{2}$ outputs a surjectively $\vec{H}$-coloured digraph
$(\vec{G},c)$ of size at most $O(|H|\cdot|\vec{G}^{\prime}|)$ such that the
outdegree of $\vec{G}$ is bounded by $2d^{\prime}+1$, and

$\\#\mbox{$\mathsf{Hom}(\vec{H}/(u,v)\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$}=\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$}\,.$

###### Proof.

We write $uv$ for the vertex in $\vec{H}/(u,v)$ that corresponds to the
contraction of $u$ and $v$. Recall that $\vec{G}^{\prime}$ is surjectively
$\vec{H}/(u,v)$-coloured by $c^{\prime}$, and set $V_{uv}:=c^{\prime-1}(uv)$.
Let us now provide the construction of $(\vec{G},c)$:

  1. (a)

We start with $\vec{G}^{\prime}$ and delete the set $V_{uv}$ (including all
incident arcs).

  2. (b)

We add two copies of $V_{uv}$; one is denoted by $V_{u}$, and the other one is
denoted by $V_{v}$. For each vertex $w\in V_{uv}$, we denote the copy of $w$
in $V_{u}$ by $w_{u}$, and the copy of $w$ in $V_{v}$ by $w_{v}$.

  3. (c)

For each $w\in V_{uv}$, we add an arc $(w_{u},w_{v})$.

  4. (d)

For each $x\in V(\vec{H})\setminus\\{u,v\\}$ we proceed as follows

     * •

If $(x,u)\in E(\vec{H})$, then, for every $y\in c^{\prime-1}(x)$ and $w\in
V_{uv}$, we add an arc from $y$ to $w_{u}\in V_{u}$ if and only if $(y,w)\in
E(\vec{G}^{\prime})$.

     * •

If $(u,x)\in E(\vec{H})$, then, for every $y\in c^{\prime-1}(x)$ and $w\in
V_{uv}$, we add an arc from $w_{u}\in V_{u}$ to $y$ if and only if $(w,y)\in
E(\vec{G}^{\prime})$.

     * •

If $(x,v)\in E(\vec{H})$, then, for every $y\in c^{\prime-1}(x)$ and $w\in
V_{uv}$,we add an arc from $y$ to $w_{v}\in V_{v}$ if and only if $(y,w)\in
E(\vec{G}^{\prime})$.

     * •

If $(v,x)\in E(\vec{H})$, then, for every $y\in c^{\prime-1}(x)$ and $w\in
V_{uv}$, we add an arc from $w_{v}\in V_{v}$ to $y$ if and only if $(w,y)\in
E(\vec{G}^{\prime})$.

  5. (e)

Finally, $c$ agrees with $c^{\prime}$ on $V(\vec{H})\setminus\\{u,v\\}$, and
$c$ maps every vertex in $V_{u}$ to $u$ and it maps every vertex in $V_{v}$ to
$v$.

It is immediate that $c$ is a surjective $\vec{H}$-colouring of $\vec{G}$.
Furthermore, it is clear that the running time is bounded by
$\mathsf{poly}(|\vec{H}|,|\vec{G}^{\prime}|)$, and that the size of
$(\vec{G},c)$ is at most $O(|H|\cdot|\vec{G}^{\prime}|)$. Let us consider the
outdegree: For $x\in
V(\vec{H})\setminus\\{u,v\\}=V(\vec{H}/(u,v))\setminus\\{uv\\}$, the outdegree
of every vertex $v\in c^{-1}(x)=c^{\prime-1}(x)$ in $\vec{G}$ is bounded by
twice the outdegree of $v$ in $\vec{G}^{\prime}$ (see (d) above). Furthermore,
the outdegree of every vertex $w_{u}\in c^{-1}(u)$ in $\vec{G}$ is bounded by
the outdegree of $w$ in $\vec{G}^{\prime}$ plus $1$ (see (d) above and note
that the arcs added in (c) above can increase it by $1$). Finally, the
outdegree of every vertex $w_{v}\in c^{-1}(v)$ in $\vec{G}$ is bounded by the
outdegree of $w$ in $\vec{G}^{\prime}$ (see (d) above). Consequently, we can
bound the outdegree of $\vec{G}$ by $2d^{\prime}+1$.

Finally, note that (c) above makes sure that any homomorphism $\psi$ in
$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$ must map $u$ and $v$ to
the same copy of a vertex $w\in V_{uv}$. Furthermore, (d) makes sure that the
mapping $\varphi$ that agrees with $\psi$ on $V(\vec{H})\setminus\\{u,v\\}$
and that maps $uv$ to $w$ (where $w_{u}$ and $w_{v}$ are the images of $u$ and
$v$ under $\psi$), is a homomorphism in
$\mathsf{Hom}(\vec{H}/(u,v)\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$.
On the other hand every homomorphism
$\varphi\in\mbox{$\mathsf{Hom}(\vec{H}/(u,v)\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$}$
corresponds to the homomorphism
$\psi\in\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$}$ that
agrees with $\varphi$ on $V(\vec{H})\setminus\\{u,v\\}$, and that maps $u$ and
$v$ to $w_{u}$ and $w_{v}$, where $w=\varphi(uv)$. Concretely, we obtain the
desired bijection between
$\mathsf{Hom}(\vec{H}/(u,v)\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$
and $\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$, concluding the proof.
∎

######  Lemma 47.

There exists an algorithm $\mathbb{A}_{3}$ that satisfies the following
constraints:

  1. 1.

$\mathbb{A}_{3}$ expects as input a digraph $\vec{H}$, a loop $(u,u)$ of
$\vec{H}$, and a surjectively $\vec{H}\setminus(u,u)$-coloured digraph
$(\vec{G}^{\prime},c^{\prime})$ of outdegree $d^{\prime}$.

  2. 2.

The running time of $\mathbb{A}_{3}$ is bounded by
$\mathsf{poly}(|\vec{H}|,|\vec{G}^{\prime}|)$.

  3. 3.

$\mathbb{A}_{3}$ outputs a surjectively $\vec{H}$-coloured digraph
$(\vec{G},c)$ of size at most $O(|\vec{G}^{\prime}|)$ such that the outdegree
of $\vec{G}$ is bounded by $d^{\prime}+1$, and

$\\#\mbox{$\mathsf{Hom}(\vec{H}\setminus(u,u)\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$}=\\#\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$}\,.$

###### Proof.

This is a very easy case: Obtain $\vec{G}$ from $\vec{G}^{\prime}$ by adding a
loop to each vertex of $\vec{G}^{\prime}$ coloured by $c^{\prime}$ with $u$.
Furthermore, we set $c:=c^{\prime}$. Clearly, $c$ is a surjective
$\vec{H}$-colouring of $\vec{G}$, and the outdegree of $\vec{G}$ can increase
by at most $1$. Furthermore, the construction immediately yields that
$\mbox{$\mathsf{Hom}(\vec{H}\setminus(u,u)\\!\rightarrow\\!(\vec{G}^{\prime},c^{\prime}))$}=\mbox{$\mathsf{Hom}(\vec{H}\\!\rightarrow\\!(\vec{G},c))$}$,
that is, a mapping
$\varphi:V(\vec{H})(=V(\vec{H}^{\prime}))\\!\rightarrow\\!V(\vec{G})(=V(\vec{G}^{\prime}))$
is a homomorphism from $\vec{H}\setminus(u,u)$ to
$(\vec{G}^{\prime},c^{\prime})$ if and only if it is a homomorphism from
$\vec{H}$ to $(\vec{G},c)$ ∎

In combination, the three lemmas above yield the following:

######  Lemma 48.

Let $\vec{C}$ be a recursively enumerable class of digraphs and let
$\vec{C}^{\prime}$ be a class of MR minors of graphs in $\vec{C}$. Then

$\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C}^{\prime})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C})\,.$

###### Proof.

Let $\vec{H}^{\prime}$ and $(\vec{G}^{\prime},c^{\prime})$ be an input
instance of $\\#\textsc{cp-DirHom}_{\mathrm{d}}(\vec{C}^{\prime})$. We start
by searching a graph $\vec{H}\in\vec{C}$ such that $\vec{H}^{\prime}$ is an MR
minor of $\vec{H}$. Note that this can be done in time only depending on
$\vec{H}^{\prime}$. Since $\vec{H}^{\prime}$ can be obtained from $\vec{H}$ by
a sequence of $\ell$ sink-deletions, contractions, and loop deletions, we can
use algorithms $\mathbb{A}_{1}$, $\mathbb{A}_{2}$ and $\mathbb{A}_{3}$ from
the previous three lemmas for a total of $\ell$ times. Note that the crucial
property of the $\mathbb{A}_{i}$ is that the oracle queries always have size
bounded by $f(|\vec{H}|)\cdot O(|\vec{G}^{\prime}|)$. Hence, even after $\ell$
applications of the constructions, the total size will still be bounded by
$f(|\vec{H}|)\cdot O(|\vec{G}^{\prime}|)$. Since furthermore each individual
application takes only polynomial time, we obtain, as desired a parameterised
Turing-reduction. ∎

The final part of this subsection is the following lemma for removing the
colours. Note that its proof is a simple application of the inclusion-
exclusion principle and transfers verbatim from e.g. [45, Lemma 2.49] (see
also [22, Lemma 1.34]). We emphasise that the reduction only requires oracle
queries for subgraphs of the input host-graph which cannot increase the
outdegree; thus the reduction applies to our setting.

######  Lemma 49.

Let $\vec{C}$ be a class of digraphs. We have

$\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})\,.$

###  6.3 Lower Bounds

We start by extending the notion of adaptive width from hypergraphs to
digraphs.

######  Definition 50 (Adaptive width of digraphs).

The _adaptive width_ of a digraph $\vec{H}$, denoted by
$\operatorname{aw}(\vec{H})$, is defined as the adaptive width of its contour.
That is $\operatorname{aw}(\vec{H}):=\operatorname{aw}(\Gamma(\vec{H}))$.

We proceed by proving intractability of $\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C})$ for classes $\vec{C}$ of canonical DAGs of
unbounded adaptive width.

######  Lemma 51.

Let $\vec{C}$ be a recursively enumerable class of canonical DAGs. If the
adaptive width of $\vec{C}$ is unbounded then $\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C})$ is not fixed-parameter tractable, unless ETH
fails.

The proof of Lemma 51 uses a careful reduction from a version of the
parameterised constraint satisfaction problem and is encapsulated in the
following subsection.

####  6.3.1 Reduction from a Constraint Satisfaction problem

The starting point of our reduction is the following _decision_ problem and
the corresponding hardness result proven by Chen et al. [14] (building upon
Marx [40]); below, $\mathcal{S}$ denotes a class of relational structures.

Let us emphasise the subtle difference between the input restrictions of
$\textsc{Hom}(\mathcal{S})$ and $\\#\textsc{CSP}(\mathcal{C})$: In the former,
we enforce that $\mathcal{A}$ is contained in $\mathcal{S}$. In the latter, we
only restrict the hypergraphs of the relational structure $\mathcal{A}$ by
requiring that the hypergraph $\mathcal{H}(\mathcal{A})$ is contained in
$\mathcal{C}$.

For what follows, we call a relational structure $\mathcal{A}$ _minimal under
homomorphic equivalence_ if there is no homomorphism from $\mathcal{A}$ to a
proper substructure of $\mathcal{A}$.

######  Theorem 52 ([14]).

Let $\mathcal{S}$ be a recursively enumerable class of relational structures
that are minimal under homomorphic equivalence, and assume that ETH holds. If
$\mathcal{S}$ has unbounded adaptive width then $\textsc{Hom}(\mathcal{S})$ is
not fixed-parameter tractable.

To obtain hardness of $\\#\textsc{DirHom}_{\mathrm{d}}(\vec{C})$ from Theorem
52, we show a chain of parameterized Turing reductions using two intermediate
problems; one of them is $\\#\textsc{cp-DirHom}_{\mathrm{d}}(\vec{C})$, and
for the second one we extend the notion of colour-prescribed homomorphisms to
hypergraphs: Let $\mathcal{H}$ be a hypergraph. An $\mathcal{H}$_-colouring_
of a hypergraph $\mathcal{G}$ is a homomorphism
$c\in\mbox{$\mathsf{Hom}(\mathcal{G}\\!\rightarrow\\!\mathcal{H})$}$. An
$\mathcal{H}$_-coloured hypergraph_ is a pair $(\mathcal{G},c)$ where
$\mathcal{G}$ is a hypergraph and $c$ is an $\mathcal{H}$-colouring of
$\mathcal{G}$. Given a $\mathcal{H}$-coloured hypergraph $(\mathcal{G},c)$, a
map $\psi:V(\mathcal{H})\\!\rightarrow\\!V(\mathcal{G})$ is $c$-_colour-
prescribed_ if $c(\psi(v))=v$ for every $v\in V(\mathcal{H})$. The set of all
$c$-colour-prescribed homomorphisms from $\mathcal{H}$ to $\mathcal{G}$ is
denoted by $\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!(\mathcal{G},c))$.

We can now introduce the problem $\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})$; here $\mathcal{C}$ is a class of hypergraphs:

In the rest of this subsection we prove:

$\displaystyle\textsc{Hom}(\mathcal{S})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C})$ (10)

where $\mathcal{S}$ and $\mathcal{C}$ are carefully constructed from $\vec{C}$
so to preserve the (un)boundedness of adaptive width. The next two paragraphs
prove the reductions of (10) in order.

##### $\textsc{Hom}(\mathcal{S})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})$

We reduce $\textsc{Hom}(\mathcal{S})$ to $\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})$ for a certain class
$\mathcal{S}=\mathcal{S}(\mathcal{C})$ described below. To this end we convert
every hypergraph into a structure; this structure is the same of Definition 38
– only for hypergraphs. Without loss of generality, in what follows we assume
$V(\mathcal{H})=\\{1,\ldots,k\\}$ where $k=|V(\mathcal{H})|$.

######  Definition 53.

Let $\mathcal{H}$ be any hypergraph. The structure $\mathcal{A}[\mathcal{H}]$
has universe $V(\mathcal{H})$ and, for every $e\in E(\mathcal{H})$, contains a
relation $R^{\mathcal{A}}_{e}$ whose only tuple is the set $e$ sorted in
nondecreasing order.

Since we use individual relation symbols for each $e\in E(\mathcal{H})$, the
following is straightforward to prove:

######  Claim 54.

Let $\mathcal{H}$ be any hypergraph. Then $\mathcal{A}[\mathcal{H}]$ is
minimal under homomorphic equivalence, and the hypergraph of
$\mathcal{A}[\mathcal{H}]$ is $\mathcal{H}$.

For any class $\mathcal{C}$ of hypergraphs let
$\mathcal{S}[\mathcal{C}]=\\{A[\mathcal{H}]~{}|~{}\mathcal{H}\in\mathcal{C}\\}$.
We prove:

######  Lemma 55.

For every recursively enumerable class $\mathcal{C}$ of hypergraphs without
isolated vertices,
$\textsc{Hom}(\mathcal{S}[\mathcal{C}])\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})$.

###### Proof.

Let $(\mathcal{A},\mathcal{B})$ be an instance of
$\textsc{Hom}(\mathcal{S}[\mathcal{C}])$, and let $U(\mathcal{A})$ and
$U(\mathcal{B})$, respectively, be the universes of $\mathcal{A}$ and
$\mathcal{B}$. If $\mathcal{A}$ and $\mathcal{B}$ have different signatures
then clearly the solution is NO. Otherwise, since
$\mathcal{A}\in\mathcal{S}[\mathcal{C}]$ and $\mathcal{C}$ is recursively
enumerable, in time $f(|\mathcal{A}|)$ for some computable $f$ we find
$\mathcal{H}\in\mathcal{C}$ such that $\mathcal{A}=\mathcal{A}[\mathcal{H}]$.
Then we construct the hypergraph $\mathcal{G}$ defined by:

  * •

$V(\mathcal{G})=U(\mathcal{B})\times V(\mathcal{H})$

  * •

$E(\mathcal{G})=\\{(x_{1},i_{1}),\dots,(x_{\ell},i_{\ell})\\}:e=\\{i_{1},\dots,i_{\ell}\\}\in
E(\mathcal{H}),i_{1}<\ldots<i_{\ell},(x_{1},\dots,x_{\ell})\in
R^{\mathcal{B}}_{e}$

Let $c:V(\mathcal{G})\\!\rightarrow\\!V(\mathcal{H})$ be defined by
$c((x,i))=i$ for all $(x,i)\in V(\mathcal{G})$. Note that $c$ is an
$\mathcal{H}$-colouring of $\mathcal{G}$. Consider the instance
$(\mathcal{H},\mathcal{(}G,c))$ of $\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})$. We claim:

$\displaystyle\mbox{$\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$}\neq\emptyset\;\Leftrightarrow\;\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!(\mathcal{G},c))$}\neq\emptyset$
(11)

To prove that
$\mbox{$\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$}\neq\emptyset\,\Rightarrow\,\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!(\mathcal{G},c))$}\neq\emptyset$,
suppose
$\varphi\in\mbox{$\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$}$.
Define $\psi:V(\mathcal{H})\\!\rightarrow\\!V(\mathcal{G})$ by
$\psi(i)=(\varphi(i),i)$ for all $i\in V(\mathcal{H})$. We claim that
$\psi\in\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!(\mathcal{G},c))$}$.
Let $e=\\{i_{1},\dots,i_{\ell}\\}\in E(\mathcal{H})$ with
$i_{1}<\dots<i_{\ell}$. By definition of $\mathcal{A}[\mathcal{H}]$ we have
$(i_{1},\dots,i_{\ell})\in R^{\mathcal{A}}_{e}$; and since $\varphi$ is a
homomorphism, $(\varphi(i_{1}),\dots,\varphi(i_{\ell}))\in
R^{\mathcal{B}}_{e}$. By definition of $\mathcal{G}$ this implies that
$\\{(\varphi(i_{1}),i_{1}),\dots,(\varphi(i_{\ell}),i_{\ell})\\}\in
E(\mathcal{G})$. Hence,
$\psi\in\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!\mathcal{G})$}$. To
see that $\psi$ is $c$-colour-prescribed, note that
$c(\psi(i))=c((\varphi(i),i))=i$ for all $i\in V(\mathcal{H})$.

To prove that
$\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!(\mathcal{G},c))$}\neq\emptyset\,\Rightarrow\,\mbox{$\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$}\neq\emptyset$,
suppose
$\psi\in\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!(\mathcal{G},c))$}$.
Since $\psi$ is $c$-colour-prescribed, for each $i\in V(\mathcal{H})$ we have
$\psi(i)=(x_{i},i)$ for some $x_{i}\in U(\mathcal{B})$. Define
$\varphi:U(\mathcal{A})\\!\rightarrow\\!U(\mathcal{B})$ by letting
$\varphi(i)=x_{i}$ for all $i\in U(\mathcal{A})$. We claim that
$\varphi\in\mbox{$\mathsf{Hom}(\mathcal{A}\\!\rightarrow\\!\mathcal{B})$}$.
Let indeed $(i_{1},\dots,i_{\ell})\in R^{\mathcal{A}}_{e}$. By definition of
$\mathcal{A}$ this implies $e=\\{i_{1},\dots,i_{\ell}\\}\in E(\mathcal{H})$
and $i_{1}<\dots<i_{\ell}$. Since $\psi$ is $c$-color-prescribed, then
$\psi(i_{j})=(x_{j},i_{j})$ for all $j=1,\ldots,\ell$; and since
$\psi\in\mbox{$\mathsf{Hom}(\mathcal{H}\\!\rightarrow\\!\mathcal{G})$}$, then
$\\{(x_{1},i_{1}),\dots,(x_{\ell},i_{\ell})\\}\in E(\mathcal{G})$. By
definition of $\mathcal{G}$ this implies $(x_{1},\dots,x_{\ell})\in
R^{\mathcal{B}}_{e}$, and since
$\varphi(i_{1},\dots,i_{\ell})=(x_{1},\dots,x_{\ell})$, then
$\varphi(i_{1},\dots,i_{\ell})\in R^{\mathcal{B}}_{e}$.

Finally, note that $|\mathcal{H}|=f(|\mathcal{A}|)$ and $a(\mathcal{G})\leq
a(\mathcal{H})\leq|\mathcal{H}|$. Therefore $|\mathcal{H}|+a(\mathcal{G})$ is
a function of $|\mathcal{A}|$, hence the reduction preserves the parameter. ∎

##### $\\#\textsc{cp-
Hom}_{\mathrm{a}}(\mathcal{C})\leq^{\mathrm{fpt}}_{\mathrm{T}}\\#\textsc{cp-
DirHom}_{\mathrm{d}}(\vec{C})$

Recall that the contour of a digraph $\vec{H}$, denoted by $\Gamma(\vec{H})$,
is obtained by deleting from the reachability hypergraph
$\mathcal{R}(\vec{H})$ the vertices corresponding to sources in
$\vec{H}\mathbin{{/}{\sim}}$ (see Definition 18). For our reduction we need to
prove that the adaptive width of a contour is at least that of the original
hypergraph.

######  Lemma 56.

Let $\vec{H}$ be a canonical DAG and let $\mathcal{R}$ be its reachability
hypergraph. Then
$\operatorname{aw}({\vec{H}})\geq\operatorname{aw}(\mathcal{R})$.

###### Proof.

Recall that, by definition,
$\operatorname{aw}({\vec{H}})=\operatorname{aw}(\Gamma(\vec{H}))$. Set
$\mathcal{F}:=\Gamma(\vec{H})$ and let $s_{1},\ldots,s_{\ell}$ be the sources
of $\vec{H}$ and $e_{1},\ldots,e_{\ell}$ the corresponding hyperedges in
$\mathcal{R}$. Let $\mathcal{F}_{0}=\mathcal{R}$, and for $i=1,\ldots,\ell$
let $\mathcal{F}_{i}$ be the hypergraph obtained from $\mathcal{F}_{i-1}$ by
first deleting $s_{i}$ and then removing a copy of $e_{i}$ if more than one
exist. Note that $\mathcal{F}_{\ell}=\mathcal{F}$. We prove that
$\operatorname{aw}(\mathcal{F}_{i})\geq\operatorname{aw}(\mathcal{F}_{i-1})$
for all $i=1,\ldots,\ell$, which implies
$\operatorname{aw}(\mathcal{F}_{\ell})\geq\operatorname{aw}(\mathcal{F}_{0})$,
that is, $\operatorname{aw}(\mathcal{F})\geq\operatorname{aw}(\mathcal{R})$.
Since removing a copy of a multi-edge leaves adaptive with unchanged, we can
assume $\mathcal{F}_{i}$ is obtained from $\mathcal{F}_{i-1}$ by just deleting
$s_{i}$.

We rephrase and prove the claim
$\operatorname{aw}(\mathcal{F}_{i})\geq\operatorname{aw}(\mathcal{F}_{i-1})$
as follows. Let $\mathcal{H}$ be a hypergraph, let $e\in E(\mathcal{H})$, and
let $\mathcal{H}^{\prime}$ be the hypergraph obtained from $\mathcal{H}$ by
adding a new vertex $v^{\prime}$ and replacing $e$ with
$e\cup\\{v^{\prime}\\}$. We claim
$\operatorname{aw}(\mathcal{H})\geq\operatorname{aw}(\mathcal{H}^{\prime})$.
To this end, we show that for every fractional independent set $\mu^{\prime}$
of $\mathcal{H}^{\prime}$ there exists a tree decomposition
$(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ of $\mathcal{H}^{\prime}$ such
that ${\mu^{\prime}}\mathchar
45\relax\mathsf{width}(\mathcal{T}^{\prime},\mathcal{B}^{\prime})\leq\operatorname{aw}(\mathcal{H})$.
Let then $\mu^{\prime}$ be a fractional independent set of
$\mathcal{H}^{\prime}$, and let $\mu$ be the restriction of $\mu^{\prime}$ to
$V(\mathcal{H})=V(\mathcal{H}^{\prime})\setminus\\{v^{\prime}\\}$. Note that
$\mu$ is a fractional independent set of $\mathcal{H}$; thus, by definition of
adaptive width, there is a tree decomposition $(\mathcal{T},\mathcal{B})$ of
$\mathcal{H}$ such that ${\mu}\mathchar
45\relax\mathsf{width}(\mathcal{T},\mathcal{B})\leq\operatorname{aw}(\mathcal{H})$.
By definition of tree decomposition, there exists $B_{e}\in\mathcal{B}$ such
that $e\subseteq B_{e}$. Let $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ be
obtained from $(\mathcal{T},\mathcal{B})$ by appending appending the bag
$B_{e^{\prime}}=e^{\prime}$ to $B_{e}$.

We claim that $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ is a tree
decomposition of $\mathcal{H^{\prime}}$ and that ${\mu^{\prime}}\mathchar
45\relax\mathsf{width}(\mathcal{T}^{\prime},\mathcal{B}^{\prime})\leq\operatorname{aw}(\mathcal{H})$.
To see that $(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ is a tree
decomposition of $\mathcal{H^{\prime}}$ note that:

  * •

every edge of $\mathcal{H}^{\prime}$ is a subset of some bag of
$\mathcal{B}^{\prime}$. Indeed, $e^{\prime}\subseteq B_{e^{\prime}}$, while
every other edge is in $E(\mathcal{H})$, and is thus a subset of some bag of
$\mathcal{B}$ since $(\mathcal{T},\mathcal{B})$ is a tree decomposition of
$\mathcal{H}$

  * •

for every $u\in V(\mathcal{H}^{\prime})$ the subgraph
$\mathcal{T}^{\prime}_{u}$ of $\mathcal{T}^{\prime}$ induced by the bags
containing $u$ is connected. Indeed, if $u=v^{\prime}$ then
$\mathcal{T}^{\prime}_{u}$ has only one vertex. Else,