# A Dichotomy Hierarchy Characterizing Linear Time Subgraph Counting in
Bounded Degeneracy Graphs

Daniel Paul-Pena
University of California, Santa Cruz
<EMAIL_ADDRESS>C. Seshadhri
University of California, Santa Cruz
<EMAIL_ADDRESS>All the authors are supported by NSF CCF-1740850, DMS-2023495,
and CCF-1839317.

###### Abstract

Subgraph and homomorphism counting are fundamental algorithmic problems. Given
a constant-sized pattern graph $H$ and a large input graph $G$, we wish to
count the number of $H$-homomorphisms/subgraphs in $G$. Given the massive
sizes of real-world graphs and the practical importance of counting problems,
we focus on when (near) linear time algorithms are possible. The seminal work
of Chiba-Nishizeki (SICOMP 1985) shows that for bounded degeneracy graphs $G$,
clique and $4$-cycle counting can be done linear time. Recent works (Bera et
al, SODA 2021, JACM 2022) show a dichotomy theorem characterizing the patterns
$H$ for which $H$-homomorphism counting is possible in linear time, for
bounded degeneracy inputs $G$. At the other end, Nešetřil and Ossona de Mendez
used their deep theory of “sparsity” to define bounded expansion graphs (which
contains all minor-closed families). They prove that, for _all_ $H$,
$H$-homomorphism counting can be done in linear time for bounded expansion
inputs. What lies between? For a specific $H$, can we characterize input
classes where $H$-homomorphism counting is possible in linear time?

We discover a hierarchy of dichotomy theorems that precisely answer the above
questions. We show the existence of an infinite sequence of graph classes
$\mathcal{G}_{0}\supseteq\mathcal{G}_{1}\supseteq\ldots\supseteq\mathcal{G}_{\infty}$
where $\mathcal{G}_{0}$ is the class of bounded degeneracy graphs, and
$\mathcal{G}_{\infty}$ is the class of bounded expansion graphs. Fix any
constant sized pattern graph $H$. Let $LICL(H)$ denote the length of the
longest induced cycle in $H$. We prove the following. If $LICL(H)<3(r+2)$,
then $H$-homomorphisms can be counted in linear time for inputs in
$\mathcal{G}_{r}$. If $LICL(H)\geq 3(r+2)$, then (assuming fine-grained
complexity conjectures) $H$-homomorphism counting on inputs from
$\mathcal{G}_{r}$ takes $\Omega(m^{1+\gamma})$ time. (Here, $m$ denotes the
number of input edges, and $\gamma$ is some explicit constant.) We prove
similar dichotomy theorems for subgraph counting.

##  1 Introduction

Counting the number of small patterns in a large input graph is a central
algorithmic technique and widely used in both theory and practice [Lov67,
CN85a, FG04, DJ04, Lov12, ANRD15, CDM17, PSV17, ST19, RW20]. We express this
problem as _homomorphism_ or _subgraph_ counting. The pattern is a simple,
typically constant sized graph $H=(V(H),E(H))$. The input simple graph is
denoted by $G=(V(G),E(G))$. An $H$-homomorphism is a map $f:V(H)\to V(G)$ that
preserves edges. So, $\forall(u,v)\in E(H)$, $(f(u),f(v))\in E(G)$. If $f$ is
an injection (so distinct vertices of $H$ are mapped to distinct vertices of
$G$), this map is a subgraph. We use $\mathrm{Hom}_{H}(G)$ (resp.
$\mathrm{Sub}_{H}(G)$) to denote the count of the distinct $H$-homomorphisms
(resp. $H$-subgraphs).

Homomorphism and subgraph counting have applications in logic, graph theory,
partition functions in statistical physics, database theory, and network
science [CM77, BW99, DG00, BCL+06, PSV17, DRW19, PS20]. The topic of computing
$\mathrm{Hom}_{H}(G)$ is itself a subfield of graph algorithms [IR78, AYZ97,
BW99, DG00, DST02, DJ04, BCL+06, CDM17, Bre19, RW20]. The simplest non-trivial
case is when $H$ is a triangle, which has itself led to numerous papers.

When $H$ is part of the input size, the problem is exactly counting subgraph
isomorphisms, which is $\mathbb{NP}$-hard. In many applications, the pattern
is small and fixed. Let $n=|V(G)|$ and $k=|V(H)|$. Even when $H$ is a
$k$-clique, the problem of computing $\mathrm{Hom}_{H}(G)$ is $\\#W[1]$-hard
when parameterized by $k$ [DJ04]. So we do not expect $n^{o(k)}$ algorithms in
general. Nonetheless, the $n^{k}$ barrier can be beaten for specific $H$. The
breakthrough result of Curticapean-Dell-Marx proved that if $H$ has treewidth
at most 2, then $\mathrm{Hom}_{H}(G)$ can be computed in $\text{poly}(k)\cdot
n^{\omega}$ time, where $\omega$ is the matrix multiplication constant
[CDM17]. Their result also showed that algorithms and lower bounds easily
translate between homomorphism counting to subgraph counting. In the following
discussion, we only refer to $\mathrm{Hom}_{H}(G)$. But all our questions and
answers, with suitable modification, apply to $\mathrm{Sub}_{H}(G)$ as well.

Homomorphism and subgraph counting have wide applications in network science,
and there is a large study of practical algorithms for this problem (refer to
tutorial [ST19]). In practice, (near) linear time is likely a better
mathematical abstraction for feasibility, than just polynomial time. We are
motivated by the following question.

_Under what conditions on $G$ and $H$ can $\mathrm{Hom}_{H}(G)$ be computed in
near-linear time?_

A starting point for this broad investigation is a seminal result of Chiba-
Nishizeki [CN85b] that focuses on _graph degeneracy_. An input graph $G$ has
bounded degeneracy, if all subgraphs of $G$ have bounded average degree.
Chiba-Nishizeki proved that clique counting and $4$-cycle counting can be done
in linear time for bounded degeneracy graphs. The degeneracy has a special
significance in the analysis of real-world graphs, since it is intimately tied
to the technique of “core decompositions” [Ses23]. The family of bounded
degeneracy graphs is quite rich, and includes all minor-closed families,
bounded treewidth classes, and preferential attachment graphs. Most real-world
graphs tend to have small degeneracy ([GG06, JS17, SERF18, BCG20, BS20], also
Table 2 in [BCG20]), underscoring the practical importance of this class.

A series of recent subgraph counting advances provide strong dichotomy
theorems characterizing the patterns $H$ for which $\mathrm{Hom}_{H}(G)$ can
be computed in linear time, when $G$ has bounded degeneracy [Bre19, BPS20,
BPS21, BGL+22]. Assuming fine-grained complexity conjectures, linear time
algorithms exist iff the longest induced cycle of $H$ is strictly less than
$6$. This is a surprisingly precise characterization, even though the final
linear time algorithm is quite intricate.

At the “other end”, early work by Eppstein showed that, for all fixed $H$,
determining the existence of an $H$-homomorphsim is linear-time computable if
$G$ is planar [Epp95]. These results were extended to bounded genus graphs
[Epp00]. In a grand generalization of these results, Nešetřil and Ossona de
Mendez established the concept of _bounded expansion_ graph classes [NO08a].
These classes are defined using the theory of shallow minors. Bounded
expansion classes are quite broad, and include all bounded degree graphs,
include bounded tree-width graps, and all minor-closed families. Bounded
expansion graphs form a strict subset of bounded degeneracy graphs. They
proved that for all fixed $H$, if $G$ has bounded expansion, then one can
count $H$-homomorphism/subgraphs in linear time (refer to Table 18.1 and
Section 18.6 of [NO12] and [NO08b]).

To summarize the above discussion, we have two ends of a spectrum. Assume some
fine-grained complexity conjectures on triangle counting. Suppose $G$ has
bounded degeneracy. Then $\mathrm{Hom}_{H}(G)$ is linear-time computable iff
the longest induced cycle of $H$ is strictly less than $6$. On other hand, if
$G$ has bounded expansion, then for all $H$, $\mathrm{Hom}_{H}(G)$ can be
computed in linear time.

What lies in between? Is there some class of graphs between bounded degeneracy
and bounded expansion graphs where, say, $9$-cycle homomorphisms can be
counted in linear time? In the context of linear time algorithms, what
determines the hardness of $H$-homomorphism counting?

Figure 1: A visualization of our main result. There is a decreasing hierarchy
of input graph classes between bounded degeneracy and bounded expansion. There
is a corresponding increasing hierarchy of pattern classes, based on the
$LICL$. As we look at more restrictive graph classes, we can count
homomorphisms of more patterns in linear time.

###  1.1 Main Result

We give a comprehensive answer to the above questions. There is an infinite
hierarchy of classes between bounded degeneracy and bounded expansion graph
classes. For any pattern $H$, we can precisely point out the largest class
where $\mathrm{Hom}_{H}(G)$ is linear-time computable. We use $LICL(H)$ to
denote the length of the longest induced cycle in $H$.

These graph classes are defined using a concept called the _$r$ rank greatest
reduced average degree_ (or $r$-grad) of a graph [NO12]. The definition is
technical and explained in the next section. For any $r\in{\mathbb{Z}}^{+}$,
the quantity $\nabla_{r/2}(G)$ denotes the $r/2$-grad of $G$. This is a well-
defined graph quantity. Also, $\nabla_{0}(G)$ is the maximum average degree of
any subgraph of $G$, which, up to constant factors, is the graph degeneracy
(or arboricity) (Theorem $4$ in [Ses23]). Moreover, for any $r<s$,
$\nabla_{r/2}(G)\leq\nabla_{s/2}(G)$.

To give our main lower bound, we use the following common conjecture from
fine-grained complexity, the Triangle Detection Conjecture.

######  Conjecture 1.1.

(Triangle Detection Conjecture [AW14]) There exists a constant $\gamma>0$ such
that in the word RAM model of $O(\log{n})$ bits, any algorithm to detect
whether an input graph on $m$ edges has a triangle requires
$\Omega(m^{1+\gamma})$ time in expectation.

#### The informal statement.

Consider a class of input graphs with bounded $\nabla_{r/2}$. If
$LICL(H)<3(r+2)$, then $\mathrm{Hom}_{H}(G)$ can be counted in linear time. If
$LICL(H)\geq 3(r+2)$, then, assuming the Triangle Detection Conjecture, any
algorithm counting $\mathrm{Hom}_{H}(G)$ for graphs with bounded
$\nabla_{r/2}$ requires $\Omega(m^{1+\gamma})$ time. (Here, $m$ refers to the
number of edges in $G$.)

######  Theorem 1.2 (Main Theorem).

Fix any $r\in{\mathbb{Z}}^{+}$. Let $H$ be the pattern graph, and let the
input graph $G$ have $m$ edges. Let $f:\mathbb{N}\to\mathbb{N}$ denote some
explicit function. Let $\nabla_{r/2}(G)$ denote the $r/2$-grad of $G$.

  * •

If $LICL(H)<3(r+2)$, then there exists an algorithm that computes
$\mathrm{Hom}_{H}(G)$ in time $f(\nabla_{r/2}(G))\cdot m$.

  * •

If $LICL(H)\geq 3(r+2)$: Assume the Triangle Detection Conjecture. For any
function $g:\mathbb{N}\to\mathbb{N}$, there is no algorithm that computes
$\mathrm{Hom}_{H}(G)$ in time $g(\nabla_{r/2}(G))o(m^{1+\gamma})$ ($\gamma$ is
the constant from the Triangle Detection Conjecture).

Remark: The algorithm above is randomized, but the only use of randomness is
in building hash tables for a polynomial sized universe. Replacing the hash
tables with van Emde Boas trees, we can get a deterministic algorithm running
in time $O(m\log\log m)$.

#### The hierarchy for linear-time counting.

The theorem above can be informally visualized as Fig. 1. Consider an infinite
hierarchy of nested graph classes
$\mathcal{G}_{0}\supseteq\mathcal{G}_{1}\supseteq\mathcal{G}_{2}\ldots\supseteq\mathcal{G}_{\infty}$,
where $\mathcal{G}_{\infty}=\bigcap_{r\in{\mathbb{Z}}^{+}}\mathcal{G}_{r}$.
The class of bounded degeneracy graphs is $\mathcal{G}_{0}$ and the class of
bounded expansion graphs is $\mathcal{G}_{\infty}$. (Recall that even
$\mathcal{G}_{\infty}$ contains all minor-closed families; so it is really a
big graph class by itself.) Formally, $\mathcal{G}_{r}$ is the class of graphs
where $\nabla_{r/2}$ is bounded.

Now consider an “opposite” hierarchy of pattern classes ${\cal
H}_{0}\subseteq{\cal H}_{1}\subseteq{\cal H}_{2}\ldots\subseteq{\cal
H}_{\infty}$, where ${\cal H}_{\infty}$ is the set of all patterns. For every
$r\in{\mathbb{Z}}^{+}\cup\\{\infty\\}$, for all patterns $H\in{\cal H}_{r}$,
there is a linear time algorithm computing $\mathrm{Hom}_{H}(G)$ where
$G\in\mathcal{G}_{r}$. Moreover, for all $H\notin{\cal H}_{r}$, one requires
$m^{1+\gamma}$ time to compute $\mathrm{Hom}_{H}(G)$ for
$G\in\mathcal{G}_{r}$.

Specifically, for $r=0$, $\mathcal{G}_{0}$ is the class of bounded degeneracy
graphs, and ${\cal H}_{0}$ is the set of patterns with $LICL(H)<6$.

#### The obstacle of long induced cycles.

Theorem 1.2 also gives a precise condition that makes patterns harder to
count. Long induced cycles are the obstruction towards efficient (near-linear)
algorithms. There is a curious jump of $3$ for the $LICL$ at every “level” of
this hierarchy. While this may appear to be some artifact of the algorithm,
this jump is matched by the hardness results of Theorem 1.2. We find it quite
striking that the multiples of $3$ are exactly the transition points for the
hardness of homomorphism counting. The graph classes $\mathcal{G}_{r}$ are
defined by the $r/2$-grad values, which seem to have no connection to these
multiple of $3$ transition points.

#### The dichotomies for subgraph counting.

Subgraph counts can be easily represented as linear combinations of
homomorphism counts, using inclusion-exclusion. Hence, algorithms for the
latter can be used for subgraph counting. To count $H$-subgraphs, we count
homomorphisms of all patterns formed by specific mergings of $H$. Remarkably,
a result of Curticapean-Dell-Marx showed that this procedure is actually
optimal [CDM17]. Meaning, _lower bounds_ for homomorphism counting translate
to subgraph counting exactly as the upper bounds go. Using their techniques,
we can adapt Theorem 1.2 to subgraph counting dichotomies.

For a pattern $H$, the $Spasm(H)$ is the set of patterns obtained by merging
any independent set of $H$. (Note that an $H$-homomorphism may map an
independent set to the same vertex of $G$.) Abusing notation, let
$LICL(Spasm(H))$ denote the largest LICL value among all patterns in
$Spasm(H)$. To get our hierarchical dichotomies for subgraph counting, we
simply replace $LICL(H)$ in Theorem 1.2 by the larger quantity
$LICL(Spasm(H))$.

######  Theorem 1.3 (Dichotomies for subgraph counting).

Fix any $r\in{\mathbb{Z}}^{+}$. Let $H$ be the pattern graph, and let the
input graph $G$ have $m$ edges. Let $f:\mathbb{N}\to\mathbb{N}$ denote some
explicit function.

  * •

If $LICL(Spasm(H))<3(r+2)$, then there exists an algorithm that computes
$\mathrm{Sub}_{H}(G)$ in time $f(\nabla_{r/2}(G))\cdot m$.

  * •

If $LICL(Spasm(H))\geq 3(r+2)$: Assume the Triangle Detection Conjecture. For
any function $g:\mathbb{N}\to\mathbb{N}$, there is no algorithm with runtime
that computes $\mathrm{Sub}_{H}(G)$ in time
$g(\nabla_{r/2}(G))o(m^{1+\gamma})$ ($\gamma$ is the constant from the
Triangle Detection Conjecture).

###  1.2 Shallow Minors and Greatest Reduced Average Density

To formally explain what $\nabla_{r/2}$ means, we introduce the fundamental
concept of _shallow minors_. Recall that a minor of $G$ is a graph $F$ formed
as follows. Each vertex of $F$ represents a connected subgraph of $G$. All of
these connected graphs are vertex disjoint. An edge in $F$ represents an edge
in $G$ connecting the corresponding subgraphs. (Usually, a minor is described
in terms of deletions and contractions. The connected subgraphs described
above are contracted to the single vertices of $F$.)

In a shallow minor at depth $d$, the connected subgraphs have radius at most
$d$. This section is taken from Sections 4.2 and 4.4 of [NO12].

######  Definition 1.4.

The graph $G^{\prime}$ is a _shallow minor of $G$ at depth $d$_ if there
exists a collection of disjoint subsets $V_{1},\ldots,V_{p}$ of vertices in
$G$ such that:

  * •

Each graph induced on $V_{i}$ has radius at most $d$: in set $V_{i}$, there is
a vertex $x_{i}$ such that every vertex in $V_{i}$ is at distance at most $d$
from $x_{i}$ in the graph induced in $V_{i}$. This $x_{i}$ is called the
_center_ of $V_{i}$.

  * •

$G^{\prime}$ is a subgraph of the graph $G$ with $\mathcal{P}$ contracted:
each vertex $v$ of $G^{\prime}$ corresponds to a set $V_{i(v)}$, and edge
$(u,v)$ in $G^{\prime}$ corresponds to two sets $V_{i(u)}$ and $V_{i(v)}$
linked by at least one edge.

We use $G^{\prime}\;\in\;G\;\triangledown\;d$ to denote that $G^{\prime}$ is a
shallow minor of $G$ at depth $d$.

We can also define shallow minor at half-integer depths. Suppose
$G^{\prime}\in G\;\triangledown\;d$. There is a subgraph of $G$ that is a
_witness_ , which essentially contains the subgraphs of radius $d$ induced by
the $V_{i}$’s (corresponding to vertices of $G^{\prime}$) connected by certain
edges (corresponding to the edges of $G^{\prime}$). The latter edges are
called _external_ edges of the witness. The graph induced by each $V_{i}$ is
called a _bush_.

######  Definition 1.5.

A minor $G^{\prime}\in G\;\triangledown\;d$ is said to have _depth $d-(1/2)$_
if the following holds. There exists a subgraph of $G$ witnessing the
$G^{\prime}$ minor, such that for every external edge $(i,j)$: let $B_{i}$ and
$B_{j}$ be the corresponding bushes containing $i$ and $j$ respectively. Let
$x_{i}$ and $x_{j}$ be the corresponding centers. Then, either the distance of
$x_{i}$ to $i$, or the distance of $x_{j}$ to $j$, is strictly less than $d$.

Let us unpack this definition. Each bush is a graph of radius $d$. But to
witness the minor $G^{\prime}$, the external edges need not be “maximally far”
from the centers. So the minor is considered to have depth $d-(1/2)$, less
than just $d$. While this may seem like an extremely technical condition, the
half-integer depth minors play a crucial role in Theorem 1.2. To precisely
capture the linear-time hardness of homomorphism counting, we need the classes
defined through half-integer depth minors.

We define the central concept of the greatest reduced average density.

######  Definition 1.6.

Let $r$ be a non-negative half-integer. The rank $r$ _greatest reduced average
density (grad)_ of a graph $G$ is defined as:

$\displaystyle\nabla_{r}(G)=\max_{G^{\prime}\;\in\;G\;\triangledown\;r}{\left\\{\frac{|E_{G^{\prime}}|}{|V_{G^{\prime}}|}\right\\}}$

In words, the rank $r$ grad is the maximum average degree over all minors of
$G$ of depth $r$.

The classes of the hierarchy defined by Theorem 1.2 (and Fig. 1) are bounded
$\nabla_{r/2}$ graph classes. Consider the simple case of $r=0$. A depth $0$
minor is just a subgraph. The rank $0$ grad is the maximum average degree over
subgraphs, which is (up to constant factors) the graph degeneracy.

A graph class with bounded $\nabla_{0}$ is a class where all subgraphs of
graphs in the class have bounded average degree. This is precisely
$\mathcal{G}_{0}$ in our hierarchy. A graph class has _bounded expansion_ if
$\nabla_{r}$ is bounded for all $r$.

##  2 Main Ideas

Our result has many moving parts. In this section, we give a high-level
overview with a focus on various obstacles we faced. Many of the new concepts
and definitions were introduced to overcome these obstacles. Our result is
obtained from marrying techniques from three sources: first and foremost, the
deep theory of sparsity of Nešetřil and Osana de Mendez [NO12], the DAG-
treewidth of Bressan [Bre19, Bre21], and the unique reachability and induced
cycle obstructions of Bera et al. (denoted BPS and BGLSS) [BPS21, BGL+22]. Our
lower bounds are fairly direct adaptations of techniques from BPS and BGLSS.

#### Graph orientations.

Arguably, the starting point for any work on subgraph counting related to
graph degeneracy is the clique-counting work of Chiba-Nishizeki [CN85b]. A
number of results recognized that the Chiba-Nishizeki ideas can be recast in
terms of _graph orientations_ [MB83, Ses23]. The primary challenge for
homomorphism counting on sparse graphs is the presence of high-degree
vertices. Such vertices kill any simple brute force BFS procedure to find
homomorphisms. The idea is to orient/direct the edges of $G$ into a DAG, such
that _outdegrees_ are bounded. The hope is then to search for
homomorphisms/subgraphs in constant-radius outneighborhoods, which will have
bounded size.

A natural approach is to find an (acyclic) orientation that minimizes the
maximum outdegree. The optimal quantity is called the _graph degeneracy_ , and
remarkably, there is a simple linear time procedure to find such a “degeneracy
orientation” [MB83]. Moreover, this simple algorithm is intimately connected
with $\nabla_{0}(G)$; the degeneracy is a $2$-approximation of
$\nabla_{0}(G)$. In words, all subgraphs of $G$ have bounded average degree
iff the degeneracy orientation has bounded outdegree. And we have assumed that
$\nabla_{0}(G)$ is bounded, so we can orient $G$ into a DAG $\vec{G}$ of
bounded outdegree.

#### Homomorphism counting for bounded degeneracy graphs.

We now outline the upper bound results of BPS and BGLSS, which fundamentally
use Bressan’s DAG-treewidth. Let us refer to an $H$-homomorphism/subgraph as a
_match_.

Every $H$-match in $G$ forms some directed match in $\vec{G}$. We can
enumerate over all the (constant many) orientations $\vec{H}$ of $H$, and
count $\vec{H}$-matches in $\vec{G}$. So we reduce to a directed acyclic
homomorphism counting problem.

Suppose $\vec{H}$ has a single source vertex, so there is a rooted directed
tree $\vec{T}$ spanning $\vec{H}$. Since $\vec{G}$ has bounded outdegree,
there are $O(n)$ $\vec{T}$-matches in $\vec{G}$. (Which can be enumerated by a
bounded depth outward BFS from each vertex.) We can enumerate over all these
$\vec{T}$-matches, and see which of them induce $\vec{H}$-matches. When $H$ is
a clique, this recovers Chiba-Nishizeki’s original algorithm. Moreover, this
is probably one of the best practical algorithms for small clique counting
[PSV17].

The story gets interesting when $\vec{H}$ has multiple sources. In this case,
$\vec{H}$ can be covered by a collection of rooted trees, one from each source
in $\vec{H}$. These rooted trees are “fragments” of $\vec{H}$, which can be
pieced together to yield an $\vec{H}$-match. For each fragment $\vec{T}$, we
can enumerate all the $\vec{T}$-matches. The “piecing together” requires a
careful indexing of all these matches.

When two fragment trees $\vec{T}$ and $\vec{T^{\prime}}$ share a vertex (in
$\vec{H}$), we have to select corresponding matches in $\vec{G}$ that share a
vertex. It is challenging to index the tree matches appropriately to retrieve
the relevant matches that might lead to an $\vec{H}$-match. A number of
results designed ad hoc methods for orientations of various $H$ [Coh09, PSV17,
BPS20]. A breakthrough was achieved by Bressan, who gave a systematic
algorithm that indexes the fragments to efficiently count $\vec{H}$-matches
[Bre19]. He introduced a novel concept of _DAG-tree decomposition_.

For a given $\vec{H}$, the DAG-tree decomposition is a tree ${\cal T}$ where
nodes represent bags of sources in $\vec{H}$. Roughly speaking, each subtree
of ${\cal T}$ represents a subgraph of $\vec{H}$ formed by all vertices
reachable from the sources (in the bags) in ${\cal T}$. The subgraphs
represented by independent subtrees can be counted/indexed independently. The
non-trivial step is the “merging” of matches of children subtrees in ${\cal
T}$. Suppose a node in ${\cal T}$ has two children, which represent the
subgraphs $\vec{H_{1}}$ and $\vec{H_{2}}$. The parent node will represent a
subgraph $\vec{H^{\prime}}$ that contains $\vec{H_{1}}$ and $\vec{H_{2}}$.
Roughly speaking, we construct $\vec{H^{\prime}}$-matches by extending
$\vec{H_{1}}$ and $\vec{H_{2}}$-matches through some shared vertices. These
shared vertices are reachable from the sources in the bag represented by the
parent node. The complexity of this step is determined by the bag size. The
DAG-treewidth $\tau$ is the size of the largest bag, and the running time is
$O(n^{\tau})$. Relevant to us, when the DAG-treewidth is one, the algorithm
runs in (near) linear time.

We stress that the process is highly non-trivial, and a lot of homomorphism
information needs to be “compressed”. A planar graph can have $\Theta(n^{2})$
$4$-cycles, yet the above method can count them exactly in linear time.

When is the DAG-treewidth of $\vec{H}$ one? This is precisely captured by BPS
and BGLSS. If $LICL(H)<6$, then for all orientations of $\vec{H}$, the DAG-
treewidth is one. The proof of this fact involves new concept of unique
reachability graphs; but we defer the discussion of this point later.

The above summary gives the overall picture of proving the existence of linear
time algorithms for $H$-homomorphism counting on bounded degeneracy graphs,
where $LICL(H)<6$.

Figure 2: On the left, an oriented $6$-cycle with $3$ sources. This
orientation has a DAG-treewidth greater than $1$. It is not possible to
decompose this pattern in a way that allows us to compute homomorphisms in
linear time. The graph on the right is the result of connecting the endpoints
of each out-out wedge, giving a fraternal augmentation. This new graph has a
$LICL<6$ and hence for any orientation of the red edges, the DAG-treewidth is
$1$.

###  2.1 The $6$-cycle obstruction

We now explain the $6$-cycle barrier. Consider the oriented $6$-cycle
$\vec{H}$ in the left of Fig. 2. It can be partitioned into three out-out
wedges (paths of length $2$), each corresponding to a unique source. Thus,
$\vec{H}$ forms a “triangle” of out-out wedges. Counting
$\vec{H}$-homomorphisms is equivalent to counting triangles in the following
graph. In the oriented $\vec{G}$, enumerate all out-out wedges $(u,v,w)$,
where $v$ denotes the wedge center. Create a new undirected graph
${G^{\prime}}$ with the edges $(u,w)$. Since $G$ has bounded degeneracy,
$\vec{G}$ has bounded outdegree, and the number of out-out wedges is linear.
So $G^{\prime}$ has $O(m)$ edges. Triangles in $G^{\prime}$ are precisely
$6$-cycles in $\vec{G}$. Indeed, this argument gives the hardness construction
in BPS, reducing triangle counting in arbitrary graphs to $6$-cycle counting
in bounded degeneracy graphs.

This is the starting point for our investigation. Under what circumstance can
$6$-cycle counting be done in linear time? If the graph $G^{\prime}$ obtained
above also had bounded degeneracy, then triangle counting in $G^{\prime}$
could be done in linear time (since $G^{\prime}$ has $O(m)$ edges). What
condition does $G$ need to satisfy for $G^{\prime}$ to have bounded
degeneracy?

#### Enter shallow minors.

Let us imagine contracting every alternate edge of the $6$-cycle. This leads
to a triangle minor. We can choose the centers of these contracted components
with the following property. The three non-contracted edges are incident to
some center. Hence, this forms a shallow minor of depth $1/2$, according to
Definition 1.5. Non-trivially, one can find a method of contracting $G$, so
that all the $6$-cycles in $G$ are consistently contracted to triangles.
Meaning, there is a $1/2$-shallow minor $G^{\prime\prime}$ such that
$6$-cycles of $G$ become triangles in $G^{\prime\prime}$. The shallow minor
machinery of Nešetřil and Ossona de Mendez can be used to show if
$G^{\prime\prime}$ has bounded degeneracy, then the graph $G^{\prime}$ (from
the previous paragraph) also has bounded degeneracy.

Hence, if all $1/2$-shallow minors of $G$ have bounded degeneracy, then we can
count triangles in $G^{\prime}$ in linear time. And the former condition is
precisely saying that $\nabla_{1/2}(G)$ is bounded.

#### Implementing via fraternal augmentations.

Let us implement the above approach so that it works for all $H$ with
$LICL(H)=6$. We start with $\vec{G}$ and $\vec{H}$ as before, and assume that
$\nabla_{1/2}(G)$ is bounded. We perform a series of _fraternal augmentations_
in both $\vec{G}$ and $\vec{H}$. For every out-out wedge $(u,v,w)$, we add the
edge $(u,w)$ to get the graphs $\vec{G^{\prime}}$ and $\vec{H^{\prime}}$. Note
that new edges are undirected, so we try to orient them in $\vec{G^{\prime}}$
so that the maximum outdegree is minimized. Denote this graph as
$\vec{G^{\prime\prime}}$. We then enumerate over all orientations
$\vec{H^{\prime\prime}}$ of the new edges in $\vec{H^{\prime}}$. Finally, we
count $\mathrm{Hom}_{\vec{H^{\prime\prime}}}(\vec{G^{\prime\prime}})$ and sum
over all the $\vec{H^{\prime\prime}}$.

Since $\nabla_{1/2}(G)$ is bounded, we can prove that $\vec{G^{\prime\prime}}$
will have bounded outdegree. We can also show that
$LICL(\vec{H^{\prime\prime}})$, treated as an undirected graph, will be
strictly less than $6$. The key is that the augmentations in $\vec{H}$ will
reduce the length of _all_ induced cycles. This is seen for the simple example
of the $6$-cycle in Fig. 2. Hence, the previous machinery of BPS and Bressan
using width one DAG-tree decompositions can be applied to get a linear time
algorithm. With some painstaking effort, one can push this approach to
$LICL(H)<8$. Essentially, fraternal augmentations in $H$ reduce the $LICL$ to
less than $6$, at which point previous methods can run in linear time.

We note that the term “fraternal augmentation” was introduced by Nešetřil and
Ossana de Mendes (Chap. 4 of [NO12]). But the idea is implicit in many
previous results on subgraph counting in bounded degeneracy graphs [Coh09,
PSV17, OB17].

Figure 3: An example of performing fraternal augmentations on an oriented $9$
cycle pattern (black edges). The first augmentation gives the red edges,
reaching a situation analogous to the $6$ cycle in Fig. 2, an additional
fraternal augmentation (blue edges) gives a pattern with an $LICL$ less than
$6$ and hence a DAG-treewidth of $1$.

###  2.2 More rounds of augmentations

Consider the oriented $9$-cycle pattern of Fig. 3. Let us perform a single
round of fraternal augmentations, to get the red edges. The $LICL$ has now
gone down to $6$, so we still cannot count homomorphisms (of the resulting
pattern) in linear time. Suppose we orient these new (red) edges, and perform
another fraternal augmentation. This step adds the blue edges, and the $LICL$
is down to $3$.

To count $9$-cycle homomorphisms in linear time, we need to perform two rounds
of fraternal augmentations in $G$, and hope that the degeneracy of the
resulting graph is bounded. One might imagine that if $\nabla_{1}$ is bounded,
then two rounds of augmentations will lead to a bounded degeneracy graph. It
turns out the situation is far more nuanced. There are new obstacles for
counting $9$-cycle homomorphisms in linear time. This leads to the next
technical tool.

#### Designing fraternity functions.

Augmentations are really shortcuts in the graph; each augmentation represents
a path of longer length. In general, we assume a bound on $\nabla_{r}(G)$ to
get linear-time algorithms. Such a bound refers to $r$-shallow minors, which
essentially contract paths of length at most $2r$. Our augmentations on such a
graph should not shortcut a path that is longer than $2r$, since the bounded
$\nabla_{r}(G)$ condition cannot say anything about such augmentations. Thus,
we have to perform augmentations carefully so that the bounded $\nabla_{r}(G)$
condition can be used.

We discover the way to perform such careful augmentations is by crafting
specific _fraternity functions_ of Nešetřil and Ossona de Mendez. This is a
highly technical definition. At a high level, every augmented edge has a
weight, which is (roughly) speaking the length of the path shortcut by this
edge. Any subsequent augmentation is not allowed to exceed a weight threshold.
We show an example of these weights in Fig. 3. The final augmentation is
described by a fraternity function, which satisfies a number of consistency
constraints. A deep result from the theory of sparsity is that if
$\nabla_{r}(G)$ is bounded, then augmenting by a “$(2r+1)$-fraternity
function” maintains bounded degeneracy. We apply this weighted fraternity
function on both on the input $G$ and pattern $H$.

Figure 4: An example of how fraternal augmentations do not preserve
homomorphisms. Consider the homomorphism $\phi$ from $H$ to $G$ with
$\phi(a)=1$ and $\phi(b)=\phi(c)=2$. We can see how this will not be a valid
homomorphism from $H^{\prime}$ to $G^{\prime}$ as the new edge connecting $b$
and $c$ is not preserved. However the number of subgraphs is preserved as the
subgraphs $\\{1,2,3\\}$ in $G$ and in $G^{\prime}$ are equivalent to $H$ and
$H^{\prime}$ respectively.

#### Maintaining homomorphism counts.

There are some annoyances when performing augmentations for homomorphism
counting. We explain these to motivate seemingly artificial technical
conditions in our homomorphisms and final counting algorithms.

As we add more edges to $\vec{G}$, we may create “fake” $\vec{H}$
homomorphisms. On the flip side, when augmenting $\vec{H}$, some existing
matches may be inadmissible (due to new edges in the pattern). We have a
simple example in Fig. 4 where augmentations do not preserve homomorphism
counts.

We use two ideas to handle these problems. Firstly, we enforce that
homomorphisms must be weight preserving, where the weights come from the
fraternity functions described earlier. This prevents mapping of augmented
edges to original edges and vice versa. Secondly, it is more convenient to
create a new input instance from a graph product $G\times H$. We find
$H$-homomorphisms in this product graph, where it is much easier to track the
effect of augmentations on $H$-homomorphisms. All in all, we can then show
direct correspondences between homomorphisms in the original graph $G$, and
the homomorphisms in the final graph (constructed by graph products and a
series of augmentation steps).

Figure 5: An example of a pattern where we have performed 2 iterations of the
augmentation (we will call this a $3$-fraternal extension of the pattern). As
we can see the augmented pattern still has $LICL\geq 6$. However, the hub-
treewidth is $1$.

###  2.3 A major obstruction: extraneous induced cycles

So the overall story looks like the following. We have a graph $G$ such that
$\nabla_{r}(G)$ is bounded. We repeatedly perform augmentations, as long as
they satisfy the constraints of a $(2r+1)$-fraternity function. Intuitively,
one can think of $2r$ rounds of augmentations. The resulting graph
$G^{\prime}$ has bounded degeneracy. One also performs similar augmentations
on $H$ to get the new pattern $H^{\prime}$. (Of course, there is the extra
complication of orienting every new edge that is created, but let us ignore
that for now.)

The hope is that $LICL(H^{\prime})$ is strictly less than $6$, in which case
previous algorithms can count $H^{\prime}$-homomorphisms in $G^{\prime}$ in
linear time. Specifically, if $LICL(H)<3(r+2)$, we would like
$LICL(H^{\prime})$ to be less than $6$. We think that with sufficiently many
rounds of augmentations, we can cut down the $LICL$ length.

And this is false. This statement fails, but only for a sufficiently complex
example. The above approach does work for counting cycle homomorphisms, or
when $LICL(H)<8$. But there is a pattern $H$ with $LICL(H)=8$ where the
approach breaks.

For ease of exposition, we present an example with $LICL(H)=9$. Consider the
pattern in Fig. 5. The problem is that the newly added augmentation edges
(given in blue and red) create a new induced cycle of length $6$. This induced
cycle is given by the red vertices. Unfortunately, we cannot guarantee a DAG-
treewidth of one, so the existing algorithmic approach of BPS and BGLSS (as a
black box) cannot yield a linear time algorithm.

At this stage, the authors thought an entire rethink was needed. Thankfully,
that was not needed. The path around this obstruction is an unpacking of
Bressan’s algorithm and a deeper look into the BPS machinery. By getting to
the core of these results, we can generalize them appropriately to deal with
these “extraneous” induced cycle in the patterns.

#### Dealing with cyclicity.

It turns out that a seemingly minor technicality is important to handling Fig.
5. We started with a DAG $\vec{G}$ and a pattern $\vec{H}$. The reason to make
$G$ into a DAG $\vec{G}$ was that the degeneracy orientation was linear time
computable and gave a DAG with constant outdegree. As a result, the pattern
$\vec{H}$ is also a DAG, which motivated DAG-tree decomposition and DAG-
treewidth.

When we augment, we add new _undirected_ edges. To do a subsequent round of
fraternal augmentations, we need to orient these edges, so that we can
construct new out-out wedges. Every orientation has to keep the outdegree
bounded. A natural approach is to extend the existing partial order (implied
by the DAG $\vec{G}$). This actually _cannot_ work. Meaning, if we want to
keep the overall outdegree bounded after multiple augmentation rounds, then we
must use cyclic orientations of $G$.

#### Hubsets to the rescue.

So we need to deal with cyclic patterns $\vec{H}$, while Bressan’s algorithm
is tailored to DAG patterns. Our insight is that Bressan’s algorithm is quite
flexible, and we can generalize the concept of DAG sources to “hubsets”. A
hubset is a set of vertices from which all other vertices can be reached. The
corresponding definitions of DAG-tree decomposition and DAG-treewidth all
generalize to hubsets. Technically, the proofs of Bressan go through quite
directly. But hubsets give us significantly more flexibility in minimizing the
“hub treewidth”.

Recall that the obstacle of Fig. 3 has an induced cycle of length $6$, and is
not guaranteed to have DAG-treewidth one. But we can argue than the hub-
treewidth is just one, which leads to a linear time algorithm for counting
that pattern (when $\nabla_{1}(G)$ is bounded).

#### Extending BPS to hubsets.

In order to take advantage of the hubsets we have to rework the machinery of
BPS that related induced cycles to DAG-treewidth, the process is quite
technical. All in all, we can prove the following. If $LICL(H)<3(r+2)$, then
(roughly speaking) after performing $r$ rounds of fraternal augments, the
resulting pattern $\vec{H}$ has a hub treewidth of one.

###  2.4 Lower bounds and subgraphs

The lower bounds closely follow the techniques of BPS and BGLSS [BPS21,
BGL+22]. Using the tensorization techniques of Curticapean, Dell, and Marx,
one can essentially show that the hardest patterns to count are cycles. The
ideas in BPS and BGLSS are to use various graph products and manipulations,
and they need to maintain the degeneracy of their various constructions. In
our setting, we deal with more restrictive rank $r$ bounded grad graphs, so we
need some extra care in our arguments.

The hardness for cycle counting is fairly straightforward, and taken from
[BPS20]. We basically subdivide an edge into a longer path, and reduce
triangle counting in arbitrary graphs to cycle counting in bounded grad
graphs. We perform some calculations to show that the resulting graphs has
bounded grad. The rank $r$ determines the length of the subdivision, and hence
the length of the cycle that a triangle is converted to. It suffices to show
that the final graph has bounded rank $r$ grad, which is quite direct. These
simple constructions match the upper bounds of Theorem 1.2, completing the
story for homomorphism counting.

The deep insight of Curticapean, Dell, and Marx is that, as their title says,
homomorphisms form a good basis for subgraph counting [CDM17]. Essentially,
they show that for any quantity represented as a linear combination of
homomorphisms, the complexity of computing that quantity is determined by the
hardest homomorphism. It is fairly direct to see that $H$-subgraph counting
can be done by an inclusion-exclusion on the various
$H^{\prime}$-homomorphisms (for $H^{\prime}\in Spasm(H)$). Using techniques
from [CDM17], we can translate the inclusion-exclusion algorithm into hardness
for subgraph counting.

##  3 Related Work

The theory of sparsity is a deep topic at the intersection of graph theory,
logic, and combinatorics. We refer the reader to the textbook [NO12]. Chapters
4, 5, and 7 contain most of the relevant background for our work.

We cannot do justice to the literature on homomorphism counting, which has an
immense history. It was observed that the treewidth of the pattern plays a
role in the final complexity. Díaz et al. [DST02] designed an algorithm with
runtime $O(2^{k}n^{t(H)+1})$ where $t(H)$ is the treewidth of the target graph
$H$. Dalmau and Jonsson [DJ04] proved that such a dependence on treewidth is
necessary. They show that that $\mathrm{Hom}_{H}(G)$ is polynomial time
solvable if and only if $H$ has bounded treewidth, otherwise it is
$\\#W[1]$-complete.

Relevant to our framework of restrictions on both $G$ and $H$, Roth and
Wellnitz [RW20] consider a doubly restricted version of $\mathrm{Hom}_{H}(G)$,
where both $H$ and $G$ are from graph classes. They primarily focus on the
parameterized dichotomy between poly-time solvable instances and
$\\#W[1]$-completeness.

Degeneracy is a measure of sparsity and has been known since the early work of
Szekeres-Wilf [SW68]. We refer to reader to a recent short survey of Seshadhri
on subgraph counting and degeneracy [Ses23]. The family of bounded degeneracy
graphs is quite rich: it involves all minor-closed families, bounded expansion
families, and preferential attachment graphs. Most real-world graphs have
small degeneracy ([GG06, JS17, SERF18, BCG20, BS20], also Table 2 in [BCG20]).

Arguably the first work on exploiting degeneracy for subgraph counting is the
seminal work of Chiba and Nishizeki [CN85a]. Since then, it has been a central
technique in theoretical and practical algorithms [Epp94, ANRD15, JSP15,
PSV17, OB17, JS17, PS20].

Bressan [Bre19] introduced the concept of DAG-treewidth to design faster
algorithms for homomorphism and subgraph counting problems in bounded
degeneracy graphs. Bressan showed that for a pattern $H$ with $|V(H)|=k$ and
an input graph $G$ with $|E(G)|=m$ and degeneracy $\kappa$, one can count
$\mathrm{Hom}_{H}(G)$ in $f(\kappa,k)O(m^{\tau(H)}\log m)$ time, where
$\tau(H)$ is the DAG-treewidth of $H$. Assuming the exponential time
hypothesis [IPZ98], the subgraph counting problem does not admit any
$f(\kappa,k)m^{o(\tau(H)/\ln\tau(H))})$ algorithm, for any positive function
$f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$. Recent work of Bressan,
Lanziger, and Roth develops algorithms for pattern counting in directed graphs
[BLR23].

A focus on linear time algorithm in bounded degeneracy graphs was initiated by
Bera, Pashanasangi, and Seshadhri [BPS20]. They showed the lower bound for
counting $6$-cycles. That work was significantly generalized by BPS and BGLSS
which completely characterized linear time homomorphism counting in bounded
degeneracy graphs [BPS21, BGL+22].

There are numerous pattern counting results in Big Data models such as the
property testing model [ELRS17, ERS18, AKK18, ERS20], the streaming model
[BKS02, MMPS11, KMSS12, AGM12, JSP13, PTTW13, MVV16, BC17, BS20], and the Map
Reduce model [Coh09, SV11, KPP+14].

We now discuss the triangle detection conjecture. Itai and Rodeh [IR78] gave
the first non-trivial algorithm for the triangle detection and finding problem
with $O(m^{3/2})$ runtime. The best known algorithm for the triangle detection
problem uses fast matrix multiplication and runs in time
$O(\min\\{n^{\omega},m^{{2\omega}/{(\omega+1)}}\\})$ [AYZ97]. If $\omega=2$,
this yields a running time of $m^{4/3}$, which many believe to be the true
complexity. The current best is $O(m^{1.41\ldots})$, using the best matrix
multiplication algorithms Any improvement on this bound would be considered a
huge breakthrough in algorithms. Disproving the Triangle Detection Conjecture
would require an algorithm that would go even beyond the best possible matrix
multiplication based algorithm. We refer the reader to [AW14] for more details
on Triangle Detection Conjecture.

##  4 Preliminaries

###  4.1 Graphs and Homomorphisms

We use $G=(V_{G},E_{G})$ to denote the input graph, we will use $n=|V_{G}|$
for the number of vertices of $G$ and $m=|E_{G}|$ for the number of edges. We
use $H=(V_{H},E_{H})$ for the pattern graph and $k=|V_{H}|$ for the number of
vertices of $H$, we consider $k$ to have constant value. Both graphs are
simple and undirected.

We will also have labeled graphs, a labeled graph is a graph
$G=(V_{G},E_{G},L_{G})$, where $L_{G}:V_{G}\to S$ is the label function that
maps the vertices of the graph to a set of labels $S$. Additionally we will
have weighted labeled graphs $G=(V_{G},E_{G},W_{G},L_{G})$ where
$W_{G}:E_{G}\to\mathbb{N}$ is the weight function that maps the edges of the
graph to the correspondent weight. We will use $E_{G}^{i}$ to denote the the
subset of edges of $G$ with weight equal to $i$, that is, $E_{G}^{i}=\\{e\in
E_{G}:W_{G}(e)=i\\}$.

A homomorphism from $H$ to $G$ is a mapping $\phi:V_{H}\to V_{G}$ where
$\forall(u,u^{\prime})\in E_{H}$ we have $(\phi(u),\phi(u^{\prime}))\in
E_{G}$. We use $\Phi(H,G)$ for the set of homomorphisms from $H$ to $G$. We
denote with $\mathrm{Hom}_{H}(G)$ to the problem of counting the number of
distinct homomorphisms from $H$ to $G$, that is
$\mathrm{Hom}_{H}(G)=|\Phi(H,G)|$.

We extend these definitions for weighted and labeled graphs. Given two
weighted labeled graphs $H^{\prime},G^{\prime}$ we will define a homomorphism
from $H^{\prime}$ to $G^{\prime}$ as a mapping $\phi:V_{H^{\prime}}\to
V_{G^{\prime}}$ such that $\forall\ u\in V_{H^{\prime}}\
L_{H^{\prime}}(u)=L_{G^{\prime}}(\phi(u))$ and $\forall(u,v)\in
E_{H^{\prime}}$ we have $(\phi(u),\phi(u^{\prime}))\in E_{G^{\prime}}$ and
$W_{H^{\prime}}((u,v))\geq W_{G^{\prime}}((\phi(u),\phi(v)))$. Similarly
$\mathrm{Hom}_{H^{\prime}}(G^{\prime})$ will correspond to the problem of
counting the number of homomorphisms from $H^{\prime}$ to $G^{\prime}$.

We use $LICL(H)$ for the largest induced cycle length of $H$, that is, the
maximum length of any induced subgraph of $H$ that forms a cycle. We use
$Spasm(H)$ to refer to the spasm of $H$, that is, the collection of graphs
obtained by contracting subsets of not-neighboring vertices in $H$.
$LICL(Spasm(H))$ will be the largest induced graph in all the graphs in the
spasm of $H$.

###  4.2 Subgraph copies

Given the graphs $H$ and $G$ we say that $G^{\prime}$ is a copy of $H$ in $G$
if $G^{\prime}$ is a subgraph of $G$ such that there exists a 1:1 mapping from
$H$ to $G^{\prime}$ that preserves the edges. We use $\mathrm{Sub}_{H}(G)$ for
the problem of counting the number of distinct non-induced copies of $H$ in
$G$.

There is a direct relation between $\mathrm{Sub}_{H}(G)$ and
$\mathrm{Hom}_{H^{\prime}}(G)$ for the graphs $H^{\prime}\in Spasm(H)$. The
exact identity can be seen in [CDM17], but we can express it as follows:

######  Lemma 4.1.

Given two graphs $G$ and $H$, for each graph $H_{i}\in Spasm(H)$ there exists
a non-zero constant $c_{i}$ such that:

$\displaystyle\mathrm{Sub}_{H}(G)=\sum_{H_{i}\in
Spasm(H)}c_{i}\mathrm{Hom}_{H_{i}}(G)$

###  4.3 Degeneracy and the degeneracy orientation

A graph $G$ is $\kappa$-degenerate if every subgraph of $G$ has a minimum
degree of at most $\kappa$. The degeneracy of $G$, $\kappa(G)$, is the maximum
value of $\kappa$ such that $G$ is $\kappa$-degenerate. The degeneracy is also
called the _coloring number_. A graph has bounded degeneracy when $\kappa$ has
constant value.

There is a way of orienting a graph acyclically, such that the maximum
outdegree is upper bounded by the degeneracy of such graph. This is a classic
result in graph theory (refer to Section 5.2 of [Die10] and survey [Ses23]).
To construct such orientation, one can generate an ordering of the vertices of
$G$ by iteratively selecting the lowest degree vertex in the graph and
removing it. Hence the degeneracy orientation can be constructed in linear
time.

######  Fact 4.2.

([MB83]) Given an undirected graph $G$ with degeneracy $\kappa=\kappa(G)$,
there exists an acyclical orientation $\vec{G}^{\kappa}$ of $G$ such that the
maximum outdegree of $\vec{G}^{\kappa}$ is $\kappa$. Moreover, this
orientation can be computed in time $O(n+m)$.

For a directed graph $\vec{G}$, we will use $\Delta^{+}(\vec{G})$ to refer to
the maximum outdegree of any vertex of $\vec{G}$.

###  4.4 Shallow Topological Minors and Top-Grads

We can define shallow topological minors, which play a useful role in our
analysis.

######  Definition 4.3 (Shallow topological Minor [NO12]).

A shallow topological minor of a graph $G$ of depth $d$ is a graph
$G^{\prime}$ obtained from $G$ by taking a subgraph and then replacing an
internally vertex disjoint family of paths of length at most $2d+1$ by single
edges. $G^{\prime}$ is a shallow topological minor of $G$ at depth $d$ if
there is a $\leq d$-subdivision of $G^{\prime}$ that is a subgraph of $G$.

We use $G^{\prime}\;\in\;G\;\tilde{\triangledown}\;d$ to indicate that
$G^{\prime}$ is a shallow topological minor of $G$ at depth $d$.

Similar to grads, we can define the the topological greatest reduced average
density:

######  Definition 4.4.

(top-grad [NO12]) The topological greatest reduced average density (top-grad)
with rank $r$ of a graph $G$ is defined as:

$\displaystyle\tilde{\nabla}_{r}(G)=\max_{G^{\prime}\;\in\;G\;\tilde{\triangledown}\;r}{\left\\{\frac{|E_{G^{\prime}}|}{|V_{G^{\prime}}|}\right\\}}$

Nešetřil and Ossona de Mendez proved that there is a polynomial relation
between $\nabla$ and $\tilde{\nabla}$ of a graph $G$, this is given by the
following fact:

######  Fact 4.5 (Corollary $4.1$ in [NO12]).

For every graph $G$ and every integer $r\geq 1$ holds

$\displaystyle\tilde{\nabla}_{r}(G)\leq\nabla_{r}(G)\leq
4(4\tilde{\nabla}_{r}(G))^{(r+1)^{2}}$

This corollary directly gives us the following fact.

######  Fact 4.6.

For any constant $r$, the classes of bounded rank $r$ grads and bounded rank
$r$ top-grads are equivalent. Moreover, for any graph $G$, $\nabla_{r}(G)$ is
bounded if and only if $\tilde{\nabla}_{r}(G)$ is bounded.

###  4.5 DAG-treewidth and Bressan’s algorithm

Bressan introduced the concepts of DAG-tree decomposition and DAG-treewidth of
a directed acyclic graph $\vec{H}$ [Bre19]. Before defining the DAG-tree
decomposition of $\vec{H}$ we need to define a few concepts. We use
$S=S(\vec{H})$ to denote the set of sources of $\vec{H}$, that is, the
vertices in $\vec{H}$ with no in-edges. Given two vertices $u,v\in
V_{\vec{H}}$, we say that $v$ is reachable from $u$ if there exists a direct
path in $\vec{H}$ from $u$ to $v$.

For a vertex $s\in\vec{H}$ we use $Reach_{\vec{H}}(s)$ to denote the set of
vertices of $\vec{H}$ that are reachable from $s$. We can extend this
definition to set of vertices, let $B\subseteq S$ is a set of vertices of
$\vec{H}$, we use $Reach_{\vec{H}}(B)=\bigcup_{s\in B}Reach_{\vec{H}}(s)$ for
the union of the reachability sets of the vertices in the set $B$.
Additionally we use $\vec{H}(s)$ to represent the induced subgraph of
$\vec{H}$ in the vertices of $Reach_{\vec{H}}(s)$.

We can now bring the definition of DAG-tree decomposition of $\vec{H}$:

######  Definition 4.7 (DAG-tree decomposition[Bre19]).

Let $\vec{H}$ be a directed acyclic graph with source set $S$. A DAG-tree
decomposition of $\vec{H}$ is a rooted tree $T=(\mathcal{B},{\cal E})$ with
the following properties:

  1. 1.

Each node $B\in\mathcal{B}$ is a bag of sources, $B\subseteq S$.

  2. 2.

$\bigcup_{B\in\mathcal{B}}B=S$.

  3. 3.

For all $B,B_{1},B_{2}\in\mathcal{B}$, if $B$ is on the unique path between
$B_{1}$ and $B_{2}$ in $\mathcal{T}$, then we have $Reach_{\vec{H}}(B_{1})\cap
Reach_{\vec{H}}(B_{2})\subseteq Reach_{\vec{H}}(B)$.

Bressan also defined the DAG-treewidth:

######  Definition 4.8 (DAG-treewidth($\tau$) [Bre19]).

The DAG-treewidth of a DAG-tree decomposition ${\cal T}=(\mathcal{B},{\cal
E})$ is defined as the maximum bag size over all the bags of sources of ${\cal
T}$:

$\displaystyle\tau({\cal T})=\max_{B\in\mathcal{B}}|B|$

We also use $\tau(\vec{H})$ to refer to the DAG-treewidth of the directed
graph $\vec{H}$, which is the minimum $\tau({\cal T})$ over all possible DAG-
tree decomposition ${\cal T}$ of $\vec{H}$.

Bressan introduced an algorithm that allows to compute the number of
Homomorphisms between directed acyclical graphs $\vec{H}$ and $\vec{G}$. This
algorithm uses the DAG-tree decomposition ${\cal T}$ of $\vec{H}$ to compute
the homomorphisms from $\vec{H}$ to $\vec{G}$ from the homomorphisms of
$\vec{H}(B)$ to $\vec{G}$ for each of the bags sources $B$ in ${\cal T}$. When
$\vec{G}$ has bounded outdegree and $\vec{H}$ has $\tau(\vec{H})=1$ this will
take $O(n\log n)$ time. We can restate this result as follows:

######  Lemma 4.9 ([Bre19]).

Let $\vec{H}$ be a directed acyclic graph with $\tau(\vec{H})=1$ and let
$\vec{G}$ be a directed acyclic graph with bounded maximum outdegree. There is
an algorithm that computes $\mathrm{Hom}_{\vec{H}}(\vec{G})$ in $O(n\log{n}))$
time.

###  4.6 Graph Products

We will use two different graph products in this work, they are standard
definitions but we show them here for completeness:

######  Definition 4.10.

(Categorical Product)[[NO12]] Given two graphs $G$ and $G^{\prime}$, we define
their categorical product $G\times G^{\prime}$ as follows:

$V_{G\times G^{\prime}}=V_{G}\times V_{G^{\prime}}$ $E_{G\times
G^{\prime}}=\\{(\langle u,u^{\prime}\rangle,\langle
v,v^{\prime}\rangle):(u,v)\in E_{G}\text{ and }(u^{\prime},v^{\prime})\in
E_{G^{\prime}}\\}$

######  Definition 4.11.

(Lexicographical Product)[[NO12]] Given two graphs $G$ and $G^{\prime}$, we
define their lexicographical product $G\bullet G^{\prime}$ as follows:

$V_{G\bullet G^{\prime}}=V_{G}\times V_{G^{\prime}}$ $E_{G\bullet
G^{\prime}}=\\{(\langle u,u^{\prime}\rangle,\langle
v,v^{\prime}\rangle):(u,v)\in E_{G}\text{ or }(u=v\text{ and
}(u^{\prime},v^{\prime})\in E_{G^{\prime}}\\}$

We can show that there is a direct relation between both products:

######  Fact 4.12.

For any constant $c>0$: $G\times K_{c}=G\bullet\bar{K_{c}}$

###### Proof.

First, from both definitions we have that the vertex sets are equivalent:
$V_{G\times K_{c}}=V_{G\bullet\bar{K_{c}}}=V_{G}\times V_{K_{c}}$.

We can also show that the edge sets are equivalent:

  * •

$E_{G\times K_{c}}=\\{(\langle u,u^{\prime}\rangle,\langle
v,v^{\prime}\rangle):(u,v)\in E_{G}\text{ and }(u^{\prime},v^{\prime})\in
E_{K_{c}}\\}=\\{(\langle u,u^{\prime}\rangle,\langle
v,v^{\prime}\rangle):(u,v)\in E_{G}\\}$.

  * •

$E_{G\bullet\bar{K_{c}}}=\\{(\langle u,u^{\prime}\rangle,\langle
v,v^{\prime}\rangle):(u,v)\in E_{G}\text{ or }(u=v\text{ and
}(u^{\prime},v^{\prime})\in E_{\bar{K_{c}}}\\}=\\{(\langle
u,u^{\prime}\rangle,\langle v,v^{\prime}\rangle):(u,v)\in E_{G}\\}$.

∎

###  4.7 Fraternity Function

Nešetřil and Ossona de Mendez introduced the notion of Fraternity Function in
[NO12]:

######  Definition 4.13.

(Fraternity Function) [Section 7.4 [NO12]] Let $\mathcal{V}$ be a finite set
and let $t$ be an integer. $t$-fraternity function is a function
$\omega:\mathcal{V}\times\mathcal{V}\to\mathbb{N}\cup\\{\infty\\}$ such that
for every $x,y\in\mathcal{V}$ one of $\omega(x,y)$ and $\omega(y,x)$ (at
least) is $\infty$ and such that for every $x\neq y\in\mathcal{V}$:

  * •

Either $\min(\omega(x,y),\omega(y,x))=1$

  * •

Or
$\min(\omega(x,y),\omega(y,x))=\min_{z\in\mathcal{V}\setminus\\{x,y\\}}\omega(z,x)+\omega(z,y)$
111All the definitions in the Sparsity book use indegree instead of outdegree,
which is more commonly used for subgraph counting using the degeneracy
orientation. We will use the outdegree orientation instead and hence some of
the definitions have been altered to reflect this.

  * •

Or $\min(\omega(x,y),\omega(y,x))>t$ and
$\min_{z\in\mathcal{V}\setminus\\{x,y\\}}\omega(z,x)+\omega(z,y)>t$.

Given a $t$-fraternity function $\omega$ we define the directed weighted graph
$\vec{G}^{\omega}=(V_{\vec{G}^{\omega}},E_{\vec{G}^{\omega}},W_{\vec{G}^{\omega}})$
as the graph with vertex set $V_{\vec{G}^{\omega}}=\mathcal{V}$ whose edges
are all the pairs $u,v\in\mathcal{V}$ such that $\omega(u,v)\leq t$ and for
every edge $(u,v)$ we have $W((u,v))=\omega(u,v)$. We also define the directed
graph
$\vec{G}^{\omega}_{i}=(V_{\vec{G}^{\omega}_{i}},E_{\vec{G}^{\omega}_{i}})$ as
the graph with vertex set $V_{\vec{G}^{\omega}}=\mathcal{V}$ whose edges are
all the pairs $u,v\in\mathcal{V}$ such that $\omega(u,v)=i$. We define
$\Delta^{+}_{i}(\omega)=\Delta^{+}(\vec{G}^{\omega}_{i})$.

We say that a directed weighted graph $\vec{G}$ forms a $t$-fraternity
function if there is a $t$-fraternity function $\omega$ such that
$\vec{G}=\vec{G}^{\omega}$. We call the fraternity function of $G$ to $\omega$
in such cases.

##  5 Proving the Upper Bound

In this section we state the theorem that shows the upper bound of the Main
Theorem and give a complete proof for it. In the following sections we will
proof the different lemmas that compose the proof:

######  Theorem 5.1.

For all $t>0\in\mathbb{N}$, let $G$ be an input graph with $n$ vertices, $m$
edges and bounded $\nabla_{(t-1)/2}(G)$. If $LICL(H)<3(t+1)$ then exists an
algorithm that computes $\mathrm{Hom}_{H}(G)$ in $O(n\log{n})$ time.

###### Proof.

Fix any $t>0$.

First, we need to compute the labeled version of $H$ and $G$, respectively
$H^{L}$ and $F$. This is because the fraternal extension procedures that we
will perform in the following step will not preserve the number of
homomorphisms if applied directly on $H$ and $G$ (see Fig. 4).

The constructions of these graphs are defined in §6. We can construct $H^{L}$
in $O(k)$ time and $F$ in $O(n)$ time (Claim 6.3). Additionally, we will show
that this transformations preserves both the LICL of the pattern graph and the
bounded grad conditions on the pattern and input graphs respectively:

  * •

$LICL(H^{L})=LICL(H)$

  * •

For any constant $i$, $\nabla_{i}(G)$ is bounded if and only if
$\nabla_{i}(F)$ is bounded. (Lemma 6.6).

We will also prove that the number of homomorphisms from $H$ to $G$ is equal
to the number of homomorphisms from $H^{L}$ to $F$ (Claim 6.4).

Then, we will compute both the optimal acyclic $t$-Fraternal extension of $F$,
${\vec{F}}^{(t)}$, and the collection of $t$-fraternal extensions of $H^{L}$.
We will formally define these concepts in §7. We will also show how to
efficiently construct ${\vec{F}}^{(t)}$:

######  Lemma 5.2.

Let $F$ be a graph with $O(n)$ vertices and bounded $\nabla_{(t-1)/2}$, we can
construct ${\vec{F}}^{(t)}$ in $O(t\cdot n)$ time.

Additionally, in the same section we prove that ${\vec{F}}^{(t)}$ will have
bounded maximum outdegree:

######  Lemma 5.3.

Let $F$ be a graph with $O(n)$ vertices and bounded $\nabla_{(t-1)/2}$, then
the directed graph ${\vec{F}}^{(t)}$ has bounded max outdegree.

$\Sigma(H,t)$ is independent on the input graph and will only depend on the
pattern graph $H$. Because $H$ is assumed to be constant sized we will be able
to compute $\Sigma(H,t)$ in $O(1)$ time.

We can now reduce our problem from computing $\mathrm{Hom}_{H^{L}}(F)$ to
computing $\mathrm{Hom}_{\vec{H}^{\prime}}({\vec{F}}^{(t)})$ for all
$\vec{H}^{\prime}\in\Sigma(H,t)$. In Subsection 7.4 we will show a direct
equivalence between both quantities, given by the following lemma:

######  Lemma 5.4.

$\mathrm{Hom}_{H^{L}}(F)=\sum_{\vec{H}^{\prime}\in\Sigma(H,t)}\mathrm{Hom}_{H^{\prime}}({\vec{F}}^{(t)})$

In §8 we introduce the concepts of hubset, hub-tree decomposition and hub-
treewidth. These concepts are a generalization of the source set, DAG-tree
decomposition and DAG-treewidth respectively for directed graphs that are not
acyclical. Using this new concepts, in §9 we show that there is a relation
between the hub-treewidth of the $t$-fraternal extensions of $H$ and the
$LICL$ of $H$, as given by the following lemma:

######  Lemma 5.5.

Let $H$ be a pattern graph with $LICL(H)<3(t+1)$, then for any $t$-fraternal
extension $\vec{H}^{\prime}\in\Sigma(H,t,$) we have that
$\tau(\vec{H}^{\prime})=1$.

Hence, because $H$ has an $LICL<3(t+1)$ we will have that the hub-treewidth of
all the graphs in $\Sigma(H,t)$ is $1$.

Finally, in §10 we show how to compute
$\mathrm{Hom}_{\vec{H}^{\prime}}({\vec{F}}^{(t)})$ for each
$\vec{H}^{\prime}\in\Sigma(H,t)$. By replacing the DAG-tree decomposition with
the hub-tree decomposition we are able to adapt Bressan’s algorithm [Bre21] to
work with labeled, weighted and directed graphs, giving the following lemma:

######  Lemma 5.6.

Let $\vec{G}$ be a directed weighted and labeled graph with $n$ vertices and
bounded outdegree and let $\vec{H}$ be a directed weighted and labeled graph
with $\tau(H)=1$. There exists an algorithm that computes
$\mathrm{Hom}_{\vec{H}}(\vec{G})$ in $O(n\log n)$ time.

Hence, we can compute $\mathrm{Hom}_{\vec{H}^{\prime}}({\vec{G}}^{(t)})$ in
linear time for each graph $\vec{H}^{\prime}\in\Sigma(H,t)$, as from Lemma 5.5
we have that $\tau(\vec{H}^{\prime})=1$ and from Lemma 5.3 we have that
$\Delta^{+}({\vec{F}}^{(t)})$ is bounded. We can then aggregate the counts
using Lemma 5.4 to obtain the final homomorphism count. The whole process will
take $O(n\log{n})$ time.

∎

##  6 Labeled Graphs

As we mentioned in the introduction, we can not use the fraternal extensions
directly on $G$ and $H$. Fraternal extensions do not preserve the number of
homomorphisms (see Fig. 4). We define a pair of labeled graphs that can be
obtained directly from $H$ and $G$ in linear time. Every homomorphism of the
original graphs will translate into an injective homomorphism in the labeled
graphs. We then will be able to do fraternal extensions on the labeled graphs
while preserving the homomorphism count.

First, we define the labeled version of $H$, $H^{L}$ which basically is $H$
but with every vertex labeled to itself:

######  Definition 6.1.

$H^{L}$: Given a pattern graph $H=(V_{H},E_{H})$ we define the labeled graph
$H^{L}=(V_{H^{L}},E_{H^{L}},L_{H^{L}})$, where:

  * •

$V_{H^{L}}=V_{H}$

  * •

$E_{H^{L}}=E_{H}$

  * •

$L_{H^{L}}:V_{H^{L}}\to V_{H^{L}}$ is a labeling function such that $\forall
v\in V_{H^{L}},L_{H^{L}}(v)=v$.

Now we define the graph $F$, this graph is obtained using the categorical
product (Definition 4.10) of $H^{L}$ and $G$:

######  Definition 6.2.

$F$: Given a pattern graph $H=(V_{H},E_{H})$ and an input graph
$G=(V_{G},E_{G})$, we define the labeled graph $F=(V_{F},E_{F},L_{F})$ as
follows:

  * •

$V_{F}=V_{H\times G}$

  * •

$E_{F}=E_{H\times G}$

  * •

$L_{F}:V_{F}\to V_{H^{L}},\text{ where }\forall\langle u,v\rangle\in V_{F}\
L(\langle u,v\rangle)=u$

Constructing $H^{L}$ is trivial and takes constant time $O(k)$. We can
construct $F$ efficiently as in the following claim:

######  Claim 6.3.

$F$ has $O(n\cdot\kappa)$ vertices and $O(n\cdot\kappa\cdot k^{2})$, and can
be constructed in $O(n\cdot\kappa\cdot k^{2})$ time.

###### Proof.

We can construct the vertices and assign the labels in $O(n\cdot k)$ time. We
will have at most $n\cdot\kappa$ edges in $E_{G}$, and $k^{2}$ edges in
$E_{H}$, hence we will take at most $O(n\cdot\kappa\cdot k^{2})$ to generate
$E_{F}$. The total complexity will be $O(n\cdot\kappa\cdot k^{2})$. ∎

We can show that the number of homomorphisms from $H$ to $G$ is equivalent to
the number of homomorphisms from $H^{L}$ to $F$:

######  Claim 6.4.

$\mathrm{Hom}_{H}(G)=\mathrm{Hom}_{H^{L}}(F)$

###### Proof.

We show that there is a bijection between the homomorphisms from $H$ to $G$
and from $H^{L}$ to $F$:

  * •

Consider a homomorphism $\phi$ from $H$ to $G$, it will map the vertex $u$ to
$\phi(u)$, we can create a homomorphism $\phi^{\prime}$ from $H^{L}$ to $F$ by
mapping $u$ to the vertex $\langle u,\phi(u)\rangle$ in $V_{F}$ for all $u\in
V_{H}$. If there is an edge in $H$ between $u_{i},u_{j}$ we will have that
there is also an edge between $\phi(u_{i})$ and $\phi(u_{j})$ in $G$, that
implies by construction the existence of the arc $(\langle
u_{i},\phi(u_{i})\rangle,\langle u_{j},\phi(u_{j})\rangle)$ in $F$, and hence
$\phi^{\prime}$ will be a valid homomorphism.

  * •

Similarly, given a homomorphism $\phi^{\prime}$ from $H^{L}$ to $F$ we can
obtain a homomorphism $\phi$ from $H$ to $G$ by setting
$\phi(u)=v:\phi^{\prime}(u)=\langle u,v\rangle$. Again we need to show that
this is a valid homomorphism: let $u_{i},u_{j}$ be two vertices in $H$, we
have $\phi(u_{i})=v_{i}=v:\phi^{\prime}(u_{i})=\langle u_{i},v\rangle$ and
$\phi(u_{j})=v_{j}=v:\phi^{\prime}(u_{j})=\langle u_{j},v\rangle$. If there is
an edge in $H$ between $u_{i}$ and $u_{j}$ we will have that there is also an
edge between $\langle u_{i},v_{i}\rangle$ and $\langle u_{j},v_{j}\rangle$ in
$F$, by construction that is only possible if there was also an edge between
$v_{i}$ and $v_{j}$ in $G$ and hence $\phi$ preserves the edge.

∎

Therefore, we have proven that we can create these labeled graphs $H^{L}$ and
$F$ in linear time, and use them to count the homomorphisms instead. If we
look at $H^{L}$ we will have that $LICL(H^{L})=LICL(H)$ as the only difference
between these graphs are the labels, which do not influence the structure of
the graph. However, in order to be able to use these graphs we need to show a
similar property for the input graph $G$ and its labeled version $F$, in this
case, we need to be able to preserve the grad $\nabla$, at least by a
polynomial factor. In order to prove this we will use the following
proposition from [NO12]:

######  Proposition 6.5 (Prop. 4.6 [NO12]).

Let $G$ be a graph, let $p\geq 2$ be a positive integer and let $r$ be a half-
integer. Then

$\tilde{\nabla}_{r}(G\bullet
K_{p})\leq\max(2r(p-1)+1,p^{2})\tilde{\nabla}_{r}(G)+p-1$

We can now prove the following lemma:

######  Lemma 6.6.

Let $G$ be an input graph, and $H$ be a pattern graph with constant size $k$.
For any constant $i$, $\nabla_{i}(G)$ is bounded if and only if
$\nabla_{i}(F)$ is bounded.

###### Proof.

First, we have that $G\subseteq F$, hence $\nabla_{i}(G)<\nabla_{i}(F)$ and if
$\nabla_{i}(F)$ is bounded so will $\nabla_{i}(G)$. We show the other
direction: note that $F$ will be a subgraph of $G\bullet K_{k}$:

$F=G\times H\subseteq G\times K_{k}=G\bullet\bar{K}_{k}\subseteq G\bullet
K_{k}$

Where the second equality comes from Fact 4.12.

Lastly, using Prop. 6.5 we have that if $\tilde{\nabla}_{i}(G)$ is bounded so
will $\tilde{\nabla}_{i}(G\bullet K_{k})$, and hence so will
$\tilde{\nabla}_{i}(F)$. Combining this with Fact 4.6 we get that
$\nabla_{i}(F)$ will be bounded if $\nabla_{i}(G)$ is bounded. ∎

######  Corollary 6.7.

$G$ has bounded degeneracy if and only if $F$ has bounded degeneracy.

##  7 Fraternal Extensions

In this section we formally introduce our augmentation procedure and define
the concept of fraternal extensions and how to construct them efficiently. We
will also show some properties of the fraternal extensions and prove the
relation between the homomorphisms from $H$ to $G$ and the ones of their
fraternal extensions.

###  7.1 The Fraternal Extension Procedure

We start by formally defining the fraternal extension of a graph:

######  Definition 7.1.

(Fraternal Extension) Given a directed graph
$\vec{G}=(V_{\vec{G}},E_{\vec{G}})$ we say that the directed weighted graph
$\vec{G}^{\prime}=(V_{\vec{G^{\prime}}},E_{\vec{G^{\prime}}},W_{\vec{G^{\prime}}})$
is a $t$-fraternal extension of $\vec{G}$ if $\vec{G}^{\prime}$ forms a
$t$-fraternity function and $E_{\vec{G}}=\\{e\in
E_{\vec{G^{\prime}}}:W_{\vec{G^{\prime}}}(e)=1\\}$.

If $G$ is an undirected graph, we say that $\vec{G}^{\prime}$ is a
$t$-fraternal extension of $G$ if it is a $t$-fraternal extensions of some
orientation $\vec{G}$ of $G$. The orientations of $G$ with unit weights are
$1$-fraternal extensions of $G$.

Abusing notation, given a directed weighted graph $\vec{G}^{\prime}$ that
forms $t$-fraternity function we say that the directed weighted graph
$\vec{G}^{\prime\prime}$ is a $t^{\prime}$-fraternal extension of
$\vec{G}^{\prime}$ if $\vec{G}^{\prime\prime}$ forms a $t^{\prime}$-fraternity
function and $\forall
i\in(1,t),\vec{G}^{\prime}_{i}=\vec{G}^{\prime\prime}_{i}$.

Note that all these definitions can be extended to labeled graphs.

We can construct fraternal extensions of a graph efficiently using a recursive
procedure. The initial step is to give unit weights to every edge in the
graph, each orientation of the resultant graph will be a different fraternal
extension. Then, for $i\in[2,t]$, for every out-out wedge with combined weight
is $i$ we add an undirected arc connecting it endpoints with weight $i$. Each
orientation of the undirected edges will generate a distinct fraternal
extension. The orientation of the undirected edges in each step will be
different if we are performing this procedure on the pattern or on the input
graph, as we will see in following subsections. We summarize the extension
procedure in Alg. 1:

Input:
-Directed graph $\vec{G}$ (should be a $(t-1)$-fraternal extension)
-Integer $t$
Output:
-Set of edges $E^{t}$

1:Let $E^{t}=\emptyset$.

2:for each out-out wedge $(u,v,w)$ in $\vec{G}$ do

3: if $W_{\vec{G}}(v,u)+W_{\vec{G}}(v,w)=t$ and $(u,w)\notin E_{\vec{G}}$ and
$(w,u)\notin E_{\vec{G}}$ then

4: Add $(u,w)$ to $E^{t}$.

5: end if

6:end for

7:Return $E^{t}$

Algorithm 1 Extension($\vec{G}$,$t$)

We can prove that the fraternal extensions will connect the endpoints of out-
out wedges.

######  Claim 7.2.

If a graph $\vec{G}^{\prime}$ is a $t$-fraternal extension of a graph
$\vec{G}$, then for every out-out wedge $(u,v,w)$ in $\vec{G}$ with
$W_{\vec{G}}((v,u))+W_{\vec{G}}(v,w)\leq t$ we have that there is an edge
connecting $u$ and $w$ in $\vec{G}^{\prime}$ of weight at most $t$.

###### Proof.

If $\vec{G}^{\prime}$ is a $t$-fraternal extension of a graph $\vec{G}$ then
by the definition of fraternal extension we have that $\vec{G}^{\prime}$ must
form a $t$-fraternity function, thus there is a $t$-fraternity function
$\omega:\mathcal{V}\times\mathcal{V}\to\mathbb{N}\cup\\{\infty\\}$ such that
$\vec{G}^{\prime}=G^{\omega}$. Let $(u,v,w)$ be an out-out wedge in $\vec{G}$
with $W_{\vec{G}}((v,u))+W_{\vec{G}}(v,w)\leq t$.

Abusing notation we will refer with $u,v,w$ to the correspondent elements in
${\cal V}$. Because $\omega$ is a $t$-fraternity function we have by the
definition of fraternity function (Definition 4.13)that for $u$ and $w$,
either:

  * •

$\min(\omega(u,w),\omega(w,u))=1$, in which case there is an edge of weight
$1$ connecting the two vertices.

  * •

$\min(\omega(u,w),\omega(w,u))=\min_{z\in\mathcal{V}\setminus\\{u,w\\}}\omega(z,u)+\omega(z,w)$,
for $z=v$ we have
$\omega(z,u)+\omega(z,w)=W_{\vec{G}}((v,u))+W_{\vec{G}}(v,w)\leq t$, and hence
we have that there will be an edge of weight at most $t$ connecting $u$ to $w$
or $w$ to $u$.

  * •

$\min(\omega(x,y),\omega(y,x))>t$ and
$\min_{z\in\mathcal{V}\setminus\\{x,y\\}}\omega(z,x)+\omega(z,y)>t$, which is
not possible as for $z=v$ we have
$\omega(z,u)+\omega(z,w)=W_{\vec{G}}((v,u))+W_{\vec{G}}(v,w)\leq t$.

In all the cases we either reach to a contradiction or we prove the existence
of the edge, completing the proof. ∎

###  7.2 The Fraternal Extensions of $H$

In the case of the pattern graph $H$, we are interested in generating all the
possible $t$-fraternal extensions of its labeled version $H^{L}$ at an
specific depth $t$. We will use $\Sigma(H,t)$ to denote such collection of
graphs. We define it as follows:

######  Definition 7.3.

$\Sigma(H,t)$ Given a pattern graph $H$ We call $\Sigma(H,t)$ to the
collection of directed weighted and labeled graphs $\vec{H}^{\prime}$ such
that $\vec{H}^{\prime}$ is a $t$-fraternal extension of any acyclical
orientation of the labeled graph $H^{L}$.

Figure 6: An example of how the fraternal extensions of a graph $H$ are
generated, the figure is not showing all the possible fraternal extensions.
$\Sigma(H,1)$ corresponds to all the possible acyclical orientations of $H$.
$\Sigma(H,2)$ adds the graphs obtained by adding edges between out-out wedges
in the graphs of $\Sigma(H,1)$, this may generate some new out-out wedges that
will be connected by edges in the graphs in $\Sigma(H,3)$. Note that a graph
in $\Sigma(H,1)$ with no out-out wedges will also be part of $\Sigma(H,2)$ and
$\Sigma(H,3)$.

Note that $\Sigma(H,1)$ corresponds exactly with the collection of acyclical
orientations of $H$ (adding unit weights to the edges and trivial labels to
the vertices).

Let $\vec{H}_{i}$ be a $i$-fraternal extension of $H$. Abusing notation, we
will use $\Sigma(\vec{H}_{i},t)$ for $t>i$ to denote the set of $t$-fraternal
extensions $\vec{H}^{\prime}$ of $H$ such that $\vec{H}^{\prime}$ is also a
$t$-fraternal extension of $\vec{H}_{i}$.

Obtaining the collection of fraternal extensions of a graph can be seen as an
iterative process where we apply the extension procedure defined in Alg. 1 to
all the fraternal extensions of the previous layer and then consider all the
possible orientations of these new edges, this process is summarized in Alg.
2. Fig. 6 shows an example of this process applied to a simple pattern graph.

Input:
-Labeled Graph $H^{L}$
-Integer $t$
Output:
-$\Sigma(H,t)$

1:Set $\Sigma(H,1)=\emptyset$

2:for each acyclical orientation $\vec{H}$ of $H^{L}$ do

3: Add $\vec{H}$ to $\Sigma(H,1)$ with unit weights.

4:end for

5:for $i\in[2,t]$ do

6: Set $\Sigma(H,i)=\emptyset$

7: for $\vec{H}\in\Sigma(H,i-1)$ do

8: Let $E^{i}=$ Extension($\vec{H},i)$

9: for each orientation $\vec{E}^{i}$ of the edges $E^{i}$ with weights $i$ do

10: Add $\vec{H}\cup\vec{E}^{i}$ to $\Sigma(H,i)$

11: end for

12: end for

13:end for

14:Return $\Sigma(H,t)$

Algorithm 2 ComputeExtensions($H^{L}$, $t$)

###  7.3 The Fraternal Extensions of $F$

We now formally define the optimal acyclic $t$-fraternal extension of $F$:

######  Definition 7.4.

(Optimal Acyclic $t$-Fraternal Extension ${\vec{F}}^{(t)}$) Given a graph $F$
we use ${\vec{F}}^{(t)}$ to denote an optimal acyclic $t$-fraternal extension
of $F$. It is defined as follows:

  * •

${\vec{F}}^{(t)}$ is a $t$-fraternal extension of $F$.

  * •

For every $i\in[1,t]$ we have that the edges ${{\vec{F}}^{(t)}}_{i}$ are
oriented acyclically following the degeneracy orientation of the edges with
weight $i$.

Note that for a graph $F$ there are multiple graphs that will follows those
properties, as the degeneracy orientation of a set of undirected edges might
not be unique. We can select any arbitrary degeneracy orientation whenever it
is not unique.

We can show that there is a strong relation between the $\nabla_{(t-1)/2}$ of
a graph $F$ and the maximum outdegree of any of its optimal acyclic
$t$-fraternal extensions:

See 5.3

###### Proof.

We prove by induction on $t$:

When $t=1$, ${\vec{F}}^{(1)}$ corresponds with the degeneracy orientation of
$F$. Because $F$ has bounded $\nabla_{(t-1)/2}$, we get that it also has
bounded $\nabla_{0}$ and hence, bounded degeneracy. Therefore, the degeneracy
orientation of $F$ will have bounded outdegree $\Delta^{+}({\vec{F}}^{(1)})$.

Now, for the inductive step, assume that for any $k<t$,
$\Delta^{+}({\vec{F}}^{(k)})$ is bounded. We prove that
$\Delta^{+}({\vec{F}}^{(k+1)})$ will also be bounded. First, we bring the
following lemma from [NO12]:

######  Lemma 7.5 (Lemma 7.6 in [NO12]).

Let $\mathcal{V}$ be a finite set, let $k\geq 1$ be an integer, let $\omega$
be a $k$-fraternity function and let $F=G_{1}^{\omega}$.

There exists a $(k+1)$-fraternity function $\omega^{\prime}$ such that:

$\forall(x,y)\in\mathcal{V}^{2},\omega(x,y)\leq
k\Longrightarrow\omega^{\prime}(x,y)=\omega(x,y)$
$\Delta^{+}_{k+1}(\omega^{\prime})\leq\tilde{\nabla}_{k/2}(F\bullet\overline{K}_{1+N_{\omega}(k+1)})$

Here $N_{\omega}(k+1)$ is a real valued function defined in section 7.4 of
[NO12] and its value is polynomial in
$\Delta_{1}^{+}(\omega)+,\ldots,\Delta_{k}^{+}(\omega)$.

Let $\omega_{k}$ be the fraternity function of ${\vec{F}}^{(k)}$. By our
assumption $\Delta^{+}({\vec{F}}^{(k)})$ is bounded, hence
$\Delta_{1}^{+}(\omega)+,\ldots,\Delta_{k}^{+}(\omega)$ will also be bounded
and so will $N=N_{\omega}(k+1)$. Applying Lemma 7.5 we know that there exists
a function $\omega^{\prime}$ such that
$\forall(x,y)\in\mathcal{V}^{2},\omega_{k}(x,y)\leq
k\Longrightarrow\omega^{\prime}(x,y)=\omega_{k}(x,y)$ and
$\Delta^{+}_{k+1}(\omega^{\prime})\leq\tilde{\nabla}_{k/2}(F\bullet\overline{K}_{1+N})$.

In other words, there exists a $k+1$-fraternal extension
$\vec{F}^{\prime}=G^{\omega^{\prime}}$ of $F$ such that its outdegree is at
most $\tilde{\nabla}_{k/2}(F\bullet\overline{K}_{1+N_{\omega}(k+1)})$. We must
show now that $\tilde{\nabla}_{k/2}(F\bullet\overline{K}_{1+N_{\omega}(k+1)})$
is bounded:

Recall that $N=N_{\omega}(k+1)$ is bounded. We have that $k<t$ hence
$k/2\leq(t-1)/2$ and $\nabla_{k/2}(F)\leq\nabla_{(t-1)/2}(F)$. Therefore,
because $F$ has bounded $\nabla_{(t-1)/2}$, it will also have bounded
$\nabla_{k/2}$. Now, applying Prop. 6.5 we get that
$\tilde{\nabla}_{k/2}(F\bullet\overline{K}_{1+N})$ will also be bounded as $N$
is a constant, and we get that:

$\displaystyle\Delta^{+}(\vec{F}^{\prime})_{k+1}=\Delta^{+}(G^{\omega^{\prime}})_{k+1}=\Delta^{+}_{k+1}\leq\tilde{\nabla}_{k/2}(F\bullet\overline{K}_{1+N})$

Therefore $\Delta^{+}(\vec{F}^{\prime})_{k+1}$ will be bounded.

However is possible that $\omega^{\prime}$ is orienting the edges of the $k+1$
layer in an orientation that is not acyclical, we can show that the max
outdegree of the degeneracy orientation is as most a factor of $2$ with
respect to the minimum max out degree of all cyclical orientations:

######  Claim 7.6.

Given an undirected graph $G$, let $\vec{G}^{*}$ be the orientation of $G$
with minimal $\Delta^{+}$ and let $\vec{G}^{\kappa}$ be the degeneracy
orientation of $G$:

$\Delta^{+}(G^{\kappa})\leq 2\Delta^{+}(G^{*})$

###### Proof.

$\Delta^{+}(\vec{G}^{\kappa})$ is equal to the degeneracy $\kappa$ of $G$.
There exists a subgraph $G^{\prime}$ in $G$ such that has minimum degree
$\kappa=\Delta^{+}(\vec{G}^{\kappa})$. Let $n^{\prime}$ be the number of
vertices in $G^{\prime}$ and $m^{\prime}$ the number of edges. We will have
that $m^{\prime}\geq\frac{n^{\prime}\cdot\Delta^{+}(\vec{G}^{\kappa})}{2}$.

If we divide all the $m^{\prime}$ edges equally so that the maximum outdegree
in $G^{\prime}$ is minimized we will have that every vertex has an outdegree
of at least $\frac{\Delta^{+}(\vec{G}^{\kappa})}{2}$. Hence any orientation of
the edges of $G^{\prime}$ will have an outdegree of at least
$\frac{\Delta^{+}(\vec{G}^{\kappa})}{2}$. Therefore,
$\Delta^{+}(\vec{G}^{*})\geq\frac{\Delta^{+}(\vec{G}^{\kappa})}{2}$. ∎

Therefore $\Delta^{+}_{k+1}({\vec{F}}^{(k+1)})\leq
2\Delta^{+}(\vec{F}^{\prime})_{k+1}$, and hence, it is bounded. Because for
all the other layers ${\vec{F}}^{(k)}$ and ${\vec{F}}^{(k+1)}$ are identical
and ${\vec{F}}^{(k)}$ has bounded outdegree, we get that
$\Delta^{+}({\vec{F}}^{(k+1)})$ is bounded.

∎

Additionally, If $F$ belongs to the class of graphs with bounded rank
$(t-1)/2$ grad. we can then compute ${\vec{F}}^{(t)}$ efficiently. The process
is summarized in Alg. 3, and basically consist of perform multiple iterations
of the extension procedure, orienting the edges by the degeneracy orientation
each time. We get the following lemma:

See 5.2

###### Proof.

First, because $F$ has bounded $\nabla_{(t-1)/2}$ it will also have bounded
degeneracy $\kappa$. We can then construct ${\vec{F}}^{(1)}$ by orienting $F$
acyclically using the degeneracy orientation, by Fact 4.2 this will take
linear time on the number of vertices and edges of $F$, which is still $O(n)$.

By Lemma 7.5 we will have that for all $k\leq t$ the graph ${\vec{F}}^{(k)}$
has bounded $\Delta^{+}$. We show an inductive process where given
${\vec{F}}^{(k)}$ we can compute ${\vec{F}}^{(k+1)}$ in linear time:

  * •

First, compute all the out-out wedges of ${\vec{F}}^{(k)}$. This can be done
in linear time as the outdegree of every vertex is bounded. The number of out-
out wedges will also be linear in $n$.

  * •

For every out-out wedge $(u,v,w)$, if the sum of the weights of the two edges
$(v,u)$ and $(v,w)$ is $k+1$ then create an edge connecting $(u,w)$ with
weight $k+1$. This process takes linear time in the number of out-out wedges,
which is again, linear in $n$. And there will be at most $O(n)$ edges in the
$k+1$ layer.

  * •

Finally, orient the newly created edges using the degeneracy orientation when
considering only the new edges. This again can be done in $O(n)$ time.

We complete the proof by showing that the resultant graph $\vec{F}^{\prime}$
is a valid ${\vec{F}}^{(k+1)}$. First, we can see that every layer in the
graph is oriented by the degeneracy orientation. That was true for the layer
$1$ to $k$ as we started our construction with ${\vec{F}}^{(k)}$ and we
haven’t added any additional edge with a weight $\leq k$. It is also true for
the $k+1$ layer as the last step of our construction orients the layer using
the degeneracy orientation.

Now we just need to show that $\vec{F}^{\prime}$ is a $k+1$-fraternal
extension of $F$. Let ${\cal V}=V_{\vec{F}^{\prime}}$ and $\omega:{\cal
V}\times{\cal V}\to\mathbb{N}$ be a function such that
$G^{\omega}=\vec{F}^{\prime}$. We must show that $\omega$ forms a
$k+1$-fraternity function. We prove by contradiction, if $\omega$ is not a
$k+1$ fraternity function, then by Definition 4.13 we have that there must
exist a pair of vertices in $V_{\vec{F}^{\prime}}$ such that the equivalent
nodes $u,v$ in ${\cal V}$ do not meet any of the following conditions:

  1. 1.

$\min(\omega(u,v),\omega(v,u))=1$

  2. 2.

$\min(\omega(u,v),\omega(v,u))=\min_{w\in\mathcal{V}\setminus\\{u,v\\}}\omega(w,u)+\omega(w,v)$

  3. 3.

$\min(\omega(u,v),\omega(v,u))>k+1$ and
$\min_{w\in\mathcal{V}\setminus\\{u,v\\}}\omega(w,u)+\omega(w,v)>k+1$.

If $u$ and $v$ do not meet the first condition then we have that
$\min(\omega(u,v),\omega(v,u))>1$ (recall that in a fraternity function a
missing edge is considered as $\infty$). If
$\min(\omega(u,v),\omega(v,u))<k+1$ then $u,v$ was an edge in
${\vec{F}}^{(k)}$ which implies that it will meet the second condition, as
${\vec{F}}^{(k)}$ was a valid $k$-fraternity extension. Hence, we have that
$\min(\omega(u,v),\omega(v,u))$ is either $k+1$ or $>k+1$:

  * •

In the first case $\min(\omega(u,v),\omega(v,u))=k+1$: because the second
condition is not true we will have that
$\min_{w\in\mathcal{V}\setminus\\{u,v\\}}\omega(w,u)+\omega(w,v)\neq k+1$. If
it is greater than $k+1$ then our procedure would not have generated an edge
connecting $u,v$ with weight $k+1$. Otherwise we have that is lower than $k+1$
we have that $\min_{w\in\mathcal{V}\setminus\\{u,v\\}}\leq k$, but then in
${\vec{F}}^{(t)}$ we will have an edge connecting $u$ and $v$ with weight $k$
or it would not be a valid fraternal extension. Both cases reach to a
contradiction.

  * •

In the second case we have that $\min(\omega(u,v),\omega(v,u))>k+1$: Then
because the third condition is false, we will have that
$\min_{w\in\mathcal{V}\setminus\\{u,v\\}}\omega(w,u)+\omega(w,v)\leq k+1$. But
in that case an out-out wedge with weight at most $k+1$ would connect $u$ and
$v$, and hence our procedure would have generated an edge connecting $u$ and
$v$ with weight at most $k+1$, again reaching a contradiction.

∎

Input:
-Labeled Graph $F$
-Integer $t$
Output:
-${\vec{F}}^{(t)}$

1:Let ${\vec{F}}^{(1)}$ be the degeneracy orientation of $F$ with unit
weights.

2:for $k\in[2,t]$ do

3: Let $E^{i}=$ Extension(${\vec{F}}^{(i-1)},i)$

4: Let $\vec{E}^{i}$ be the degeneracy orientation of the edges in $E^{i}$
with weight $i$.

5: Set ${\vec{F}}^{(i)}={\vec{F}}^{(i-1)}\cup\vec{E}^{i}$

6:end for

7:Return ${\vec{F}}^{(t)}$

Algorithm 3 CompOptimalExtension($F$,$t$)

###  7.4 Equivalence of Homomorphisms

In this section we prove the equivalence between the homomorphisms of the
original graphs and the fraternal extensions. This is given by Lemma 5.4, that
we restate:

See 5.4

###### Proof.

Let $\Phi(H^{L},F)$ be the set of homomorphisms from $H^{L}$ to $F$. For every
$\vec{H}^{\prime}\in\Sigma(H,t)$, let $\Phi(\vec{H}^{\prime},{\vec{F}}^{(t)})$
be the set of homomorphisms from $\vec{H}^{\prime}$ to ${\vec{F}}^{(t)}$. We
can see that each of these sets are disjoint:

######  Claim 7.7.

Let $\vec{H}^{\prime},\vec{H}^{\prime\prime}\in\Sigma(H,t)$ be two distinct
$t$-fraternal extensions of $H$:

$\displaystyle\Phi(\vec{H}^{\prime},{\vec{F}}^{(t)})\cap\Phi(\vec{H}^{\prime\prime},{\vec{F}}^{(t)})=\emptyset.$

###### Proof.

First, we show that if $\vec{H}^{\prime}$ and $\vec{H}^{\prime\prime}$ are
distinct $t$-fraternal extensions of $H$ then there must exist an edge $e\in
E_{\vec{H}^{\prime}}$ such that it is reversed in $\vec{H}^{\prime\prime}$. We
prove it by contradiction: Assume there is no such edge, we show that then
$\vec{H}^{\prime}=\vec{H}^{\prime\prime}$. We do induction in the depth of the
fraternal extensions:

  * •

For the base case, $\vec{H^{\prime}}$ and $\vec{H}^{\prime\prime}$ are both
$1$-fraternal extensions and therefore they will correspond to different
orientations of the edges in $H$, if they don’t differ in any edge then
$\vec{H}^{\prime}$ and $\vec{H}^{\prime\prime}$ will correspond to the exact
same orientation.

  * •

For the inductive step, assume for some $k<t$ that if there is no reversed
edge in two $k$-fraternal extensions
$\vec{H}^{\prime}$,$\vec{H}^{\prime\prime}$ of $H$, then
$\vec{H}^{\prime}=\vec{H}^{\prime\prime}$. We show that same holds for
$k+1$-fraternal extensions. By the assumption we know that two $k$-fraternal
extensions that do not differ in any edge will correspond to the same graph.
Hence, two $k+1$-fraternal extension
$\vec{H}^{\prime},\vec{H}^{\prime\prime}\in\Sigma(H,k+1)$ will have the same
edges (with the exact same orientations) up to the layer $k$, and therefore
the edges in the layer $k+1$ must be the same. Because we are assuming that
there are not reversed edges, they will also have the same orientation.
Therefore $\vec{H}^{\prime}=\vec{H}^{\prime\prime}$.

Hence, there exists an edge $e$ that have different orientations in
$\vec{H}^{\prime}$ and $\vec{H}^{\prime\prime}$. Let $u,v$ be the endpoints of
the edge $e$, the arc $(u,v)$ belongs to $\vec{H}^{\prime}$ and the arc
$(v,u)$ to $\vec{H}^{\prime\prime}$. We show that no homomorphism $\phi$ can
be both in $\Phi(\vec{H}^{\prime},{\vec{F}}^{(t)})$ and in
$\Phi(\vec{H}^{\prime\prime},{\vec{F}}^{(t)})$. Consider the vertices
$\phi(u)$ and $\phi(v)$ of ${\vec{F}}^{(t)}$, we can have either an arc from
$\phi(u)$ to $\phi(v)$, from $\phi(v)$ to $\phi(u)$, or none. In order for
$\phi$ to be a valid homomorphism of $\vec{H}^{\prime}$, we will need the
directed arc $(\phi(u),\phi(v))$ to be in ${\vec{F}}^{(t)}$, similarly for
$\vec{H}^{\prime\prime}$ we will need the directed arc $(\phi(v),\phi(u))$ to
be in ${\vec{F}}^{(t)}$. A fraternal extension can not contain two opposite
edges connecting the same two vertices. Therefore $\phi$ can not be a
homomorphism of $\vec{H}^{\prime}$ and $\vec{H}^{\prime\prime}$ at the same
time. ∎

Now we just need to show that:

$\displaystyle\Phi(H^{L},F)=\bigcup_{\vec{H}^{\prime}\in\Sigma(H,t)}\Phi(\vec{H}^{\prime},{\vec{F}}^{(t)})$

We start by proving that for every $\vec{H}^{\prime}\in\Sigma(H,t)$, if $\phi$
is a homomorphism from $\vec{H}^{\prime}$ to ${\vec{F}}^{(t)}$ then it will
also be a valid homomorphism from $H^{L}$ to $F$: Let
$\vec{H}^{\prime}\in\Sigma(H,t)$ be a $t$-fraternal extension of $H$ and
$\phi$ a homomorphism from $\vec{H}^{\prime}$ to ${\vec{F}}^{(t)}$, $\phi$
must be an injective mapping, hence every vertex in $\vec{H}^{\prime}$ is
mapped to a distinct vertex in ${\vec{F}}^{(t)}$.

We show that $\phi$ is also a valid homomorphism from $H^{L}$ to $F$, consider
the edge $(u,v)\in H^{L}$, we must show that the edge $(\phi(u),\phi(v))$ is
present in $F$. Because $\vec{H}^{\prime}$ is a fraternal extension of
$H^{L}$, we will have that they share the edges of weight $1$, hence either
the arc $(u,v)$ or the arc $(v,u)$ will be present in $\vec{H}^{\prime}$ (we
can assume without loss of generality that it is oriented from $u$ to $v$)
with unit weight $W_{\vec{H}^{\prime}}((u,v))=1$. Because $\phi$ is a
homomorphism from $\vec{H}^{\prime}$ to ${\vec{F}}^{(t)}$ we will have that
the edge $(\phi(u),\phi(v))$ must be present in ${\vec{F}}^{(t)}$ with weight
$W_{{\vec{F}}^{(t)}}((u,v))=W_{\vec{H}^{\prime}}((u,v))=1$. For
${\vec{F}}^{(t)}$ to have an edge with weight $1$, such edge must be also in
$F$, and hence $(\phi(u),\phi(v))$ is present in $E_{F}$.

Now we prove that if $\phi$ is a homomorphism from $H^{L}$ to $F$ then there
exists a fraternal extension $\vec{H}^{\prime}\in\Sigma(H,t)$ such that $\phi$
is a valid homomorphism from $\vec{H}^{\prime}$ to ${\vec{F}}^{(t)}$: Let
$\phi$ be a homomorphism from $H^{L}$ to $F$, we show that we can construct a
$t$-fraternal extension of $H^{L}$ such that $\phi$ is a valid homomorphism
from it to ${\vec{F}}^{(t)}$. We use induction on $t$:

  * •

For the base case $k=1$, we can orient every edge $(u,v)$ in $H^{L}$ so it
matches the orientation of the edge $(\phi(u),\phi(v))$ in ${\vec{F}}^{(1)}$.
This orientation will be acyclic and therefore the resultant graph will be in
$\Sigma(H,1,$).

  * •

For the inductive step, we assume that for $k<t$ exists a $k$-fraternal
extension $\vec{H}^{k}$ of $H$ where $\phi$ is a valid homomorphism from
$\vec{H}^{k}$ to ${\vec{F}}^{(k)}$. We prove that it also holds for $k+1$:
First, let $\vec{H}^{\prime}$ be a $k+1$-fraternal extension of $\vec{H}^{k}$,
any edge $(u,v)$ in $\vec{H}^{\prime}$ with $W_{\vec{H}^{\prime}}((u,v))<t$
must have a correspondent edge $(\phi(u),\phi(v))$ in ${\vec{F}}^{(k)}$ and
hence in ${\vec{F}}^{(k+1)}$ with
$W_{{\vec{F}}^{(k+1)}}((\phi(u),\phi(v)))<W_{\vec{H}^{\prime}}((u,v))$.

Hence we only need to verify that the edges $e$ in $\vec{H}^{\prime}$ with
$W_{\vec{H}^{\prime}}(e)=k+1$ are also present in ${\vec{F}}^{(t)}$. Consider
the edge $e=(u,v)$ in $\vec{H}^{\prime}$ with $W_{\vec{H}^{\prime}}(e)=k+1$,
we need to show that ${\vec{F}}^{(t)}$ contains either $(\phi(u),\phi(v))$ or
$(\phi(v),\phi(u))$ as the edges in the last layer of $\vec{H}^{\prime}$ can
be oriented arbitrarily and still will be a valid $k+1$-fraternal extension of
$\vec{H}^{k}$. If such edge $e$ exists, then there must exist a vertex $w$ in
$\vec{H}^{\prime}$ such that there is an out-out wedge $(u,w,v)$ in
$\vec{H}^{k}$ with total weight $k+1$, by the assumption, we will have that
there is an out-out wedge $(\phi(u),\phi(w),\phi(v))$ in ${\vec{F}}^{(k)}$
with total weight $\leq k+1$. Hence ${\vec{F}}^{(t)}$ must include either
$(\phi(u),\phi(v))$ or $(\phi(v),\phi(u))$ with weight $\leq k+1$.

∎

##  8 The Hub-Set

As we mentioned before, the fraternal extensions of an acyclic graph might no
longer be acyclic. Bressan’s algorithm for counting homomorphism requires of
directed acyclic graphs, as it relays on the definitions of DAG-tree
decomposition and DAG-treewidth. We will generalize these definitions and
extend Bressan’s algorithm to directed graphs that are not necessarily
acyclic. For that purpose we introduce the concept of hubset of a directed
graph:

######  Definition 8.1.

Let $\vec{H}$ be a directed graph, a hubset of $\vec{H}$ is any subset of
vertices $\mathcal{S}\subseteq V_{\vec{H}}$ such that:

  * •

For each pair $s,s^{\prime}\in\mathcal{S}$ with $s\neq s^{\prime}$ there is no
directed path connecting $s$ to $s^{\prime}$ (or vice versa).

  * •

For each vertex $v\in V_{\vec{H}}\setminus\mathcal{S}$, there exists a vertex
$s\in\mathcal{S}$ such that there is a directed path connecting $s$ to $v$.

We will use $\mathcal{S}(\vec{H})$ to denote any hubset of $\vec{H}$. Note
that when $\vec{H}$ is acyclic the hubset of $\vec{H}$ is unique and
corresponds exactly with the source set. Furthermore, this applies to any
fraternal extension of a DAG as we can see in the following claim:

######  Claim 8.2.

Let $\vec{H}^{\prime}$ be a fraternal extension of the DAG $\vec{H}$.
$\vec{H}$ has an unique hubset and $\mathcal{S}(\vec{H}^{\prime})=S(\vec{H})$.

###### Proof.

Note that the edges of $\vec{H}$ are a subset of the edges of
$\vec{H}^{\prime}$. Hence, the second condition for the hubset is
automatically satisfied as every vertex in $\vec{H}$ is reachable from at
least one source in $S(\vec{H})$. For the first condition suffices to observe
that the indegree of any of the sources will be $0$ in all the fraternal
extensions of $\vec{H}$. We can prove it by contradiction, assume that there
is a fraternal extension that adds an edge incident to the source $s\in
S(\vec{H})$, then we will have that $s$ was one of the endpoints of an out-out
wedge. That is not possible as $s$ is a source and hence its initial indegree
in $\vec{H}$ was $0$.

Now we prove that the hubset is unique, note that by the previous argument
every source of $\vec{H}$ will still be source in $\vec{H}^{\prime}$. Hence
all the sources must be included in the hubset in order to satisfy the second
condition. Adding any additional vertex in the hubset is also not possible, as
all the vertices are reachable from at least one source and we would violate
the first condition. ∎

Note that every graph $\Sigma(H,1)$ is a DAG, therefore the previous claim
will apply to every graph in $\Sigma(H,t)$ for every $t>0$.

We can now define a new type of decomposition of a graph based on the hubset.
This new decomposition is just a generalization of Bressan’s DAG-tree
decomposition for directed graphs:

######  Definition 8.3 (hub-tree decomposition).

Let $\vec{H}$ be a directed graph with hubset
$\mathcal{S}=\mathcal{S}(\vec{H})$. A hub-tree decompositionof $\vec{H}$ is a
rooted tree ${\cal T}=(\mathcal{B},{\cal E})$ with the following properties:

  1. 1.

Each node $B\in\mathcal{B}$ is a subset of $\mathcal{S}$ of $\vec{H}$,
$B\subseteq\mathcal{S}$.

  2. 2.

$\bigcup_{B\in\mathcal{B}}B=\mathcal{S}$.

  3. 3.

For all $B,B_{1},B_{2}\in\mathcal{B}$, if $B$ is on the unique path between
$B_{1}$ and $B_{2}$ in $\mathcal{T}$, then we have $Reach_{\vec{H}}(B_{1})\cap
Reach_{\vec{H}}(B_{2})\subseteq Reach_{\vec{H}}(B)$.

We similarly define the hub-treewidth of a graph:

######  Definition 8.4 (hub-treewidth($\tau$)).

The hub-treewidth of a hub-tree decomposition ${\cal T}=(\mathcal{B},{\cal
E})$ is defined as the maximum size over all the nodes of ${\cal T}$:

$\displaystyle\tau({\cal T})=\max_{B\in\mathcal{B}}|B|$

We also use $\tau(\vec{H})$ to refer to the hub-treewidth of the directed
graph $\vec{H}$, which is the minimum $\tau({\cal T})$ over all possible hub-
tree decomposition of $\vec{H}$.

Note that when $\vec{H}$ is acyclic the definitions for DAG-tree decomposition
and hub-tree decomposition are equivalent. Similarly we will have that the
DAG-treewidth and hub-treewidth are the same, that is why we will refer to
both of them using $\tau$.

##  9 The hub-treewidth of fraternal extensions and the LICL

As we can see in Fig. 5, the fraternal extensions do not necessarily reduce
the $LICL$ of the pattern graphs, as new cycles can be formed with the new
edges in the extensions. However, there is a clear relation between the $LICL$
of the original graph and the hub-treewidth of the fraternal extensions. We
will be proving such relation in this section, given by the following lemma:

See 5.5

###  9.1 Main Technical Lemma

In this subsection we prove the main technical lemma of this paper, which will
allow us to prove the relation between fraternal extensions and dag-treewidth.
First we will define a long out-out wedge:

######  Definition 9.1.

A long out-out wedge is a graph form by the union of two directed paths of any
length as the result of combining their sources. Fig. 7 shows an example of a
long out-out wedge.

We now prove the following claims that will be used in the main lemma of this
subsection:

######  Claim 9.2.

Let $u,v$ be the endpoints of a long out-out wedge with total weight $w$ and
$l$ edges in some fraternal extension $\vec{H}_{i}$ of $H$, then for all
$t\geq w$, for all $\vec{H}^{\prime}\in\Sigma(\vec{H}_{i},t)$ there is a
direct path connecting either $u$ to $v$ or $v$ to $u$ using only the vertices
in the long out-out wedge.

###### Proof.

We can prove by induction on the number of edges of the long out-out wedge:

The base case is when $l=2$, this is simply a standard out-out wedge with
where the two edges have a combined weight of $w$. By Claim 7.2 we have that
any $t$-fraternal extension of $\vec{H}_{i}$ at depth $t\geq w$ will add an
edge connecting $u,v$ if it was not already present. Hence, we will either
have a path from $u$ to $v$ or $v$ to $u$.

Now we show the inductive step: Assume that the claim holds for $l=k$, we will
prove that it also holds for $l=k+1$.

Let $s$ be the source of the long out-out wedge with length $k+1$, $s$ will be
forming a normal out-out wedge with a vertex $u^{\prime}$ in the $s-u$ path
and a vertex $v^{\prime}$ in the $s-v$ path, both $(s,u^{\prime})$ and
$(s,v^{\prime})$ edges will have a combined weight strictly less than $w$,
thus for some $t^{\prime}<w$ by Claim 7.2 any fraternal extension of $H_{i}$
at level $t^{\prime}$ will have an edge $(u^{\prime},v^{\prime})$ (we can
assume without loss of generality that it will go from $u^{\prime}$ to
$v^{\prime}$).

If $u^{\prime}=u$ then we actually a directed path from $u$ to $v$, otherwise,
we have a long out-out wedge where the total weight is still at most $w$, but
with the source at $u^{\prime}$, with one less edge, hence $l=k$. Using the
assumption of the inductive step we know that there will be a path either from
$u$ to $v$ or from $v$ to $u$ in the $t$-fraternal extension.

∎

In Fig. 7 we can see an example of the long out-out wedge construction.

Figure 7: An example of connectivity between the end-points of a long out-out
wedge, we can see how $u^{\prime}$ becomes the source of a new long out-out
wedge after adding the edge of weight $3$. When adding the edge of weight $4$
in the right picture we end up with a direct path between $u$ and $v$.

We now prove the following:

######  Claim 9.3.

Let $P$ be an induced undirected path of length $t$ from $u$ to $v$ in $H$,
then for any $t$-fraternal extension $\vec{H}\in\Sigma(H,t)$: There is an
undirected path $P^{\prime}$ connecting $u$ and $v$ (ignoring edge directions)
using only vertices in $P$ with total weight at most $t$, such that
$P^{\prime}$ either:

  * •

Case 1: Forms a direct path from $u$ to $v$.

  * •

Case 2: Forms a direct path from $v$ to $u$.

  * •

Case 3: Contains a vertex $s$ such that there is a direct path from both $u$
and $v$ to $s$ in $P^{\prime}$ (a long in-in wedge).

###### Proof.

We can prove by induction on $t$:

Our base case is when $t=1$, we have that $u$ and $v$ are connected by one
edge in $H$, in every orientation of $H$ we will have that either the edge
goes from $u$ to $v$ (Case 1) or from $v$ to $u$ (Case 2).

For the inductive step we assume that the claim holds for all $t\leq k$, we
will show that it also holds for $t=k+1$:

Let $u$ and $v$ be two vertices in $H$ inducing the path $P$ of length $k+1$.
Let $u^{\prime}$ be the vertex adjacent to $u$ in $P$, and let $e$ be the edge
connecting $u$ and $u^{\prime}$. Then $u^{\prime}$ and $v$ form an induced
path of length $k$ using the vertices of $P$.

Using the assumption of the inductive step, we have that for all the
$k$-fraternal extensions $\vec{H}_{k}\in\Sigma(H,k)$ we will have that there
is a path $P^{\prime\prime}$ connecting $u^{\prime}$ and $v$ (ignoring
directions) using only vertices in $P$ with total weight at most $k$,
following one of the three cases. We will prove that all the cases lead to the
construction of a path $P^{\prime}$ from $u$ to $v$ for all
$\vec{H}_{k+1}\in\Sigma(\vec{H}_{k},k+1)$ following one of the three
conditions:

  * •

Case 1: We have that $P^{\prime\prime}$ is a direct path from $u^{\prime}$ to
$v$ with weight at most $k$. We have two possibilities depending on the
orientation of $e$:

    1. (a)

$e$ is oriented from $u$ to $u^{\prime}$: then $e\cup P^{\prime\prime}$ forms
a direct path from $u$ to $v$ with total weight at most $k+1$.

    2. (b)

$e$ is oriented from $u^{\prime}$ to $u$: then, in $\vec{H}_{k}$, $e\cup
P^{\prime\prime}$ forms a long out-out wedge with the source at $u^{\prime}$
with at most $k+1$ edges and at most $k+1$ total weight. Hence by Claim 9.2 we
have that there will be a direct path in all
$\vec{H}_{k+1}\in\Sigma(\vec{H}_{k},k+1)$ from $u$ to $v$ or from $v$ to $u$.

  * •

Case 2: We have that $P^{\prime\prime}$ is a direct path from $v$ to
$u^{\prime}$ with weight at most $k$. We have two possibilities depending on
the orientation of $e$:

    1. (a)

$e$ is oriented from $u$ to $u^{\prime}$: then we have that $u^{\prime}$ is
reachable from both $u$ and $v$ in $\vec{H}_{k}$.

    2. (b)

$e$ is oriented from $u^{\prime}$ to $u$: then $e\cup P^{\prime\prime}$ forms
a direct path from $v$ to $u$ with total weight at most $k+1$.

  * •

Case 3: We have that $P^{\prime\prime}$ has a vertex $s$ such that there is a
direct path from both $u^{\prime}$ and $v$ to $s$ in $P^{\prime\prime}$. We
have two possibilities depending on the orientation of $e$:

    1. (a)

$e$ is oriented from $u$ to $u^{\prime}$: then we have a direct path from $u$
to $s$, and $e\cup P^{\prime\prime}$ form a long in-in wedge ending in $s$.

    2. (b)

$e$ is oriented from $u^{\prime}$ to $u$: then we can see how in
$\vec{H}_{k}$, $u$ and $s$ form a long out-out wedge in $e\cup
P^{\prime\prime}$ centered in $u^{\prime}$ with less than $k$ edges and less
than $k$ weight. Hence by Claim 9.2 we have that there will be a direct path
in all $\vec{H}_{k+1}\in\Sigma(\vec{H}_{k},k+1)$ from $u$ to $s$ or from $s$
to $u$. In the first case, $s$ will be reachable from both $u$ and $v$, and in
the second case we have a direct path from $v$ to $u$.

As we can see, every possibility lead to one of the three cases in the claim.
In Fig. 8 there is a depiction of all the cases.

Figure 8: The $6$ possible scenarios in the proof of Claim 9.3 depending on
the orientations of $e$ and $P^{\prime\prime}$. The red edges represent the
cases where a long out-out wedge appears, we know the endpoints of the long
out-out wedges will connect because of Claim 9.2

∎

Before presenting the main technical lemma, we bring the definition of Unique
reachability graph from [BPS21]. However this definition was created for
directed acyclical graphs as it uses the sources of the graph. We adapt it to
use the hubset instead:

######  Definition 9.4 (Unique reachability graph).

Let $\vec{H}$ be a directed graph with hubset
$\mathcal{S}=\mathcal{S}(\vec{H})$ and $\mathcal{S}_{p}\subseteq\mathcal{S}$
be a subset of the hubset. We define a unique reachability graph
$UR_{\mathcal{S}_{p}}(\mathcal{S}_{p},E_{\mathcal{S}_{p}})$ on the vertex set
$\mathcal{S}_{p}$, and the edge set $E_{\mathcal{S}_{p}}$ such that there
exists an edge $e=\\{s_{1},s_{2}\\}\in E_{\mathcal{S}_{p}}$, for
$s_{1},s_{2}\in\mathcal{S}_{p}$ if and only if the set
$(Reach_{\vec{H}}(s_{1})\cap Reach_{\vec{H}}(s_{2}))\setminus
Reach_{\vec{H}}(\mathcal{S}_{p}\setminus\\{s_{1},s_{2}\\})$ is non-empty.

We can now finally introduce the main technical lemma:

######  Lemma 9.5.

Given a pattern graph $H$, if $LICL(H)<3(t+1)$ then for any graph
$\vec{H}^{\prime}\in\Sigma(H,t)$ we have that $UR_{\vec{H}^{\prime}}$ is
acyclical.

###### Proof.

We prove a stronger statement, let the graph $\vec{H}^{\prime}\in\Sigma(H,t)$
be a $t$-fraternal extension of $H$. If $UR_{\vec{H}^{\prime}}$ contains a
cycle of length $l$, then $H$ will contain an induced cycle of length at least
$(t+1)\cdot l$.

Consider the subset ${\mathcal{S}}^{\prime}(\vec{H}^{\prime})$ of $l$ vertices
from the hubset $\mathcal{S}(\vec{H})$ forming the cycle in
$UR_{\vec{H}^{\prime}}$, we have
${\mathcal{S}}^{\prime}(\vec{H}^{\prime})\subseteq\mathcal{S}(\vec{H}^{\prime})$.
We can enumerate them as $s_{1},s_{2},\ldots,s_{l}$, where for $i\in[1,l]$ we
have that $s_{i}$ and $s_{i+1}$ (with $s_{l+1}=s_{1}$) share a edge in
$UR_{\vec{H}^{\prime}}$.

For each vertex $s_{i}\in{\mathcal{S}}^{\prime}(\vec{H}^{\prime})$, we define
$U(s_{j})$ as the subset of vertices of $\vec{H}^{\prime}$ that are reachable
by $s_{i}$ but are not reachable by any vertex in
${\mathcal{S}}^{\prime}(\vec{H}^{\prime})\setminus s_{i}$. Note that
$U(s_{i})$ is not empty as we will have $s_{i}\in U(s_{i})$. Also for
$s_{i}\neq s_{j}$ there can not be any edge in $H$ connecting any vertex in
$U(s_{i})$ to any vertex in $U(s_{j})$ or one of the vertices would be
reachable by at least $2$ vertices in
${\mathcal{S}}^{\prime}(\vec{H}^{\prime})$.

Similarly, for each pair of vertices
$s_{i},s_{j}\in{\mathcal{S}}^{\prime}(\vec{H}^{\prime})$, let $C(s_{i},s_{j})$
be the subset of vertices of $\vec{H}^{\prime}$ that is reachable by both
$s_{i}$ and $s_{j}$ but not by any other vertex in
${\mathcal{S}}^{\prime}(\vec{H}^{\prime})\setminus\\{s_{i},s_{j}\\}$. Note
that for $i\in[1,l]$ we will have that $C(s_{i},s_{i+1})$ is not empty, as
they share an edge in $UR_{\vec{H}^{\prime}}$. Again for $i\neq j$ there can
not be any edge in $H$ connecting any vertex in $C(s_{i},s_{i+1})$ with any
vertex in $C(s_{j},s_{j+1})$ or one of the vertices would be reachable by at
least $3$ vertices in ${\mathcal{S}}^{\prime}(\vec{H}^{\prime})$.

In Fig. 9 we show an example of the definitions of $U$ and $C$.

Figure 9: An example of a graph with three sources that will form the hubset.
The $U$ and $C$ regions for each source or pair of sources are highlighted.
This graph is $2$-fraternal extension where the Unique Reachability Graph will
have a cycle, we can see how the original graph (if we only consider edges
with weight $1$) contains an induced cycle of length at least $9$.

Let ${\cal
V}_{{\mathcal{S}}^{\prime}}=\bigcup_{i=1}^{l}U(s_{i})\cup\bigcup_{i=1}^{l}C(s_{i},s_{i+1})$.
We claim that there is an induced cycle of length $(t+1)\cdot l$ in the
induced subgraph of $H$ by ${\cal V}_{{\mathcal{S}}^{\prime}}$.

We define $A(s_{i})=C(s_{i-1},s_{i})\cup U(s_{i})\cup C(s_{i},s_{i+1})$, that
is, the portion of ${\cal V}_{{\mathcal{S}}^{\prime}}$ reachable by $s_{i}$.

Now we can show the following claim:

######  Claim 9.6.

For all $i\in[1,l]$, for all $u\in C(s_{i-1},s_{i})$ (with $s_{0}=s_{l}$) and
for all $w\in C(s_{i},s_{i+1})$ (with $s_{l+1}=s_{1}$), exists an induced path
in $H$ of length at least $t+1$ connecting $u$ and $w$ that only uses vertices
in $A(s_{i})$.

###### Proof.

Let $P$ be the shortest path in $H$ from $u$ to $w$ that only uses vertices in
$A(s_{i})$. Because this is a shortest path it will also be an induced path.
Such a path will always exists as there is a path from the vertex $s_{i}$ to
all the vertices in $A(s_{i})$ that only uses such vertices. We prove that it
will have length at least $t+1$:

Assume the opposite, then there is a path from $u$ to $w$ in $P$ that only
uses vertices in $A(s_{i})$ with at most $t$ edges. However by Claim 9.3 we
would have that in $\vec{H}^{\prime}$ there is a path $P^{\prime}\subseteq P$
where $P^{\prime}$ either:

  * •

Case 1: Is a direct path from $u$ to $w$, which would mean that $w$ is
reachable by three vertices of the hubset and hence not in $C(s_{i},s_{i+1})$.

  * •

Case 2: Is a direct path from $w$ to $u$, which would mean that $u$ is
reachable by three vertices of the hubset and hence not in $C(s_{i-1},s_{i})$.

  * •

Case 3: Has a vertex $s$ that is reachable from both $u$ and $w$, but in that
case $s$ would be reachable from three vertices of the hubset and it would not
be in ${\cal V}_{{\mathcal{S}}^{\prime}}$.

Hence we reach a contradiction in all the cases and therefore the shortest
path must have length at least $t+1$, concluding the proof of this claim.

∎

We can now select one vertex $u_{i}\in C(s_{i},s_{i+1})$ for each $i\in[1,l]$
such that the total length for all $i\in[1,l]$ of the paths connecting $u_{i}$
and $u_{i-1}$ using the vertices in $A(s_{i})$ is minimized. We have a total
of $l$ paths.

If there is a common vertex between two of the paths (ignoring the ends of the
paths) then setting that vertex as the end vertex would yield a shorter path,
hence we have that the $l$ paths only intersect in their ends, and thus,
combining them we obtain a cycle of length $l\cdot(t+1)$ (as each of the
individual paths have length $t+1$ by the previous claim).

Only left to show is that this cycle is actually an induced cycle: The paths
forming the cycle are all induced, so suffices to show that there are no edges
connecting two different paths. There are no edges connecting two different
$U(s_{i})$ or two different $C(s_{i},s_{i+1})$, hence the only possibility
would be to have two vertices in the same $C(s_{i},s_{i+1})$ of two different
paths connected by an edge but if that is the case, replacing the center of
that $C$ region by any of the two vertices would reach a shorter total length,
which is not possible. Hence we have that the cycle will be an induced cycle.
∎

###  9.2 Rest of the proof

In this section we complete the proof of Lemma 5.5, the proof is very similar
to the proof for Lemma 4.4 in [BPS21]. For completeness we will include the
whole proof with the convenient modifications. We will start by defining a
partial hub-tree decomposition which is a generalization of the partial DAG-
tree decomposition introduced in [BPS21]:

######  Definition 9.7 (partial hub-tree decomposition ).

Let $\vec{H}$ be a directed graph with hubset set
$\mathcal{S}=\mathcal{S}(\vec{H})$. For a subset
$\mathcal{S}_{p}\subseteq\mathcal{S}$, a partial hub-tree decomposition of
$\vec{H}$ with respect to $\mathcal{S}_{p}$ is a tree
$\mathcal{T}=(\mathcal{B},\mathcal{E})$ with the following three properties.

  1. 1.

Each node $B\in\mathcal{B}$ is a subset of $\mathcal{S}_{p}$: $B\subseteq
S_{p}$.

  2. 2.

The union of the nodes in $\mathcal{T}$ is the entire set $\mathcal{S}_{p}$:
$\bigcup_{B\in\mathcal{B}}B=S_{p}$.

  3. 3.

For all $B,B_{1},B_{2}\in\mathcal{B}$, if $B$ is on the unique path between
$B_{1}$ and $B_{2}$ in $\mathcal{T}$, then we have $Reach_{\vec{H}}(B_{1})\cap
Reach_{\vec{H}}(B_{2})\subseteq Reach_{\vec{H}}(B)$.

In the case that $\mathcal{S}_{p}=\mathcal{S}$ this definition corresponds
exactly with the hub-tree decomposition.

Now we bring a few more definitions from [BPS21], again generalized to
directed graphs:

######  Definition 9.8 (Intersection-cover and $\mathcal{S}_{p}$-cover).

Let $\vec{H}$ be a directed graph with hubset $\mathcal{S}$ =
$\mathcal{S}(\vec{H})$. Let $s_{1}$ and $s_{2}$ be a pair of vertices in
$\mathcal{S}$. We call a vertex $s\in\mathcal{S}$ an intersection-cover of
$s_{1}$ and $s_{2}$ if $Reach(s_{1})\cap Reach(s_{2})\subseteq Reach(s)$.
Assume $\mathcal{S}_{p}\subseteq\mathcal{S}$ is a subset of the hubset
$\mathcal{S}$. We call a vertex $s\in\mathcal{S}$, a $\mathcal{S}_{p}$-cover
of $s_{1}\in\mathcal{S}$ if for each vertex $s_{2}\in\mathcal{S}_{p}$, $s$ is
an intersection-cover for $s_{1}$ and $s_{2}$.

######  Definition 9.9 (Good-pair).

Let $\vec{H}$ be a directed graph with hubset $\mathcal{S}$ =
$\mathcal{S}(\vec{H})$. Let $x\in\mathcal{S}$ be a vertex of the hubset and
$\mathcal{T}_{\mathcal{S}_{p}}$ be a partial hub-tree decomposition of width
one for $\mathcal{S}_{p}\subset\mathcal{S}$ where $x\notin\mathcal{S}_{p}$. We
call the pair $(x,\mathcal{T}_{\mathcal{S}_{p}})$ a good-pair if there exists
a leaf node $l\in\mathcal{T}_{\mathcal{S}_{p}}$ connected to the node
$d\in\mathcal{T}_{\mathcal{S}_{p}}$ such that $d$ is an intersection-cover for
$x$ and $l$.

We also restate the following Lemma, presented in [BPS21] as Lemma $4.8$, but
extending it to non-acyclical directed graphs:

######  Lemma 9.10.

[Equivalent to Lemma $4.8$ of [BPS21]] Let $\vec{H}$ be a directed graph with
hubset $\mathcal{S}=\mathcal{S}(\vec{H})$ and let
$\mathcal{S}_{p}\subset\mathcal{S}$ be a subset of the hubset. Assume ${\cal
T}$ is a partial hub-tree decomposition for $\mathcal{S}_{p}$ with $\tau({\cal
T})=1$. Consider a vertex $s\in\mathcal{S}$ such that
$s\not\in\mathcal{S}_{p}$. If $d$ is a $\mathcal{S}_{p}$-cover of $s$, then
connecting $s$ to $d$ in ${\cal T}$ as a leaf results in a tree ${\cal
T}^{\prime}$ that is a partial hub-tree decomposition for
$\mathcal{S}_{p}\cup\\{s\\}$. Furthermore, $\tau({\cal T}^{\prime})=1$

###### Proof.

Because we had $\tau({\cal T})=1$ and we are just adding a leaf with a single
vertex to ${\cal T}$, we will have that $\tau({\cal T}^{\prime})=1$.
Therefore, suffices to show that ${\cal T}^{\prime}$ is a valid partial hub-
tree decomposition for $\mathcal{S}_{p}\cup\\{s\\}$. We prove by
contradiction: Assume it is not, then there must exist three nodes
$s_{1},s_{2},s_{3}\in{\cal T}^{\prime}$, with $s_{3}$ being in the path
between $s_{1}$ and $s_{2}$, such that $Reach(s_{1})\cap
Reach(s_{2})\not\subseteq Reach(s_{3})$. If $s\not\in\\{s_{1},s_{2},s_{3}\\}$,
then this is not possible as all the nodes were already in ${\cal T}$ and it
was a valid hub-tree decomposition. Hence $s$ must be one of the three
vertices, it can not be $s_{2}$ as $s$ is a leaf, we can assume without loss
of generalization that $s=s_{3}$. Now $s_{2}$ lies on the unique path between
$s_{1}$ and $s$.

If $s_{2}=d$, then because $d$ is a $\mathcal{S}_{p}$-cover of $s$ we will
have that $Reach(s_{1})\cap Reach(s)\subseteq Reach(d)$, reaching a
contradiction. Otherwise, $s_{2}\neq d$ but $s_{2}$ must lie in the path
between $s_{1}$ and $d$, and hence $Reach(s_{1})\cap Reach(d)\subseteq
Reach(s_{2})$ and we also had that $Reach(s_{1})\cap Reach(s)\subseteq
Reach(d)$ hence $Reach(s_{1})\cap Reach(s)\subseteq Reach(s_{2})$. Reaching a
contradiction. ∎

Now we can prove the main lemma of this section, again following closely the
proof of Lemma $4.4$ of [BPS21]. We restate the lemma:

See 5.5

###### Proof.

Let $\vec{H}^{\prime}$ be a $t$-fraternal extension of $H$ and
$\mathcal{S}=\mathcal{S}(\vec{H}^{\prime})$ be the hubset of
$\vec{H}^{\prime}$. Let $\mathcal{S}_{p}\subseteq\mathcal{S}$ denote a subset
of $\mathcal{S}$. We prove by induction on the size of $\mathcal{S}_{p}$, that
there exists a partial hub-tree decomposition of width $1$ for each
$\mathcal{S}_{p}\subseteq\mathcal{S}$. If $\mathcal{S}_{p}=\mathcal{S}$ then
we have that there is a hub-tree decomposition for $\vec{H}^{\prime}$ of width
$\tau=1$.

The base cases for $|\mathcal{S}_{p}|=1$ and $|\mathcal{S}_{p}|=2$ are both
trivial: for $|\mathcal{S}_{p}|=1$ we can put the only vertex of
$\mathcal{S}_{p}$ in its own bag and it will be a valid partial hub-tree
decomposition. For $|\mathcal{S}_{p}|=2$ we can put both vertices in separate
bags and connect them by an edge, obtaining again a valid partial hub-tree
decomposition.

For the inductive step we assume that it is possible to build a partial hub-
tree decomposition with hub-treewidth one for any subset
$\mathcal{S}_{p}\subset\mathcal{S}$ where $|\mathcal{S}_{p}|\leq r$, and
$1\leq|r|<|\mathcal{S}|$. We show how to construct a partial hub-tree
decomposition with $\tau=1$ for any subset of $\mathcal{S}$ of size $r+1$:

Let $\mathcal{S}_{r+1}\subseteq\mathcal{S}$ be any subset of size $r+1$. Let
$x\in\mathcal{S}_{r+1}$ be an arbitrary vertex of $\mathcal{S}_{r+1}$. By the
induction hypothesis we can construct a partial hub-tree decomposition with
$\tau=1$ for $\mathcal{S}_{-x}=\mathcal{S}_{r+1}\setminus\\{x\\}$. We denote
such hub-tree decomposition with ${\cal T}_{-x}$. We can then show that
$(x,{\cal T}_{-x})$ forms a good-pair, this is given by the following claim
which is equivalent to Claim $4.10$ of [BPS21]:

######  Claim 9.11.

There exists a vertex $x\in\mathcal{S}_{r+1}$ and a width one partial hub-tree
decomposition ${\cal T}_{-x}$ for
$\mathcal{S}_{-x}=\mathcal{S}_{r+1}\setminus\\{x\\}$ such that $(x,{\cal
T}_{-x})$ is a good-pair.

###### Proof.

We prove by contradiction. Assume that the claim is false, consider the unique
reachability graph on the vertex set $\mathcal{S}_{r+1}$,
$UR_{\mathcal{S}_{r}+1}$. Let $x\in\mathcal{S}_{r+1}$ be an arbitrary vertex
from $\mathcal{S}_{r+1}$. By the assumption we have that $(x,{\cal T}_{-x})$
is not a good-pair. Hence, for each leaf node $l\in{\cal T}_{-x}$ connected to
the vertex $d$ we get that $d$ is not an intersection-cover for $x$ and $l$.
Hence there exist a vertex $v$ that is reachable by $x$ and $l$ but not $d$.
But also, because $d$ is the only vertex connected to $l$ in ${\cal T}_{-x}$
we have that $d$ is a $\mathcal{S}_{-x}$-cover for $l$ and the only vertex
that can reach $v$ in $\mathcal{S}_{-x}$ is $l$. Thus, the edge $\\{x,l\\}$
will be in $UR_{\mathcal{S}_{r}+1}$.

Because ${\cal T}_{-x}$ has at least two leaves we will have that the degree
of $x$ in $UR_{\mathcal{S}_{r+1}}$ must be at least $2$. This is true for
every vertex in $x\in\mathcal{S}_{r+1}$. This implies that there is a cycle in
$UR_{S_{r+1}}$ of length at least $3$, using Lemma 9.5 this means that
$LICL(H)\geq 3(t+1)$, but we had that $LICL(H)<3(t+1)$, hence reaching a
contradiction. ∎

Now, we show that if we have a good-pair $(x,{\cal T}_{-x})$ we can construct
a hub-tree decomposition of hub-tree decomposition one, again [BPS21] proved a
more restrictive statement that we will generalize:

######  Claim 9.12 (Equivalent to Claim $4.9$ from [BPS21]).

Let $x\in\mathcal{S}_{r+1}$ and ${\cal T}_{-x}$ be a width one partial hub-
tree decomposition for $\mathcal{S}_{-x}=\mathcal{S}_{r+1}\setminus\\{x\\}$
such that $(x,{\cal T}_{-x})$ is a good-pair. Then, there exists a partial
hub-tree decomposition ${\cal T}$ for $\mathcal{S}_{r+1}$ with $\tau({\cal
T})=1$.

###### Proof.

For $(x,{\cal T}_{-x})$ to form a good-pair we must have that there is a leaf
$l$ in ${\cal T}_{-x}$ connected to a node $d\in{\cal T}_{-x}$ such that $d$
is an intersection-cover for $x$ and $l$. From the assumption of the inductive
step we can construct a hub-tree decomposition of width one for
$\mathcal{S}_{r+1}\setminus l$ and connect $l$ as a leaf to the node $d$. Let
${\cal T}$ be the resultant tree. We can show that ${\cal T}$ is a valid hub-
tree decomposition of $\mathcal{S}_{r+1}$ of width $1$.

We had that $d$ is intersection-cover of $l$ and $x$, also because $l$ only
connects to $d$ in ${\cal T}_{-x}$ we have that $d$ is a
$\mathcal{S}_{-x}$-cover of $l$. Hence $d$ is a $\mathcal{S}_{r+1}$-cover of
$l$.

By Lemma 9.10 we have that ${\cal T}$ is a valid partial hub-tree
decomposition of $\mathcal{S}_{r+1}$ with hub-treewidth one. ∎

Hence, combining both claims we get that we can construct a hub-tree
decomposition with hub-treewidth of 1 for $\mathcal{S}_{r+1}$. This proves the
induction and subsequently the lemma. ∎

##  10 Generalizing Bressan’s algorithm

In this section we prove Lemma 5.6. This will complete the proof of the upper
bound of our Main Theorem, as shown in §5. We will show how to adapt Bressan’s
Algorithm to compute the homomorphisms of the fraternal extensions. This
requires working with non-acyclical graphs using the hubset and the hub-tree
decomposition instead of the DAG-tree decomposition, and using graphs that are
weighted and labeled. We start by restating the main lemma of this section:

See 5.6

Given directed graphs $\vec{H}$ and $\vec{G}$. Lemma $4$ in [Bre21] shows a
way of computing homomorphisms for the subgraphs induced by
$Reach_{\vec{H}}(s)$ for every source $s\in S(\vec{H})$. We can generalize
this result to directed weighted and labeled graphs:

######  Lemma 10.1.

Let $\vec{H}$ be a directed weighted and labeled graphs with $k$ vertices and
hubset $\mathcal{S}=\mathcal{S}(\vec{H})$. Let $\vec{G}$ be a directed
weighted graph with max outdegree $d=\Delta^{+}(\vec{G})$. For any vertex
$s\in\mathcal{S}$, the set of homomorphisms from $\vec{H}(s)$ to $\vec{G}$ has
size $O(d^{k-1}n)$ and can be enumerated in time $O(k^{2}d^{k-1}n)$.

###### Proof.

Let $\vec{T}$ be a directed spanning tree of $\vec{H}(s)$ rooted at $s$. Let
$O$ be any arbitrary ordering of the vertices of $\vec{H}(s)$ such that all
the edges of $T$ are not inverted. For every vertex $u\in\vec{H}(s)$ following
that ordering, we can enumerate all the possible candidates of $\vec{G}$ for
the mapping $\phi(u)$. The first vertex $s$ will have $n$ candidates, as it
can be assigned to every vertex in $\vec{G}$. However for all the other
vertices, because they have at least one incoming edge from a vertex already
assigned, we just need to look at the out-neighbors of the corresponding
mapped vertex in $\vec{G}$, there will be then at most $d$ candidates, as that
is the maximum outdegree in $\vec{G}$. Hence the total number of possible
homomorphisms is bounded by $O(nd^{k-1})$. We can list all these candidate
homomorphisms in a similar amount of time. Only left is to verify if each
candidate homomorphisms $\phi$ is valid:

  * •

For each vertex $u\in V_{\vec{H}(s)}$, verify that they are mapped to a vertex
with the same label $L_{\vec{H}}(u)=L_{\vec{G}}(\phi(u))$.

  * •

For each edge $(u,v)\in E_{\vec{H}(s)}$, verify that $(\phi(u),\phi(v))\in
E_{\vec{G}}$ and $W_{\vec{H}}((u,v))\geq W_{\vec{G}}((u,v))$.

This can be done in $O(k^{2})$ time as we will have at most $k$ vertices and
$k^{2}$ edges, and every check can be done in constant time. Hence the total
time required will be $O(k^{2}d^{k-1}n)$. ∎

Note that in the case that the graph $\vec{G}$ has bounded outdegree and
$\vec{H}$ is constant sized we will be able to compute
$\mathrm{Hom}_{\vec{H}(s)}(\vec{G})$ in $O(n)$ time for all the vertices
$s\in\mathcal{S}(\vec{H})$.

Given a hub-tree decomposition ${\cal T}$ of $\vec{H}$, we will use $down(B)$
to denote the down-closure of $B$ in ${\cal T}$, that is, the union of all the
bags $B\in\mathcal{B}$ that are descendants of $B$. We will then use
$\vec{H}(down(B))$ to refer to the union of all the graphs $\vec{H}(B)$ for
$B\in down(B)$.

If $\vec{H}$ has $\tau(H)=1$ we can used a modification of the algorithm
presented by Bressan in [Bre21] to compute $\mathrm{Hom}_{\vec{H}}(\vec{G})$
in linear time. Given a hub-tree decomposition decomposition ${\cal T}$ of
$\vec{H}$, this algorithm uses dynamic programming to compute
$\mathrm{Hom}_{\vec{H}(down(s))}(\vec{G})$ for any vertex $s\in\mathcal{S}$
aggregating the values of $\mathrm{Hom}_{\vec{H}(down(s^{\prime}))}(\vec{G})$
of all the descendants $s^{\prime}$ of $s$ and
$\mathrm{Hom}_{\vec{H}(s)}(\vec{G})$.

Given a homomorphism $\phi$ we say that $\phi^{\prime}$ respects $\phi$ if for
every value $u$ that $\phi$ takes $\phi(u)=\phi^{\prime}(u)$. Given a
homomorphism $\phi$ that maps the vertices in the set $V$, we call the
restriction of $\phi$ to $V^{\prime}\subseteq V$ to the map $\phi^{\prime}$
that maps the vertices of $V^{\prime}$ with $\phi^{\prime}(v)=\phi(v)\forall
v\in V^{\prime}$. Additionally we denote with $ext(\vec{H},\vec{G},\phi)$ to
the number of homomorphisms $\phi^{\prime}$ from $\vec{H}$ to $\vec{G}$ that
respects $\phi$. We can show the following lemma which is a generalization of
Lemma $3$ in [Bre21]:

######  Lemma 10.2.

Let ${\cal T}$ be a hub-tree decomposition of a graph $\vec{H}$ and let
$B_{1},\ldots,B_{l}$ be the children of $B$ in ${\cal T}$. Fix
$\phi_{B}:\vec{H}(B)\to\vec{G}$. Let
$\Phi(\phi_{B})=\\{\phi:\vec{H}(down(B))\to\vec{G}|\phi\text{ respects
}\phi_{B})\\}$, and for $i=1,\ldots,l$ let
$\Phi_{i}(\phi_{B})=\\{\phi:\vec{H}(down(B_{i}))\to\vec{G}|\phi\text{ respects
}\phi_{B})\\}$. Then there exists a bijection between $\Phi(\phi_{B})$ and
$\Phi_{1}(\phi_{B})\times\ldots\times\Phi_{l}(\phi_{B})$, and therefore:

$ext(\vec{H}(down(B)),\vec{G},\phi_{B})=\prod_{i=1}^{l}ext(\vec{H}(down(B_{i})),\vec{G},\phi_{B})$

###### Proof.

The proof is similar to the proof of Lemma $3$ in [Bre21]:

First, we show that there exists an injection from $\Phi(\phi_{B})$ to
$\Phi_{1}(\phi_{B})\times\ldots\times\Phi_{l}(\phi_{B})$: Fix any
$\phi\in\Phi(\phi_{B})$, and let $\phi_{i}$ be the restriction of $\phi$ to
$\vec{H}(down(B_{i}))$, because $\phi$ respects $\phi_{B}$ so will $\phi_{i}$,
hence $\phi_{i}\in\Phi_{i}(\phi_{B})$, therefore the tuple
$(\phi_{1},\ldots,phi_{l})\in\Phi_{1}(\phi_{B})\times\ldots\times\Phi_{l}(\phi_{B})$.

Now we show the opposite, that there exists an injection from
$\Phi_{1}(\phi_{B})\times\ldots\times\Phi_{l}(\phi_{B})$ to $\Phi(\phi_{B})$:
Fix any tuple
$(\phi_{1},\ldots,\phi_{l})\in\Phi_{1}(\phi_{B})\times\ldots\times\Phi_{l}(\phi_{B})$,
note that the different $\phi_{i}$ of the tuple only intersect in
$\vec{H}(B)$, and they all respect $\phi_{B}$, hence we can combine
$\phi_{B},\phi_{1},\ldots,\phi_{l}$ and obtain a homomorphism $\phi$ from
$\vec{H}(down(B_{i}))$ to $\vec{G}$ such that $\phi$ respects $\phi_{B}$,
hence we will have that $\phi\in\Phi(\phi_{B})$.

∎

We now adapt Bressan’s algorithm [Bre21] to our setting, the full algorithm
can be seen in Alg. 4. We prove its correctness and runtime in the following
Lemma:

######  Lemma 10.3.

Let $\vec{H}$ be a labeled weighted and directed graph with a hub-tree
decomposition ${\cal T}$ such that $\tau({\cal T})=1$, let $B$ be any node of
${\cal T}$ and let $\vec{H}$ be a labeled weighted and directed graph with
bounded outdegree. Alg. 4 returns a dictionary $C_{B}$ such that for every
homomorphism $\phi\in\Phi(\vec{H}(B),\vec{G})$ we have
$C_{B}(\phi)=ext(\vec{H}(down(B)),\vec{G},\phi)$, and runs in
$O(n\cdot\log{n})$ time.

###### Proof.

First we prove the correctness of the algorithm. We can see that in the base
case, when $B$ is a leaf of ${\cal T}$, $C_{B}$ will contain $1$ for every
$\phi_{B}\in\Phi(H(B),G)$.

If $B$ is not a leaf, we assume that the algorithm returns the desired value
for every child $B_{i}$ of $B$. In this case the value of $AGG_{B_{i}}$ after
the first for loop will be $|\phi\in\Phi(\vec{H}(B_{i}),\vec{G}):\phi\text{
respects }\phi_{r}|=ext(\vec{H}(down(B_{i})),\vec{G},\phi_{r})$. Hence we will
have that:

$C_{B}(\phi)=\prod_{i=1}^{l}AGG_{B_{i}}(\phi_{i})=\prod_{i=1}^{l}ext(\vec{H}(down(B_{i})),\vec{G},\phi_{i})$
$=\prod_{i=1}^{l}ext(\vec{H}(down(B_{i})),\vec{G},\phi)=ext(\vec{H}(down(B)),\vec{G},\phi)$

Where the last inequality comes from Lemma 10.2.

For the runtime, we have that $B$ has at most $O(k)$ children, from Lemma 10.1
we have that every dictionary $C_{B_{i}}$ will have at most $O(n)$ keys, and
we can enumerate them in $O(n)$ time. We will need $O(n\log{n})$ time to
access the dictionary, so the total complexity is $O(n\cdot\log{n})$. ∎

Input:
-Directed weighted labeled graph $\vec{H}$ with hub-tree decomposition ${\cal T}$
-Directed weighted labeled graph $\vec{G}$
-A node $B\in{\cal T}$
Output:
-Dictionary $C_{B}$

1:Let $C_{B}$ be an empty dictionary with default value $0$.

2:if $B$ is a leaf then

3: for every homomorphism $\phi_{B}:\vec{H}(B)\to\vec{G}$ do

4: $C_{B}(\phi_{B})=1$

5: end for

6:else

7: let $B_{1},\ldots,B_{l}$ be the children of $B$ in ${\cal T}$

8: for $i=1,\ldots,l$ do

9: $C_{B_{i}}=$Generalized Bressan’s Algorithm$(\vec{H},\vec{G},B_{i})$

10: Let $AGG_{B_{i}}$ be an empty dictionary with default value $0$.

11: for every key $\phi$ in $C_{B_{i}}$ do

12: let $\phi_{r}$ be the restriction of $\phi$ to $Reach_{\vec{H}}(B)\cap
Reach_{\vec{H}}(down(B_{i}))$

13: $AGG_{B_{i}}(\phi_{r})+=C_{B_{i}}(\phi)$

14: end for

15: end for

16: for every homomorphism $\phi:\vec{H}(B)\to\vec{G}$ do

17: Let $\phi_{i}$ be the restriction of $\phi$ to $Reach_{\vec{H}}(B)\cap
Reach_{\vec{H}}(down(B_{i}))$, for $i=1,\ldots,l$.

18: $C_{B}(\phi)=\prod_{i=1}^{l}AGG_{B_{i}}(\phi_{i})$

19: end for

20:end if

21:return $C_{B}$

Algorithm 4 Generalized Bressan’s Algorithm:
Homomorphisms($\vec{H},\vec{G},B$)

We can finally prove the main lemma of this section:

###### Proof of Lemma 5.6.

We can compute a hub-tree decomposition ${\cal T}$ for $\vec{H}$ in $f(k)$