$a_{0},a_{1},\ldots,a_{\alpha},c_{i}$. Such a cycle has length $2\ell+3$, and
thus $p_{1}$ and $p_{2}$ touch due to Lemma 5.5. Hence $\psi$ is a valid
clique-embedding function.

It remains to show $\operatorname{wed}(\psi)=2\gamma+\ell$. In isolation, the
subgraphs of type A give weak edge depth of $\ell+2$ to each edge in
$\mathcal{C}$ because every edge intersects exactly $\ell+2$ paths of length
$\ell$.

We claim that the subgraphs of types B and C increase weak edge depths of all
edges in $\mathcal{C}$ by $2\gamma-2$. Edges on the path $c_{1}\leftrightline
a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline a_{\ell}$
intersect $\gamma-1$ subgraphs of type C and the subgraph $a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\ell}$ of type B with weight
$\gamma-1$. Edges on the path $c_{1}\leftrightline a_{\alpha}\leftrightline
a_{\alpha-1}\leftrightline\cdots\leftrightline a_{\ell+1}$ touch the symmetric
subgraphs. The remaining edge $\\{a_{\ell},a_{\ell+1}\\}$ touches both
subgraphs of type B with weight $\gamma-1$ each and no subgraphs of type C.
Hence, every edge in $\mathcal{C}$ has weak edge depth
$\ell+2+2\gamma-2=2\gamma+\ell$.

It remains to argue that edges outside of $\mathcal{C}$ have weak edge depth
$2\gamma+\ell$. Such edges have form $\\{a_{0},c_{i}\\}$ or
$\\{a_{\alpha},c_{i}\\}$ for some $i\in[2,\gamma]$. We already know that weak
edge depth of $\\{a_{0},c_{1}\\}$ is $2\gamma+\ell$. If we switch from this
edge to $\\{a_{0},c_{i}\\}$, we lose a single path of type A that ends in
$c_{1}$ and gain a single path of form $c_{i}\leftrightline
a_{\alpha}\leftrightline a_{\alpha-1}\leftrightline\cdots\leftrightline
a_{\ell+2}$ of type C. Therefore, weak edge depth of $\\{a_{0},c_{i}\\}$ is
the same as for $\\{a_{0},c_{1}\\}$. Edges of the form
$\\{a_{\alpha},c_{i}\\}$ can be checked symmetrically.

###  5.2 Lower bounds for $P(\alpha,\beta,\gamma\times 2)$

For a graph $P(\alpha,\beta,\gamma\times 2)$ for $\alpha\geq\beta\geq 3$ and
$\gamma\geq 1$ we fix its node numbering as follows (see Figure 10). We denote
the nodes on the path of length $\alpha$ by $a_{0}$, $a_{1}$, $\ldots$,
$a_{\alpha-1}$, $a_{\alpha}$, where $a_{0}$ and $a_{\alpha}$ are the ends of
the path. We denote the nodes on the path of length $\beta$ by $b_{0}$,
$b_{1}$, $\ldots$, $b_{\beta-1}$, $b_{\beta}$. Note that $a_{0}=b_{0}$ and
$a_{\alpha}=b_{\beta}$. We denote the nodes in the paths of length $2$ that
are adjacent to both $a_{0}$ and $a_{\alpha}$ by $c_{1}$, $c_{2}$, $\ldots$,
$c_{\gamma}$.

Figure 10: An example of a node numbering for $P(\alpha,\beta,\gamma\times 2)$
for $\alpha=7$, $\beta=4$, and $\gamma=2$.

######  Lemma 5.9.

For any $\alpha\geq\beta\geq 5$, $\alpha+\beta$ odd, and $\gamma\geq 1$, we
have $\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq
2-1/(2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+2\beta-\frac{\alpha}{2}-4\gamma-\frac{3}{2})$.

######  Proof 5.10.

As $\alpha+\beta$ is odd and $\alpha\geq\beta$, we have $\alpha\geq\beta+1$.

Define $X\coloneqq
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+2\beta-\frac{\alpha}{2}-4\gamma-\frac{3}{2}=(\beta-1)\cdot(2\gamma+\frac{\alpha-\beta+3}{2})-2\gamma$.
We create a clique embedding $\psi$ from $K_{2X-1}$ to
$P(\alpha,\beta,\gamma\times 2)$ with $\operatorname{wed}(\psi)=X$, which
yields $\operatorname{clemb}(P(\alpha,\beta,\gamma\times
2))\geq\frac{2X-1}{X}=2-\frac{1}{X}$, as desired. We treat the paths
$a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline a_{\alpha}$ and
$b_{0}\leftrightline b_{1}\leftrightline\cdots\leftrightline b_{\beta}$ as a
cycle $\mathcal{C}$ of length $\alpha+\beta$. We use $6$ different types of
subgraphs that we embed into. See Figure 11.

  1. A.

We embed one node into each path of the form $a_{\ell}\leftrightline
a_{\ell+1}\leftrightline\cdots\leftrightline
a_{\ell+\frac{\alpha+\beta-3}{2}-1}$ for $\ell\in[\frac{\alpha-\beta+3}{2}]$.

  2. B.

We embed $\gamma+\frac{\alpha-\beta+3}{2}$ nodes into the path
$b_{\beta-2}\leftrightline b_{\beta-3}\leftrightline\cdots\leftrightline
b_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline
a_{\frac{\alpha-\beta+3}{2}-1}$. Furthermore, we embed
$2\gamma+\frac{\alpha-\beta+3}{2}$ nodes into each path of the form
$b_{\beta-3-\ell}\leftrightline
b_{\beta-4-\ell}\leftrightline\cdots\leftrightline b_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\frac{\alpha-\beta+3}{2}+\ell}$ for
$\ell\in[0,\beta-4]$ (note that there is at least one such $\ell$ as
$\beta\geq 5$).

  3. C.

Symmetrically, we embed $\gamma+\frac{\alpha-\beta+3}{2}$ nodes into the path
$a_{\frac{\alpha+\beta-3}{2}+1}\leftrightline
a_{\frac{\alpha+\beta-3}{2}+2}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline b_{\beta-1}\leftrightline\cdots\leftrightline b_{2}$.
Furthermore, we embed $2\gamma+\frac{\alpha-\beta+3}{2}$ nodes into each path
of the form $a_{\frac{\alpha+\beta-3}{2}+\ell}\leftrightline
a_{\frac{\alpha+\beta-3}{2}+\ell+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline b_{\beta-1}\leftrightline\cdots\leftrightline
b_{\ell+3}$ for $\ell\in[0,\beta-4]$ (note that there is at least one such
$\ell$ as $\beta\geq 4$).

  4. D.

We embed one node into each path of the form
$a_{\frac{\alpha+\beta-3}{2}+\ell}\leftrightline
a_{\frac{\alpha+\beta-3}{2}+\ell+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline c_{1}\leftrightline a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\ell-2}$ for
$\ell\in[2,\frac{\alpha-\beta+3}{2}]$ (note that there is at least one such
$\ell$ as $\alpha-\beta\geq 1$).

  5. E.

We embed one node into each path of the form $c_{\ell}\leftrightline
a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline
a_{\frac{\alpha-\beta+3}{2}-1}$ for $\ell\in[\gamma]$.

  6. F.

We embed one node into each path of the form
$a_{\frac{\alpha+\beta-3}{2}+1}\leftrightline
a_{\frac{\alpha+\beta-3}{2}+2}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline c_{\ell}$ for $\ell\in[\gamma]$.

Figure 11: Illustration of the proof of Lemma 5.9. In addition to the abstract
situation of Lemma 5.9, the figure also shows the clique embedding for
$P(12,7,2,2)$.

We now analyze this construction. In total, we embed

$\displaystyle\frac{\alpha-\beta+3}{2}\cdot 1$ (A)
$\displaystyle+(\gamma+\frac{\alpha-\beta+3}{2})+(\beta-3)\cdot(2\gamma+\frac{\alpha-\beta+3}{2})$
(B)
$\displaystyle+(\gamma+\frac{\alpha-\beta+3}{2})+(\beta-3)\cdot(2\gamma+\frac{\alpha-\beta+3}{2})$
(C) $\displaystyle+(\frac{\alpha-\beta+3}{2}-2+1)\cdot 1$ (D)
$\displaystyle+\gamma\cdot 1$ (E) $\displaystyle+\gamma\cdot 1$ (F)
$\displaystyle=2\cdot((\beta-1)\cdot(2\gamma+\frac{\alpha-\beta+3}{2})-2\gamma)-1$

nodes, which is exactly the number of nodes in $K_{2X-1}$. It is clear that
all subgraphs into which we embed are connected. Next, we prove that all pairs
of these subgraphs touch. For every type from A to F we show that the paths of
this type touch each other and all later types.

  1. A.

All paths of type A start not later than node $a_{\frac{\alpha-\beta+3}{2}}$
and end not earlier than node $a_{\frac{\alpha+\beta-3}{2}}$. Note that
$\frac{\alpha-\beta+3}{2}<\frac{\alpha+\beta-3}{2}$ as $\beta\geq 5$. Thus,
all these paths contain all nodes
$a_{\frac{\alpha-\beta+3}{2}},\ldots,a_{\frac{\alpha+\beta-3}{2}}$, and all
pairs of them touch. All paths of type B end not earlier than node
$a_{\frac{\alpha-\beta+3}{2}-1}$, so they touch all paths of type A on the
edge $\\{a_{\frac{\alpha-\beta+3}{2}-1},a_{\frac{\alpha-\beta+3}{2}}\\}$.
Symmetrically, all paths of type C start not later than
$a_{\frac{\alpha+\beta-3}{2}+1}$, so they all touch all paths of type A on the
edge $\\{a_{\frac{\alpha+\beta-3}{2}},a_{\frac{\alpha+\beta-3}{2}+1}\\}$. For
any fixed $\ell$, paths of types D (for $\ell=1$), E (for $\ell\in[\gamma]$),
and F (for $\ell\in[\gamma]$) lie on the cycle $a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\alpha}\leftrightline c_{\ell}$ of
length $\alpha+2$, which also contains all paths of type A. The paths of types
D, E, and F have length $\frac{\alpha-\beta+3}{2}$, while the paths of type A
have length $\frac{\alpha+\beta-3}{2}-1$. Thus, Lemma 5.5 implies that all
pairs of them touch.

  2. B.

All paths of type B go through node $a_{0}$, so all pairs of them touch. All
paths of type B lie on the cycle $\mathcal{C}$ of length $\alpha+\beta$
together with all paths of type C. All of these paths have length
$\frac{\alpha+\beta-3}{2}$. Thus, Lemma 5.5 implies that each path of type B
and each path of type C touch. For any fixed $\ell$, paths of types D (for
$\ell=1$), E (for $\ell\in[\gamma]$), and F (for $\ell\in[\gamma]$) go through
node $c_{\ell}$, so they touch paths of type B on the edge
$\\{a_{0},c_{\ell}\\}$.

  3. C.

All paths of type C go through node $a_{\alpha}$, so all pairs of them touch.
For any fixed $\ell$, paths of types D (for $\ell=1$), E (for
$\ell\in[\gamma]$), and F (for $\ell\in[\gamma]$) go through node $c_{\ell}$,
so they touch paths of type C on the edge $\\{a_{\alpha},c_{\ell}\\}$.

  4. D-F.

Any path of type D, E, or F goes either through node $a_{0}$ or through node
$a_{\alpha}$. Any other such path goes through node $c_{\ell}$ for some
$\ell\in[\gamma]$. Hence, they touch either on the edge $\\{a_{0},c_{\ell}\\}$
or on the edge $\\{a_{\alpha},c_{\ell}\\}$.

We showed that all pairs of subgraphs we embed touch, so $\psi$ is a valid
clique embedding. It remains to show that all edges have weak edge depth at
most $X$. There are

$\displaystyle(\gamma+\frac{\alpha-\beta+3}{2})+(\beta-3)\cdot(2\gamma+\frac{\alpha-\beta+3}{2})$
(B) $\displaystyle+(\frac{\alpha-\beta+3}{2}-2+1)\cdot 1$ (D)
$\displaystyle+\gamma\cdot 1$ (E)
$\displaystyle=(\beta-1)\cdot(2\gamma+\frac{\alpha-\beta+3}{2})-2\gamma-1$
$\displaystyle=X-1$

embedded subgraphs that go through node $a_{0}$. Node $b_{1}$ is not contained
in any paths that $a_{0}$ is not contained in. Hence, weak edge depth of
$\\{a_{0},b_{1}\\}$ is equal to $X-1$. For all edges of the form
$\\{a_{0},c_{\ell}\\}$ for $\ell\in[\gamma]$, the only new path that
$c_{\ell}$ adds to the subgraphs that are already embedded into $a_{0}$ are
paths of type F, contributing one to weak edge depth of these edges. So each
edge $\\{a_{0},c_{\ell}\\}$ has weak edge depth $(X-1)+1=X$. The same holds
for the edge $\\{a_{0},a_{1}\\}$ as the only new path that $a_{1}$ adds to the
subgraphs that are already embedded into $a_{0}$ is the path of type A that
starts in $a_{1}$, which contributes one to weak edge depth of this edge.
Whenever we now move from an edge $\\{a_{\ell},a_{\ell+1}\\}$ to an edge
$\\{a_{\ell+1},a_{\ell+2}\\}$ for $\ell\in[0,\frac{\alpha-\beta+3}{2}-2]$
(note that there is at least one such $\ell$ as $\alpha\geq\beta+1$), we lose
a single path of type D that ends in $a_{\ell}$, and we gain a single path of
type A that starts in $a_{\ell+2}$. Both have weight one, so weak edge depth
remains at $X$. When we move from the edge
$\\{a_{\frac{\alpha-\beta+3}{2}-1},a_{\frac{\alpha-\beta+3}{2}}\\}$ to the
edge $\\{a_{\frac{\alpha-\beta+3}{2}},a_{\frac{\alpha-\beta+3}{2}+1}\\}$, we
lose a single path of type B with weight $\gamma+\frac{\alpha-\beta+3}{2}$
that ends in $a_{\frac{\alpha-\beta+3}{2}-1}$ and all paths of type E with
total weight $\gamma$. At the same time we gain a single path of type C with
weight $2\gamma+\frac{\alpha-\beta+3}{2}$ that starts in node
$a_{\frac{\alpha-\beta+3}{2}+1}$. In total, weak edge depth of
$\\{a_{\frac{\alpha-\beta+3}{2}},a_{\frac{\alpha-\beta+3}{2}+1}\\}$ is again
$X$. Next, whenever we move from an edge $\\{a_{\ell},a_{\ell+1}\\}$ to an
edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[\frac{\alpha-\beta+3}{2},\frac{\alpha+\beta-3}{2}-2]$ (there is at
least one such $\ell$ because $\beta\geq 5$), we lose a single path of type B
with weight $2\gamma+\frac{\alpha-\beta+3}{2}$ that ends in node $a_{\ell}$,
and we gain a single path of type C with weight
$2\gamma+\frac{\alpha-\beta+3}{2}$ that starts in node $a_{\ell+2}$, so weak
edge depth remains at $X$. When we move from the edge
$\\{a_{\frac{\alpha+\beta-3}{2}-1},a_{\frac{\alpha+\beta-3}{2}}\\}$ to the
edge $\\{a_{\frac{\alpha+\beta-3}{2}},a_{\frac{\alpha+\beta-3}{2}+1}\\}$, we
lose a single path of type B with weight $2\gamma+\frac{\alpha-\beta+3}{2}$
that ends in node $a_{\frac{\alpha+\beta-3}{2}-1}$. We gain a path of type C
with weight $\gamma+\frac{\alpha-\beta+3}{2}$ that starts in node
$a_{\frac{\alpha+\beta-3}{2}+1}$ and all paths of type F with total weight
$\gamma$. Hence, weak edge depth of
$\\{a_{\frac{\alpha+\beta-3}{2}},a_{\frac{\alpha+\beta-3}{2}+1}\\}$ is again
$X$. Whenever we move from an edge $\\{a_{\ell},a_{\ell+1}\\}$ to an edge
$\\{a_{\ell+1},a_{\ell+2}\\}$ for $\ell\in[\frac{\alpha+\beta-3}{2},\alpha-2]$
(there is at least one such $\ell$ as $\alpha\geq\beta+1$), we lose a single
path of type A that ends in node $a_{\ell}$ and gain a single path of type D
that starts in node $a_{\ell+2}$. Both of them have weight one, so weak edge
depth of the current edge remains at $X$. If we move from the edge
$\\{a_{\alpha-1},a_{\alpha}\\}$ to an edge $\\{a_{\alpha},c_{\ell}\\}$ for
$\ell\in[\gamma]$, we lose a single path of type A that ends in $a_{\alpha-1}$
and gain a single path of type E that starts in $c_{\ell}$, so each such edge
has weak edge depth $X$. When we move from the edge
$\\{a_{\alpha-1},a_{\alpha}\\}$ to the edge $\\{b_{\beta-1},b_{\beta}\\}$, we
do not gain any new subgraphs, but we lose a single path of type A that ends
in $a_{\alpha-1}$, so weak edge depth of $\\{b_{\beta-1},b_{\beta}\\}$ is
$X-1$. When we move from the edge $\\{b_{\beta-1},b_{\beta}\\}$ to the edge
$\\{b_{\beta-2},b_{\beta-1}\\}$, we lose all paths of types D and F of total
weight $\frac{\alpha-\beta+3}{2}-1+\gamma$, and we gain a single path of type
B with weight $\gamma+\frac{\alpha-\beta+3}{2}$ that starts in $b_{\beta-2}$.
In total, weak edge depth of $\\{b_{\beta-2},b_{\beta-1}\\}$ is
$(X-1)-(\frac{\alpha-\beta+3}{2}-1+\gamma)+(\gamma+\frac{\alpha-\beta+3}{2})=X$.
Whenever we now move from an edge $\\{b_{\ell+1},b_{\ell+2}\\}$ to an edge
$\\{b_{\ell},b_{\ell+1}\\}$ for $\ell\in[\beta-3]$ (note that there is at
least one such $\ell$ as $\beta\geq 5$), we lose a single path of type C with
weight $2\gamma+\frac{\alpha-\beta+3}{2}$ that ends in node $b_{\ell+2}$, and
we gain a single path of type B with the same weight that starts in node
$b_{\ell}$, so weak edge depth of the current edge remains at $X$. This way we
checked that weak edge depth of every edge is at most $X$, which concludes the
proof of the fact that $\operatorname{wed}(\psi)=X$.

The proofs of the following two lemmas are very similar to the previous one.

######  Lemma 5.11.

For any $\alpha\geq\beta\geq 3$, $\alpha+\beta$ odd, and $\gamma\geq 1$, we
have $\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq
2-1/(2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\beta-\frac{\alpha}{2}-2\gamma+\frac{3}{2})$.

######  Proof 5.12.

As $\alpha+\beta$ is odd and $\alpha\geq\beta$, we have $\alpha\geq\beta+1$.

Define $X\coloneqq
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\beta-\frac{\alpha}{2}-2\gamma+\frac{3}{2}=(\beta-1)\cdot(2\gamma+\frac{\alpha-\beta-1}{2}+1)+2$.
We create a clique embedding $\psi$ from $K_{2X-1}$ to
$P(\alpha,\beta,\gamma\times 2)$ with $\operatorname{wed}(\psi)=X$, which
yields $\operatorname{clemb}(P(\alpha,\beta,\gamma\times
2))\geq\frac{2X-1}{X}=2-\frac{1}{X}$, as desired. We treat the paths
$a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline a_{\alpha}$ and
$b_{0}\leftrightline b_{1}\leftrightline\cdots\leftrightline b_{\beta}$ as a
cycle $\mathcal{C}$ of length $\alpha+\beta$. We use $6$ different types of
subgraphs that we embed into. See Figure 12.

  1. A.

We embed one node into each path of the form $a_{\ell}\leftrightline
a_{\ell+1}\leftrightline\cdots\leftrightline
a_{\ell+\frac{\alpha+\beta+1}{2}-2}$ for
$\ell\in[\frac{\alpha-\beta-1}{2}+1]$.

  2. B.

We embed one node into the path $b_{\beta-1}\leftrightline
b_{\beta-2}\leftrightline\cdots\leftrightline b_{1}\leftrightline
a_{0}\leftrightline\cdots\leftrightline a_{\frac{\alpha-\beta-1}{2}}$.
Furthermore, we embed $2\gamma+\frac{\alpha-\beta-1}{2}+1$ nodes into each
path of the form $b_{\beta-\ell-1}\leftrightline
b_{\beta-\ell-2}\leftrightline\cdots\leftrightline b_{1}\leftrightline
a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline
a_{\frac{\alpha-\beta-1}{2}+\ell}$ for $\ell\in[\beta-2]$. Moreover, we embed
$\gamma+1$ nodes into the path $a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\frac{\alpha+\beta+1}{2}-2}$.

  3. C.

Symmetrically, we embed one node into the path
$a_{\frac{\alpha+\beta+1}{2}}\leftrightline
a_{\frac{\alpha+\beta+1}{2}+1}\leftrightline\cdots\leftrightline
a_{\alpha-1}\leftrightline b_{\beta}\leftrightline
b_{\beta-1}\leftrightline\cdots\leftrightline b_{1}$. Furthermore, we embed
$2\gamma+\frac{\alpha-\beta-1}{2}+1$ nodes into each path of the form
$a_{\frac{\alpha-\beta-1}{2}+\ell}\leftrightline
a_{\frac{\alpha-\beta-1}{2}+\ell+1}\leftrightline\cdots\leftrightline
a_{\alpha-1}\leftrightline b_{\beta}\leftrightline
b_{\beta-1}\leftrightline\cdots\leftrightline b_{\beta-\ell+2}$ for
$\ell\in[3,\beta]$. Moreover, we embed $\gamma+1$ nodes into the path
$a_{\frac{\alpha-\beta-1}{2}+2}\leftrightline
a_{\frac{\alpha-\beta-1}{2}+3}\leftrightline\cdots\leftrightline
a_{\alpha-1}\leftrightline a_{\alpha}$.

  4. D.

If $\alpha\geq\beta+3$, we embed one node into each path of the form
$a_{\frac{\alpha+\beta+1}{2}+\ell}\leftrightline
a_{\frac{\alpha+\beta+1}{2}+\ell+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline c_{1}\leftrightline a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\ell-1}$ for
$\ell\in[\frac{\alpha-\beta-1}{2}]$.

  5. E.

We embed one node into each path of the form $c_{\ell}\leftrightline
a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline
a_{\frac{\alpha-\beta-1}{2}}$ for $\ell\in[\gamma]$.

  6. F.

We embed one node into each path of the form
$a_{\frac{\alpha+\beta+1}{2}}\leftrightline
a_{\frac{\alpha+\beta+1}{2}+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline c_{\ell}$ for $\ell\in[\gamma]$.

Figure 12: Illustration of the proof of Lemma 5.11. In addition to the
abstract situation of Lemma 5.11, the figure also shows the clique embedding
for $P(13,6,2,2)$.

We now analyze this construction. In total, we embed

$\displaystyle(\frac{\alpha-\beta-1}{2}+1)\cdot 1$ (A)
$\displaystyle+1+(\beta-2)\cdot(2\gamma+\frac{\alpha-\beta-1}{2}+1)+(\gamma+1)$
(B)
$\displaystyle+1+(\beta-3+1)\cdot(2\gamma+\frac{\alpha-\beta-1}{2}+1)+(\gamma+1)$
(C) $\displaystyle+\frac{\alpha-\beta-1}{2}\cdot 1$ (D)
$\displaystyle+\gamma\cdot 1$ (E) $\displaystyle+\gamma\cdot 1$ (F)
$\displaystyle=2\cdot((\beta-1)\cdot(2\gamma+\frac{\alpha-\beta-1}{2}+1)+2)-1$

nodes, which is exactly the number of nodes in $K_{2X-1}$. It is clear that
all subgraphs into which we embed are connected. Next, we prove that all pairs
of these subgraphs touch. For every type from A to F we show that the paths of
this type touch each other and all later types.

  1. A.

All paths of type A start not later than node $a_{\frac{\alpha-\beta-1}{2}+1}$
and end not earlier than node $a_{\frac{\alpha+\beta+1}{2}-1}$. Note that
$\frac{\alpha-\beta-1}{2}+1<\frac{\alpha+\beta+1}{2}-1$ because $\beta\geq 3$.
Thus, all these paths contain all nodes
$a_{\frac{\alpha-\beta-1}{2}+1},\ldots,a_{\frac{\alpha+\beta+1}{2}-1}$, and
all pairs of them touch. All paths of type B end not earlier than node
$a_{\frac{\alpha-\beta-1}{2}}$, so they touch all paths of type A on the edge
$\\{a_{\frac{\alpha-\beta-1}{2}},a_{\frac{\alpha-\beta-1}{2}+1}\\}$.
Symmetrically, all paths of type C start not later than
$a_{\frac{\alpha+\beta+1}{2}}$, so they touch all paths of type A on the edge
$\\{a_{\frac{\alpha+\beta+1}{2}-1},a_{\frac{\alpha+\beta+1}{2}}\\}$. For any
fixed $\ell$, paths of types D (for $\ell=1$), E (for $\ell\in[\gamma]$), and
F (for $\ell\in[\gamma]$) lie on the cycle $a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\alpha}\leftrightline c_{\ell}$ of
length $\alpha+2$, which also contains all paths of type A. The paths of types
D, E, and F have length $\frac{\alpha-\beta-1}{2}+1$, while the paths of type
A have length $\frac{\alpha+\beta+1}{2}-2$. Thus, Lemma 5.5 implies that all
pairs of them touch.

  2. B.

All paths of type B go through node $a_{0}$, so all pairs of them touch. All
paths of type B lie on the cycle $\mathcal{C}$ of length $\alpha+\beta$
together with all paths of type C. All of these paths have length
$\frac{\alpha+\beta+1}{2}-2$. Thus, Lemma 5.5 implies that each path of type B
and each path of type C touch. For any fixed $\ell$, paths of types D (for
$\ell=1$), E (for $\ell\in[\gamma]$), and F (for $\ell\in[\gamma]$) go through
node $c_{\ell}$, so they touch all paths of type B on the edge
$\\{a_{0},c_{\ell}\\}$.

  3. C.

All paths of type C go through node $a_{\alpha}$, so all pairs of them touch.
For any fixed $\ell$, paths of types D (for $\ell=1$), E (for
$\ell\in[\gamma]$), and F (for $\ell\in[\gamma]$) go through node $c_{\ell}$,
so they touch paths of type C on the edge $\\{a_{\alpha},c_{\ell}\\}$.

  4. D-F.

Any path of type D, E, or F goes either through node $a_{0}$ or through node
$a_{\alpha}$. Any other such path goes through node $c_{\ell}$ for some
$\ell\in[\gamma]$. Hence, they touch either on the edge $\\{a_{0},c_{\ell}\\}$
or on the edge $\\{a_{\alpha},c_{\ell}\\}$.

We showed that all pairs of subgraphs we embed touch, so $\psi$ is a valid
clique embedding. It remains to show that all edges have weak edge depth at
most $X$. There are

$\displaystyle
1+(\beta-2)\cdot(2\gamma+\frac{\alpha-\beta-1}{2}+1)+(\gamma+1)$ (B)
$\displaystyle+\frac{\alpha-\beta-1}{2}\cdot 1$ (D) $\displaystyle+\gamma\cdot
1$ (E) $\displaystyle=X-1$

embedded subgraphs that go through node $a_{0}$. The only subgraph that node
$b_{1}$ is contained in that $a_{0}$ is not contained in is the path of type C
with weight one that ends in $b_{1}$. Hence, weak edge depth of
$\\{a_{0},b_{1}\\}$ is equal to $X$. For all edges of the form
$\\{a_{0},c_{\ell}\\}$ for $\ell\in[\gamma]$, the only new path that
$c_{\ell}$ adds to the subgraphs that are already embedded into $a_{0}$ are
paths of type F, contributing one to weak edge depth of these edges. So each
edge $\\{a_{0},c_{\ell}\\}$ has weak edge depth $(X-1)+1=X$. The same holds
for the edge $\\{a_{0},a_{1}\\}$ as the only new path that $a_{1}$ adds to the
subgraphs that are already embedded into $a_{0}$ is the path of type A that
starts in $a_{1}$, which contributes one to weak edge depth of this edge. If
$\alpha\geq\beta+3$, whenever we now move from an edge
$\\{a_{\ell},a_{\ell+1}\\}$ to an edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[0,\frac{\alpha-\beta-1}{2}-1]$, we lose a single path of type D that
ends in $a_{\ell}$, and we gain a single path of type A that starts in
$a_{\ell+2}$. Both have weight one, so weak edge depth remains at $X$. When we
move from the edge
$\\{a_{\frac{\alpha-\beta-1}{2}},a_{\frac{\alpha-\beta-1}{2}+1}\\}$ to the
edge $\\{a_{\frac{\alpha-\beta-1}{2}+1},a_{\frac{\alpha-\beta-1}{2}+2}\\}$, we
lose a single path of type B with weight one that ends in
$a_{\frac{\alpha-\beta-1}{2}}$ and all paths of type E with total weight
$\gamma$. At the same time we gain a single path of type C with weight
$\gamma+1$ that starts in node $a_{\frac{\alpha-\beta-1}{2}+2}$. In total,
weak edge depth of
$\\{a_{\frac{\alpha-\beta-1}{2}+1},a_{\frac{\alpha-\beta-1}{2}+2}\\}$ is again
$X$. Next, whenever we move from an edge $\\{a_{\ell},a_{\ell+1}\\}$ to an
edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[\frac{\alpha-\beta-1}{2}+1,\frac{\alpha+\beta+1}{2}-3]$ (there is at
least one such $\ell$ as $\beta\geq 3$), we lose a single path of type B with
weight $2\gamma+\frac{\alpha-\beta-1}{2}+1$ that ends in node $a_{\ell}$, and
we gain a single path of type C with weight
$2\gamma+\frac{\alpha-\beta-1}{2}+1$ that starts in node $a_{\ell+2}$ so weak
edge depth remains at $X$. When we move from the edge
$\\{a_{\frac{\alpha+\beta+1}{2}-2},a_{\frac{\alpha+\beta+1}{2}-1}\\}$ to the
edge $\\{a_{\frac{\alpha+\beta+1}{2}-1},a_{\frac{\alpha+\beta+1}{2}}\\}$, we
lose a single path of type B with weight $\gamma+1$ that ends in node
$a_{\frac{\alpha+\beta+1}{2}-2}$. We gain a path of type C with weight one
that starts in node $a_{\frac{\alpha+\beta+1}{2}}$ and all paths of type F
with total weight $\gamma$. Hence, weak edge depth of
$\\{a_{\frac{\alpha+\beta+1}{2}-1},a_{\frac{\alpha+\beta+1}{2}}\\}$ is again
$X$. Now if $\alpha\geq\beta+3$, whenever we move from an edge
$\\{a_{\ell},a_{\ell+1}\\}$ to an edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[\frac{\alpha+\beta+1}{2}-1,\alpha-2]$, we lose a single path of type
A that ends in node $a_{\ell}$, and we gain a single path of type D that
starts in node $a_{\ell+2}$. Both of them have weight one, so weak edge depth
of the current edge remains at $X$. If we move from the edge
$\\{a_{\alpha-1},a_{\alpha}\\}$ to an edge $\\{a_{\alpha},c_{\ell}\\}$ for
$\ell\in[\gamma]$, we lose a single path of type A that ends in
$a_{\alpha-1}$, and we gain a single path of type E that starts in $c_{\ell}$,
so each such edge has weak edge depth $X$. When we move from the edge
$\\{a_{\alpha-1},a_{\alpha}\\}$ to the edge $\\{b_{\beta},b_{\beta-1}\\}$, we
similarly lose a single path of type A with weight one that ends in
$a_{\alpha-1}$, and we gain a single path of type B with weight one that
starts in $b_{\beta-1}$, so weak edge depth of $\\{b_{\beta},b_{\beta-1}\\}$
is $X$. Now when we move from the edge $\\{b_{\beta},b_{\beta-1}\\}$ to the
edge $\\{b_{\beta-1},b_{\beta-2}\\}$, we lose a single path of type C with
weight $\gamma+1$ that ends in node $b_{\beta}$ and all paths of types D and F
of total weight $\frac{\alpha-\beta-1}{2}+\gamma$. At the same time we gain a
single path of type B with weight $2\gamma+\frac{\alpha-\beta-1}{2}+1$ that
starts in node $b_{\beta-2}$. In total, weak depth is again $X$. Now if
$\beta\geq 4$, whenever we move from an edge $\\{b_{\ell+2},b_{\ell+1}\\}$ to
an edge $\\{b_{\ell+1},b_{\ell}\\}$ for $\ell\in[\beta-3]$, we lose a single
path of type C with weight $2\gamma+\frac{\alpha-\beta-1}{2}+1$ that ends in
$b_{\ell+2}$, and we gain a single path of type B with the same weight that
starts in node $b_{\ell}$, so weak edge depth of the current edge remains at
$X$. This way we checked that weak edge depth of every edge is at most $X$,
which concludes the proof of the fact that $\operatorname{wed}(\psi)=X$.

######  Lemma 5.13.

For any $\alpha\geq\beta\geq 3$, $\alpha+\beta$ even, and $\gamma\geq 1$, we
have $\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq
2-1/(2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{3\beta}{2}-\frac{\alpha}{2}-3\gamma)$.

######  Proof 5.14.

Define $X\coloneqq
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{3\beta}{2}-\frac{\alpha}{2}-3\gamma=(\beta-2)\cdot(2\gamma+\frac{\alpha-\beta}{2}+1)+\frac{\alpha-\beta}{2}+\gamma+2$.
We create a clique embedding $\psi$ from $K_{2X-1}$ to
$P(\alpha,\beta,\gamma\times 2)$ with $\operatorname{wed}(\psi)=X$, which
yields $\operatorname{clemb}(P(\alpha,\beta,\gamma\times
2))\geq\frac{2X-1}{X}=2-\frac{1}{X}$, as desired. We treat the paths
$a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline a_{\alpha}$ and
$b_{0}\leftrightline b_{1}\leftrightline\cdots\leftrightline b_{\beta}$ as a
cycle $\mathcal{C}$ of length $\alpha+\beta$. We use $6$ different types of
subgraphs that we embed into. See Figure 13.

  1. A.

We embed one node into each path of the form $a_{\ell}\leftrightline
a_{\ell+1}\leftrightline\cdots\leftrightline
a_{\ell+\frac{\alpha+\beta}{2}-2}$ for $\ell\in[\frac{\alpha-\beta}{2}+1]$.

  2. B.

We embed one node into the path $b_{\beta-1}\leftrightline
b_{\beta-2}\leftrightline\cdots\leftrightline b_{1}\leftrightline
a_{0}\leftrightline\cdots\leftrightline a_{\frac{\alpha-\beta}{2}}$.
Furthermore, we embed $2\gamma+\frac{\alpha-\beta}{2}+1$ nodes into each path
of the form $b_{\beta-\ell-1}\leftrightline
b_{\beta-\ell-2}\leftrightline\cdots\leftrightline b_{1}\leftrightline
a_{0}\leftrightline\cdots\leftrightline a_{\frac{\alpha-\beta}{2}+\ell}$ for
$\ell\in[\beta-2]$.

  3. C.

We embed $\gamma+1$ nodes into the path
$a_{\frac{\alpha-\beta}{2}+2}\leftrightline
a_{\frac{\alpha-\beta}{2}+3}\leftrightline\cdots\leftrightline a_{\alpha}$.
Furthermore, if $\beta\geq 4$, we embed $2\gamma+\frac{\alpha-\beta}{2}+1$
nodes into each path of the form
$a_{\frac{\alpha-\beta}{2}+\ell}\leftrightline
a_{\frac{\alpha-\beta}{2}+\ell+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline b_{\beta-1}\leftrightline\cdots\leftrightline
b_{\beta-\ell+2}$ for $\ell\in[3,\beta-1]$. Moreover, we embed
$\gamma+\frac{\alpha-\beta}{2}+1$ nodes into the path
$a_{\frac{\alpha+\beta}{2}}\leftrightline
a_{\frac{\alpha+\beta}{2}+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline b_{\beta-1}\leftrightline\cdots\leftrightline b_{2}$.

  4. D.

If $\alpha>\beta$, we embed one node into each path of the form
$a_{\frac{\alpha+\beta}{2}+\ell}\leftrightline
a_{\frac{\alpha+\beta}{2}+\ell+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline c_{1}\leftrightline a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\ell-1}$ for
$\ell\in[\frac{\alpha-\beta}{2}]$.

  5. E.

We embed one node into each path of the form $c_{\ell}\leftrightline
a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline
a_{\frac{\alpha-\beta}{2}}$ for $\ell\in[\gamma]$.

  6. F.

We embed one node into each path of the form
$a_{\frac{\alpha+\beta}{2}}\leftrightline
a_{\frac{\alpha+\beta}{2}+1}\leftrightline\cdots\leftrightline
a_{\alpha}\leftrightline c_{\ell}$ for $\ell\in[\gamma]$.

Figure 13: Illustration of the proof of Lemma 5.13. In addition to the
abstract situation of Lemma 5.13, the figure also shows the clique embedding
for $P(12,6,2,2)$.

We now analyze this construction. In total, we embed

$\displaystyle(\frac{\alpha-\beta}{2}+1)\cdot 1$ (A)
$\displaystyle+1+(\beta-2)\cdot(2\gamma+\frac{\alpha-\beta}{2}+1)$ (B)
$\displaystyle+(\gamma+1)+(\beta-3)\cdot(2\gamma+\frac{\alpha-\beta}{2}+1)+(\gamma+\frac{\alpha-\beta}{2}+1)$
(C) $\displaystyle+\frac{\alpha-\beta}{2}\cdot 1$ (D)
$\displaystyle+\gamma\cdot 1$ (E) $\displaystyle+\gamma\cdot 1$ (F)
$\displaystyle=2\cdot((\beta-2)\cdot(2\gamma+\frac{\alpha-\beta}{2}+1)+\frac{\alpha-\beta}{2}+\gamma+2)-1$

nodes, which is exactly the number of nodes in $K_{2X-1}$. It is clear that
all subgraphs into which we embed are connected. Next, we prove that all pairs
of these subgraphs touch. For every type from A to F we show that the paths of
this type touch each other and all later types.

  1. A.

All paths of type A start not later than node $a_{\frac{\alpha-\beta}{2}+1}$
and end not earlier than node $a_{\frac{\alpha+\beta}{2}-1}$. Note that
$\frac{\alpha-\beta}{2}+1<\frac{\alpha+\beta}{2}-1$ as $\beta\geq 3$. Thus,
all these paths contain all the nodes
$a_{\frac{\alpha-\beta}{2}+1},\ldots,a_{\frac{\alpha+\beta}{2}-1}$, and all
pairs of them touch. All paths of type B end not earlier than node
$a_{\frac{\alpha-\beta}{2}}$, so they touch all paths of type A on the edge
$\\{a_{\frac{\alpha-\beta}{2}},a_{\frac{\alpha-\beta}{2}+1}\\}$.
Symmetrically, all paths of type C start not later than
$a_{\frac{\alpha+\beta}{2}}$, so they all touch all paths of type A on the
edge $\\{a_{\frac{\alpha+\beta}{2}-1},a_{\frac{\alpha+\beta}{2}}\\}$. For any
fixed $\ell$, paths of types D (for $\ell=1$), E (for $\ell\in[\gamma]$), and
F (for $\ell\in[\gamma]$) lie on the cycle $a_{0}\leftrightline
a_{1}\leftrightline\cdots\leftrightline a_{\alpha}\leftrightline c_{\ell}$ of
length $\alpha+2$, which also contains all paths of type $A$. The paths of
types D, E, and F have length $\frac{\alpha-\beta}{2}+1$, while the paths of
type A have length $\frac{\alpha+\beta}{2}-2$. Thus, Lemma 5.5 implies that
all pairs of them touch.

  2. B.

All paths of type B go through node $a_{0}$, so all pairs of them touch. All
paths of type B lie on the cycle $\mathcal{C}$ of length $\alpha+\beta$
together with all paths of type C. Paths of type B have length
$\frac{\alpha+\beta}{2}-1$, and paths of type C have length
$\frac{\alpha+\beta}{2}-2$. Thus, Lemma 5.5 implies that each path of type B
and each path of type C touch. For any fixed $\ell$, paths of types D (for
$\ell=1$), E (for $\ell\in[\gamma]$), and F (for $\ell\in[\gamma]$) go through
node $c_{\ell}$, so they touch paths of type B on the edge
$\\{a_{0},c_{\ell}\\}$.

  3. C.

All paths of type C go through node $a_{\alpha}$, so all pairs of them touch.
For any fixed $\ell$, paths of types D (for $\ell=1$), E (for
$\ell\in[\gamma]$), and F (for $\ell\in[\gamma]$) go through node $c_{\ell}$,
so they touch paths of type C on the edge $\\{a_{\alpha},c_{\ell}\\}$.

  4. D-F.

Any path of type D, E, or F goes either through node $a_{0}$ or through node
$a_{\alpha}$. Any other such path goes through node $c_{\ell}$ for some
$\ell\in[\gamma]$. Hence, they touch either on the edge $\\{a_{0},c_{\ell}\\}$
or on the edge $\\{a_{\alpha},c_{\ell}\\}$.

We showed that all pairs of subgraphs we embed touch, so $\psi$ is a valid
clique embedding. It remains to show that all edges have weak edge depth at
most $X$. There are

$\displaystyle 1+(\beta-2)\cdot(2\gamma+\frac{\alpha-\beta}{2}+1)$ (B)
$\displaystyle+\frac{\alpha-\beta}{2}\cdot 1$ (D) $\displaystyle+\gamma\cdot
1$ (E) $\displaystyle=X-1$

embedded subgraphs that go through node $a_{0}$. Node $b_{1}$ is not contained
in any paths that $a_{0}$ is not contained in. Hence, weak edge depth of
$\\{a_{0},b_{1}\\}$ is equal to $X-1$. For all edges of the form
$\\{a_{0},c_{\ell}\\}$ for $\ell\in[\gamma]$, the only new path that
$c_{\ell}$ adds to the subgraphs that are already embedded into $a_{0}$ are
paths of type F, contributing one to weak edge depth of these edges. So each
edge $\\{a_{0},c_{\ell}\\}$ has weak edge depth $(X-1)+1=X$. The same holds
for the edge $\\{a_{0},a_{1}\\}$ as the only new path that $a_{1}$ adds to the
subgraphs that are already embedded into $a_{0}$ is the path of type A that
starts in $a_{1}$, which contributes one to weak edge depth of this edge. If
$\alpha>\beta$, whenever we now move from an edge $\\{a_{\ell},a_{\ell+1}\\}$
to an edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[0,\frac{\alpha-\beta}{2}-1]$, we lose a single path of type D that
ends in $a_{\ell}$, and we gain a single path of type A that starts in
$a_{\ell+2}$. Both have weight one, so weak edge depth remains at $X$. When we
move from the edge
$\\{a_{\frac{\alpha-\beta}{2}},a_{\frac{\alpha-\beta}{2}+1}\\}$ to the edge
$\\{a_{\frac{\alpha-\beta}{2}+1},a_{\frac{\alpha-\beta}{2}+2}\\}$, we lose a
single path of type B with weight one that ends in
$a_{\frac{\alpha-\beta}{2}}$ and all paths of type E with total weight
$\gamma$. At the same time we gain a single path of type C with weight
$\gamma+1$ that starts in node $a_{\frac{\alpha-\beta}{2}+2}$. In total, weak
edge depth of
$\\{a_{\frac{\alpha-\beta}{2}+1},a_{\frac{\alpha-\beta}{2}+2}\\}$ is again
$X$. Next, if $\beta\geq 4$, whenever we move from an edge
$\\{a_{\ell},a_{\ell+1}\\}$ to an edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[\frac{\alpha-\beta}{2}+1,\frac{\alpha+\beta}{2}-3]$, we lose a single
path of type B with weight $2\gamma+\frac{\alpha-\beta}{2}+1$ that ends in
node $a_{\ell}$ and gain a single path of type C with weight
$2\gamma+\frac{\alpha-\beta}{2}+1$ that starts in node $a_{\ell+2}$, so weak
edge depth remains at $X$. When we move from the edge
$\\{a_{\frac{\alpha+\beta}{2}-2},a_{\frac{\alpha+\beta}{2}-1}\\}$ to the edge
$\\{a_{\frac{\alpha+\beta}{2}-1},a_{\frac{\alpha+\beta}{2}}\\}$, we lose a
single path of type B with weight $2\gamma+\frac{\alpha-\beta}{2}+1$ that ends
in node $a_{\frac{\alpha+\beta}{2}-2}$. We gain a path of type C with weight
$\gamma+\frac{\alpha-\beta}{2}+1$ that starts in node
$a_{\frac{\alpha+\beta}{2}}$ and all paths of type F with total weight
$\gamma$. Hence, weak edge depth of
$\\{a_{\frac{\alpha+\beta}{2}-1},a_{\frac{\alpha+\beta}{2}}\\}$ is again $X$.
Now, if $\alpha>\beta$, whenever we move from an edge
$\\{a_{\ell},a_{\ell+1}\\}$ to an edge $\\{a_{\ell+1},a_{\ell+2}\\}$ for
$\ell\in[\frac{\alpha+\beta}{2}-1,\alpha-2]$, we lose a single path of type A
that ends in node $a_{\ell}$ and gain a single path of type D that starts in
node $a_{\ell+2}$. Both of them have weight one, so weak edge depth of the
current edge remains at $X$. If we move from the edge
$\\{a_{\alpha-1},a_{\alpha}\\}$ to an edge $\\{a_{\alpha},c_{\ell}\\}$ for
$\ell\in[\gamma]$, we lose a single path of type A that ends in $a_{\alpha-1}$
and gain a single path of type E that starts in $c_{\ell}$, so each such edge
has weak edge depth $X$. When we move from the edge
$\\{a_{\alpha-1},a_{\alpha}\\}$ to the edge $\\{b_{\beta},b_{\beta-1}\\}$, we
lose a single path of type A with weight one that ends in $a_{\alpha-1}$ and
gain a single path of type B with weight one that starts in $b_{\beta-1}$, so
weak edge depth of $\\{b_{\beta},b_{\beta-1}\\}$ is $X$. Now when we move from
the edge $\\{b_{\beta},b_{\beta-1}\\}$ to the edge
$\\{b_{\beta-1},b_{\beta-2}\\}$, we lose a single path of type C with weight
$\gamma+1$ that ends in node $b_{\beta}$ and all paths of types D and F of
total weight $\frac{\alpha-\beta}{2}+\gamma$. At the same time we gain a
single path of type B with weight $2\gamma+\frac{\alpha-\beta}{2}+1$ that
starts in node $b_{\beta-2}$. In total weak edge depth remains at $X$. Now if
$\beta\geq 4$, whenever we move from an edge $\\{b_{\ell+2},b_{\ell+1}\\}$ to
an edge $\\{b_{\ell+1},b_{\ell}\\}$ for $\ell\in[\beta-3]$, we lose a single
path of type C with weight $2\gamma+\frac{\alpha-\beta}{2}+1$ that ends in
$b_{\ell+2}$, and we gain a single path of type B with the same weight that
starts in node $b_{\ell}$, so weak edge depth of the current edge remains at
$X$. This way we checked that weak edge depth of every edge is at most $X$,
which concludes the proof of the fact that $\operatorname{wed}(\psi)=X$.

######  Lemma 5.15.

For $\alpha\geq\beta\geq 3$ and $\gamma\geq 1$, we have
$\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq
2-1/\mathcal{F}(\alpha,\beta,\gamma)$.

######  Proof 5.16.

We consider all the cases from the definition of $\mathcal{F}$.

  1. 1.

$\mathcal{F}(\alpha,\beta,\gamma)=2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{\beta}{2}-\frac{\alpha}{2}-2\gamma+2$,
$\alpha+\beta$ is even, $\alpha>\beta$, and $\beta<\gamma+2$. As
$\alpha>\beta$ in this case, we have $\alpha-1\geq\beta$. Furthermore, as
$\alpha+\beta$ is even, $(\alpha-1)+\beta$ is odd. Finally,
$P(\alpha-1,\beta,\gamma\times 2)$ is an induced minor of
$P(\alpha,\beta,\gamma\times 2)$. Hence, due to Lemma 2.7 and Lemma 5.11, we
obtain

$\displaystyle\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))$
$\displaystyle\geq\operatorname{clemb}(P(\alpha-1,\beta,\gamma\times 2))$
$\displaystyle\geq
2-1/(2\beta\gamma+\frac{(\alpha-1)\beta}{2}-\frac{\beta^{2}}{2}+\beta-\frac{\alpha-1}{2}-2\gamma+\frac{3}{2})$
$\displaystyle=2-1/(2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{\beta}{2}-\frac{\alpha}{2}-2\gamma+2)$
$\displaystyle=2-1/\mathcal{F}(\alpha,\beta,\gamma).$

  2. 2.

$\mathcal{F}(\alpha,\beta,\gamma)=2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{3\beta}{2}-\frac{\alpha}{2}-3\gamma$,
$\alpha+\beta$ is even, $3\beta<\alpha+6\gamma+8$, and ($\alpha=\beta$ or
$\beta\geq\gamma+2$). Follows from Lemma 5.13.

  3. 3.

$\mathcal{F}(\alpha,\beta,\gamma)=2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+3\beta-\alpha-6\gamma-4$,
$\alpha+\beta$ is even, $2\beta\leq\alpha+4\gamma+6$, and
$3\beta\geq\alpha+6\gamma+8$. In this case
$3\beta\geq\alpha+6\gamma+8\geq\beta+6\gamma+8$, so
$\alpha>\beta-1\geq(3\gamma+4)-1\geq 5$. Furthermore, as $\alpha+\beta$ is
even, $\alpha+(\beta-1)$ is odd. Finally, $P(\alpha,\beta-1,\gamma\times 2)$
is an induced minor of $P(\alpha,\beta,\gamma\times 2)$. Hence, due to Lemma
2.7 and Lemma 5.9, we obtain

$\displaystyle\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))$
$\displaystyle\geq\operatorname{clemb}(P(\alpha,\beta-1,\gamma\times 2))$
$\displaystyle\geq
2-1/(2(\beta-1)\gamma+\frac{\alpha(\beta-1)}{2}-\frac{(\beta-1)^{2}}{2}+2(\beta-1)-\frac{\alpha}{2}-4\gamma-\frac{3}{2})$
$\displaystyle=2-1/(2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+3\beta-\alpha-6\gamma-4)$
$\displaystyle=2-1/\mathcal{F}(\alpha,\beta,\gamma).$

  4. 4.

$\mathcal{F}(\alpha,\beta,\gamma)=2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\beta-\frac{\alpha}{2}-2\gamma+\frac{3}{2}$,
$\alpha+\beta$ is odd, and $\beta<2\gamma+3$. Follows from Lemma 5.11.

  5. 5.

$\mathcal{F}(\alpha,\beta,\gamma)=2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+2\beta-\frac{\alpha}{2}-4\gamma-\frac{3}{2}$,
$\alpha+\beta$ is odd, $2\beta\leq\alpha+4\gamma+6$, and $\beta\geq
2\gamma+3$. This case follows from Lemma 5.9 as $\beta\geq 2\gamma+3\geq 5$.

  6. 6.

$\mathcal{F}(\alpha,\beta,\gamma)=2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2}$,
$\alpha=0\bmod 4$, and $2\beta>\alpha+4\gamma+6$. Here we consider all cases
$6$ through $8$ together. Define $x\coloneqq(((\alpha-1)\bmod 4)+3)/2$. Denote
$\beta^{\prime}\coloneqq\frac{\alpha}{2}+2\gamma+x$. It is easy to see that
$\beta^{\prime}$ is an integer. Furthermore,
$2\alpha+2\beta^{\prime}=2\alpha+\alpha+4\gamma+(\alpha-1)+3=2\bmod 4$, hence
$\alpha+\beta^{\prime}$ is odd. Moreover, we have
$\beta^{\prime}=\frac{\alpha}{2}+2\gamma+x\geq\frac{3}{2}+2+\frac{3}{2}=5$.
Furthermore, $\beta^{\prime}<\beta\leq\alpha$ because $x\leq 3$ and
$2\beta>\alpha+4\gamma+6$ by case assumption, and thus
$P(\alpha,\beta^{\prime},\gamma\times 2)$ is an induced minor of
$P(\alpha,\beta,\gamma\times 2)$. Hence, due to Lemma 2.7 and Lemma 5.9, we
obtain

$\displaystyle\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))$
$\displaystyle\geq\operatorname{clemb}(P(\alpha,\beta^{\prime},\gamma\times
2))$ $\displaystyle\geq
2-1/(2\beta^{\prime}\gamma+\frac{\alpha\beta^{\prime}}{2}-\frac{\beta^{\prime
2}}{2}+2\beta^{\prime}-\frac{\alpha}{2}-4\gamma-\frac{3}{2})$
$\displaystyle=2-1/(2(\frac{\alpha}{2}+2\gamma+x)\gamma+\frac{\alpha(\frac{\alpha}{2}+2\gamma+x)}{2}-\frac{(\frac{\alpha}{2}+2\gamma+x)^{2}}{2}$
$\displaystyle+2(\frac{\alpha}{2}+2\gamma+x)-\frac{\alpha}{2}-4\gamma-\frac{3}{2})$
$\displaystyle=2-1/(2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2}+(2x-\frac{x^{2}}{2}-\frac{3}{2}))$
$\displaystyle=2-1/\mathcal{F}(\alpha,\beta,\gamma),$

where the last inequality can be checked for each value of $\alpha\bmod 4$.

    1. (a)

$\alpha=0\bmod 4$. In this case $x=(3+3)/2=3$. Hence,
$2x-\frac{x^{2}}{2}-\frac{3}{2}=0$.

    2. (b)

$\alpha=1\bmod 4$. In this case $x=(0+3)/2=3/2$. Hence,
$2x-\frac{x^{2}}{2}-\frac{3}{2}=3/8$.

    3. (c)

$\alpha=2\bmod 4$. In this case $x=(1+3)/2=2$. Hence,
$2x-\frac{x^{2}}{2}-\frac{3}{2}=1/2$.

    4. (d)

$\alpha=3\bmod 4$. In this case $x=(2+3)/2=5/2$. Hence,
$2x-\frac{x^{2}}{2}-\frac{3}{2}=3/8$.

  7. 7.

$\mathcal{F}(\alpha,\beta,\gamma)=2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2}+\frac{3}{8}$,
$\alpha$ is odd, and $2\beta>\alpha+4\gamma+6$. See case $6$.

  8. 8.

$\mathcal{F}(\alpha,\beta,\gamma)=2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2}+\frac{1}{2}$,
$\alpha=2\bmod 4$, and $2\beta>\alpha+4\gamma+6$. See case $6$.

###  5.3 Proof of Lemma 2.11

Now we can put the pieces together to prove Lemma 2.11.

See 2.11

######  Proof 5.17 (Proof of Lemma 2.11).

Let $(\alpha,\beta,\gamma)\in\mathcal{P}^{\prime}$.

For $(\alpha,\beta,\gamma)=(1,0,0)$, we have
$\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq 1=2-1/1$ by Lemma
5.1 and $\mathcal{F}(\alpha,\beta,\gamma)=1$ by Lemma 8.3. For
$(\alpha,\beta,\gamma)=(2,1,0)$, we have
$\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq 2-1/2$ by Lemma 5.3
and $\mathcal{F}(\alpha,\beta,\gamma)=2$ by Lemma 8.5. For
$(\alpha,\beta,\gamma)=(k-2,2,0)$ with $k\geq 4$, we have
$\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq 2-1/\left\lceil
k/2\right\rceil$ by Lemma 5.3 and
$\mathcal{F}(\alpha,\beta,\gamma)=\left\lceil k/2\right\rceil$ by Lemma 8.15.

Otherwise, we have $\alpha\geq\beta\geq 2$ and $\gamma\geq 1$. If
$\alpha=\beta=2$, then we have
$\operatorname{clemb}(P(\alpha,\beta,\gamma\times 2))\geq 2-1/(\gamma+2)$ by
Lemma 5.4 and $\mathcal{F}(\alpha,\beta,\gamma)=\gamma+2$ by Lemma 8.17. If
$\alpha>\beta=2$, then we have
$\mathcal{F}(\alpha,\beta,\gamma)=2\gamma+2+\left\lfloor\frac{\alpha-1}{2}\right\rfloor$
by Lemma 8.19, and Lemma 5.7 proves the desired inequality. Finally, if
$\alpha\geq\beta\geq 3$, then Lemma 5.15 implies the desired inequality. This
covers all $(\alpha,\beta,\gamma)\in\mathcal{P}^{\prime}$.

##  6 Algorithms: from General Case to Family $\mathcal{P}$

In this section we prove Lemmas 2.14, 2.15, 2.16 and 2.18. This covers most of
the claims from Section 2.2, except for Lemma 2.19 whose proof is postponed to
Section 7.

We start by presenting a reduction to tree patterns.

######  Lemma 6.1.

Let $H$ be a pattern. There is an algorithm that, given a (weighted) $m$-edge
host graph $G$ and a partial $H$-encoding $\mathcal{E}$ of size $s$, in time
$\mathcal{O}(m+s)$ computes a tree $T^{\prime}$ and a (weighted) host graph
$G^{\prime}$ for pattern $T^{\prime}$ such that there is a (weight-preserving)
bijection between $H$-subgraphs of $G$ encoded by $\mathcal{E}$ and
$T^{\prime}$-subgraphs of $G^{\prime}$. Furthermore, given any
$T^{\prime}$-subgraph of $G^{\prime}$, the corresponding $H$-subgraph of $G$
can be computed in constant time.

######  Proof 6.2.

It suffices to proof the weighted setting, as the unweighted setting follows
by setting all weights to zero. Recall that a partial encoding $\mathcal{E}$
consists of a tree decomposition $\mathcal{T}$, which consists of a tree $T$
together with bags $B(v)$ for each node $v$ of $T$, as well as a
submaterialization $S_{B(v)}$ for every bag $B(v)$ of $\mathcal{T}$.

We start by filtering submaterializations in time $\mathcal{O}(s)$. For each
bag $B$ of $\mathcal{T}$, we remove all $\overline{v}\in S_{B}$ such that
$\overline{v}$ does not form an $H[B]$-subgraph in $G[H[B]]$. Note that the
filtered partial $H$-encoding encodes exactly the same $H$-subgraphs as before
the filtering. Indeed, if $\overline{v}\in S_{B}$ does not form an
$H[B]$-subgraph in $G[H[B]]$, it cannot be a projection of any $H$-subgraph in
$G$ onto $B$.

We construct the new pattern $T^{\prime}$ by subdividing every edge of $T$,
i.e., we let $T^{\prime}\coloneqq(V(T)\cup E(T),\\{\\{a,e\\}\mid e\in
E(T),a\in e\\})$. Clearly, $T^{\prime}$ is a tree and a pattern.

For any edge $e=\\{a,b\\}\in E(T)$, let $B(e)\coloneqq B(a)\cap B(b)$ and
$S_{B(e)}\coloneqq\left.S_{B(a)}\right|_{B(e)}\cup\left.S_{B(b)}\right|_{B(e)}$.
With this notation, we construct the nodes of the new host graph $G^{\prime}$
as follows. For every $a\in V(T)$, we let $V^{\prime}_{a}\coloneqq S_{B(a)}$
be the part of $G^{\prime}$ corresponding to $a$. For every $e\in E(T)$, we
let $V^{\prime}_{e}\coloneqq S_{B(e)}$ be the part of $G^{\prime}$
corresponding to $e$.

The edges of $G^{\prime}$ simply encode projections: For every $\\{a,e\\}\in
E(T^{\prime})$, we let the edges between $V^{\prime}_{a}$ and $V^{\prime}_{e}$
be $\\{\\{v_{a},\left.v_{a}\right|_{B(e)}\\}\mid v_{a}\in S_{B(a)}\\}$.

We next define the edge weights. Note that, by the definition of a tree
decomposition, for every edge $e^{\prime}=\\{x,y\\}\in E(H)$ there is some
node $a\in T$ with $x,y\in B(a)$. We pick any such node $a$ and an arbitrary
edge $e\in E(T)$ incident to $a$ and denote
$\varphi(e^{\prime})\coloneqq\\{a,e\\}$. We define the edge weights in
$G^{\prime}$ by

$w^{\prime}(\\{v_{a},\left.v_{a}\right|_{B(e)}\\})\coloneqq\sum_{\\{x,y\\}\in
E(H):\,\varphi(\\{x,y\\})=\\{a,e\\}}w(\\{\left.v_{a}\right|_{x},\left.v_{a}\right|_{y}\\}).$

We now show how to build $G^{\prime}$ in time $\mathcal{O}(m+s)$. We can build
$V^{\prime}_{a}$ for each $a\in V(T)$ trivially in time
$\mathcal{O}(|S_{B(a)}|)=\mathcal{O}(s)$. To build $V^{\prime}_{e}$ for each
$e=\\{a,b\\}\in E(T)$, we first project $S_{B(a)}$ and $S_{B(b)}$ onto $B(e)$
in time $\mathcal{O}(s)$ and unite the two sequences. The resulting sequence
is $S_{B(e)}$ but with repetitions. To delete repetitions, we sort the
sequence lexicographically in time $\mathcal{O}(m+s)$ using radix sort. By
remembering throughout this process for each element of $S_{B(e)}$ from which
elements of $S_{B(a)}$ and $S_{B(b)}$ it was created through projection, we
can build edges between $V^{\prime}_{a}$ and $V^{\prime}_{e}$ and between
$V^{\prime}_{b}$ and $V^{\prime}_{e}$ in time $\mathcal{O}(s)$. To compute the
edge weights $w^{\prime}$ of edges between $V^{\prime}_{a}$ and
$V^{\prime}_{e}$ for each $\\{a,e\\}\in E(T^{\prime})$, we iterate over
$\\{x,y\\}\in E(H)$, and if $\varphi(\\{x,y\\})=\\{a,e\\}$, we add the
corresponding weights from $G$ to $G^{\prime}$. For a fixed $\\{x,y\\}\in
E(H)$ with $\varphi(\\{x,y\\})=\\{a,e\\}$, we first sort edges between $V_{x}$
and $V_{y}$ in $G$ in time $\mathcal{O}(m)$ using radix sort. Note that
$x,y\in B(a)$ holds by the definition of $\varphi$. We then use radix sort to
lexicographically sort $V^{\prime}_{a}$ in time $\mathcal{O}(m+s)$ where $x$
and $y$ come first in the ordering of $B(a)$ according to which we sort
lexicographically. We then use two pointers to go through all $v_{a}\in
V^{\prime}_{a}$ and corresponding edges
$\\{\left.v_{a}\right|_{x},\left.v_{a}\right|_{y}\\}$. We then add
$w(\\{\left.v_{a}\right|_{x},\left.v_{a}\right|_{y}\\})$ to the weight
$w^{\prime}$ of the edge $\\{v_{a},\left.v_{a}\right|_{B(e)}\\}$, which is the
single outgoing edge from $v_{a}$ to $V^{\prime}_{e}$. Thus, in time
$\mathcal{O}(m+s)$ we build $G^{\prime}$.

We now prove that there is a weight-preserving bijection between $H$-subgraphs
of $G$ encoded by $\mathcal{E}$ and $T^{\prime}$-subgraphs of $G^{\prime}$.
Fix some $H$-subgraph $\overline{v}$ of $G$ encoded by $\mathcal{E}$. Let
$I(\overline{v})\coloneqq\overline{v}^{\prime}\coloneqq(\left.\overline{v}\right|_{B(a)})_{a\in
V(T^{\prime})}$. We claim that $\overline{v}^{\prime}$ is a
$T^{\prime}$-subgraph in $G^{\prime}$ with the same weight as the $H$-subgraph
$\overline{v}$ in $G$. The fact that $\overline{v}^{\prime}$ is a
$T^{\prime}$-subgraph in $G^{\prime}$ follows from the definition of
$G^{\prime}$. The weight is preserved as for every edge $\\{x,y\\}\in E(H)$,
there is exactly one edge $\\{a,e\\}\in E(T^{\prime})$, such that the weights
of edges between $V_{x}$ and $V_{y}$ are encoded on the edges between
$V^{\prime}_{a}$ and $V^{\prime}_{e}$.

Furthermore, if $\overline{u}$ is some other $H$-subgraph of $G$ encoded by
$\mathcal{E}$, there is some $x\in V(H)$ such that $v_{x}\neq u_{x}$. There is
some node $a\in V(T)$ such that $x\in B(a)$, and thus $I(\overline{v})_{x}\neq
I(\overline{u})_{x}$. Hence, $I$ is an injection.

It remains to show that $I$ is a surjection and how to compute $I^{-1}$ in
constant time. Fix some $T^{\prime}$-subgraph $\overline{v}^{\prime}$ of
$G^{\prime}$. For each $x\in V(H)$, fix some node $\nu(x)\in V(T)$ such that
$x\in B(\nu(x))$. Let
$\overline{v}\coloneqq(\left.v^{\prime}_{\nu(x)}\right|_{x})_{x\in V(H)}$. It
is clear that $\overline{v}$ can be computed from $\overline{v}^{\prime}$ in
constant time. We claim that $\overline{v}$ is an $H$-subgraph of $G$ encoded
by $\mathcal{E}$ and $I(\overline{v})=\overline{v}^{\prime}$. First, we claim
that $v_{x}=\left.v^{\prime}_{a}\right|_{x}$ for any $a\in V(T^{\prime})$ with
$x\in B(a)$. That is, the definition of $\overline{v}$ does not depend on the
specific choice of nodes $\nu(x)$. Note that as $T$ corresponds to some tree
decomposition of $H$, nodes $a\in V(T)$ with $x\in B(a)$ form a connected
subgraph of $T$. After subdivision this fact still holds. That is, nodes $a\in
V(T^{\prime})$ with $x\in B(a)$ form a connected subgraph of $T^{\prime}$. For
any two such adjacent nodes $a,b\in V(T^{\prime})$, by the definition of
$G^{\prime}$, we have
$\left.v^{\prime}_{a}\right|_{x}=\left.v^{\prime}_{b}\right|_{x}$ as
$v^{\prime}_{a}$ and $v^{\prime}_{b}$ are adjacent in $G^{\prime}$ and edges
in $G^{\prime}$ are projections. Hence, by transitivity we get
$\left.v^{\prime}_{a}\right|_{x}=\left.v^{\prime}_{\nu(x)}\right|_{x}=v_{x}$.
From this, it follows that $I(\overline{v})=\overline{v}^{\prime}$.
Furthermore, we claim that $\overline{v}$ is an $H$-subgraph in $G$. For each
$\\{x,y\\}\in E(H)$, by the definition of a tree decomposition there is some
$a\in V(T)$ with $x,y\in B(a)$. As
$\left.\overline{v}\right|_{B(a)}=v^{\prime}_{a}\in S_{B(a)}$, we have that
$\left.\overline{v}\right|_{B(a)}$ forms an $H[B(a)]$-subgraph in $G[H[B(a)]]$
as we initially have filtered out all elements of $S_{B(a)}$ that do not form
$H[B(a)]$-subgraphs in $G[H[B(a)]]$. In particular, we have
$\\{v_{x},v_{y}\\}\in E(G)$ as $x,y\in B(a)$. As this holds for each
$\\{x,y\\}\in E(H)$, we get that $\overline{v}$ is indeed an $H$-subgraph in
$G$. Finally, for each $a\in V(T)$, we have
$\left.\overline{v}\right|_{B(a)}=v^{\prime}_{a}\in S_{B(a)}$, and thus
$\overline{v}$ is encoded by $\mathcal{E}$. This concludes the proof of the
fact that $\overline{v}$ is an $H$-subgraph of $G$ encoded by $\mathcal{E}$
and $I(\overline{v})=\overline{v}^{\prime}$, thus proving that $I$ is a
surjection.

See 2.14

######  Proof 6.3 (Proof of Lemma 2.14).

For the first claim, we first solve $H$-Encoding on $G$ in time $T(m)$, which
returns an $H$-encoding consisting of partial $H$-encodings
$\mathcal{E}_{1},\mathcal{E}_{2},\ldots,\mathcal{E}_{k}$. Recall that $k$ must
be constant, i.e., it may depend on $H$ but not on $G$. Since the running time
is $T(m)$, each partial $H$-encoding has size $\mathcal{O}(T(m))$. For each
partial encoding $\mathcal{E}_{i}$, we apply Lemma 6.1 to build a tree
$H^{\prime}_{i}$ and a host graph $G^{\prime}_{i}$ for pattern
$H^{\prime}_{i}$. We solve Min-Weight-$H^{\prime}_{i}$-Subgraph on
$G^{\prime}_{i}$ in linear time as $H^{\prime}_{i}$ is a tree. This yields a
weight for each $i$, and we return the minimum of all these weights.

Since $\mathcal{E}_{1},\mathcal{E}_{2},\ldots,\mathcal{E}_{k}$ is a full
$H$-encoding, the minimum-weight $H$-subgraph of $G$ is encoded by some
partial encoding $\mathcal{E}_{i}$, and by the weight-preserving property of
Lemma 6.1 we obtain the same minimum weight by solving Min-
Weight-$H^{\prime}_{i}$-Subgraph on $G^{\prime}_{i}$. This proves correctness.
The running time of this algorithm is $\mathcal{O}(T(m))$ as $k$ is constant.

The second claim of the lemma follows similarly. We apply Lemma 6.1 (in the
unweighted setting) to each $\mathcal{E}_{i}$. Since $H^{\prime}_{i}$ is a
tree, we can then solve $H^{\prime}_{i}$-Listing on $G^{\prime}_{i}$ in time
$\mathcal{O}(T(m)+t_{i})$ where $t_{i}$ is the number of $H$-subgraph of $G$
encoded by $\mathcal{E}_{i}$ (see, e.g., [15]). By the definition of a full
$H$-encoding, we have $\sum_{i}t_{i}=t$, and thus in total we work in time
$\mathcal{O}(T(m)+t)$. Each $H^{\prime}_{i}$-subgraph of $G^{\prime}_{i}$ can
be converted into an $H$-subgraph of $G$ in constant time.

It remains to show the third claim of the lemma. In the preprocessing phase we
solve $H$-Encoding on $G$ in time $\mathcal{O}(T(m))$ and apply Lemma 6.1 to
each $\mathcal{E}_{i}$ to build corresponding instances $G^{\prime}_{i}$ of
$H^{\prime}_{i}$-Enumeration. Since $H^{\prime}_{i}$ is a tree,
$H^{\prime}_{i}$-Enumeration can be solved in preprocessing time
$\mathcal{O}(|E(G^{\prime}_{i})|)=\mathcal{O}(T(m))$ and constant delay for
each $i$ (see, e.g., [15]). Thus, the preprocessing takes time
$\mathcal{O}(T(m))$ in total.

To enumerate the next $H$-subgraph of $G$, we pick any $i$ such that we did
not yet enumerate all $H^{\prime}_{i}$-subgraphs in $G^{\prime}_{i}$ and ask
$H^{\prime}_{i}$-Enumeration to generate a new $H^{\prime}_{i}$-subgraph of
$G^{\prime}_{i}$. This takes constant delay. Then, in constant time we can
convert the computed $H^{\prime}_{i}$-subgraph of $G^{\prime}_{i}$ into an
$H$-subgraph of $G$. As
$\mathcal{E}_{1},\mathcal{E}_{2},\ldots,\mathcal{E}_{k}$ are a full
$H$-encoding, every $H$-subgraph of $G$ is enumerated exactly once. Hence, we
obtain constant-time delay.

See 2.15

######  Proof 6.4 (Proof of Lemma 2.15).

Given a host graph $G^{\prime}$ for $H^{\prime}$-Encoding, we apply Lemma 4.8
(in the unweighted setting) to build a host graph $G$ for $H$-Encoding in time
$\mathcal{O}(m)$. Given $G$, we solve $H$-Encoding in time
$\mathcal{O}(T(m))$. As a result, we get a full $H$-encoding of $G$ consisting
of partial $H$-encodings
$\mathcal{E}_{1},\mathcal{E}_{2},\ldots,\mathcal{E}_{k}$ of $G$. There is a
bijection $I$ between $H$-subgraphs in $G$ and $H^{\prime}$-subgraphs in
$G^{\prime}$. We will create partial $H^{\prime}$-encodings
$\mathcal{E}^{\prime}_{1},\ldots,\mathcal{E}^{\prime}_{k}$ of $G^{\prime}$,
such that $\mathcal{E}^{\prime}_{i}$ encodes exactly the
$H^{\prime}$-subgraphs of $G^{\prime}$ corresponding to the $H$-subgraphs of
$G$ that are encoded by $\mathcal{E}_{i}$, which solves the problem.

Fix some partial encoding $\mathcal{E}_{i}$. Given its underlying tree
decomposition $\mathcal{T}$ of $H$, we can create a tree decomposition
$\mathcal{T}^{\prime}$ of $H^{\prime}$ by preserving the tree structure of
$\mathcal{T}$, and for each bag $B$ of $\mathcal{T}$ creating a bag
$\varphi^{-1}(B)\coloneqq\\{x\in V(H^{\prime})\mid\varphi(x)\cap
B\neq\emptyset\\}$ in $\mathcal{T}^{\prime}$, where $\varphi$ is taken from
the proof of Lemma 4.8. Consider the bijection $I$ (and its inverse $I^{-1}$)
between $H$-subgraphs of $G$ and $H^{\prime}$-subgraphs of $G^{\prime}$ from
Lemma 4.8, and denote the submaterializations of $\mathcal{E}_{i}$ by $S_{B}$,
for each bag $B$ of $\mathcal{T}$. Fix some $\overline{u}\in S_{B}$. For each
$x\in\varphi^{-1}(B)$, pick some $a\in\varphi(x)\cap B$. Let $j$ be such that
$u_{a}=v_{a,j}$. Denote $u^{\prime}_{x}=v^{\prime}_{x,j}$. Similarly to Lemma
4.8, one can see that the definition of $u^{\prime}_{x}$ does not depend on
the choice of $a$. Define
$I^{-1}(\overline{u})\coloneqq(u^{\prime}_{x})_{x\in\varphi^{-1}(B)}$. We
define the submaterialization of bag $\varphi^{-1}(B)$ by setting
$S^{\prime}_{\varphi^{-1}(B)}\coloneqq\\{I^{-1}(\overline{u})\mid\overline{u}\in
S_{B}\\}$. As the algorithm for $H$-Encoding works in time
$\mathcal{O}(T(m))$, all submaterializations of $\mathcal{E}_{i}$ have size at
most $\mathcal{O}(T(m))$. Thus, creating $S^{\prime}_{\varphi^{-1}(B)}$ takes
time $\mathcal{O}(|S_{B}|)=\mathcal{O}(T(m))$.

We now prove that the constructed $\mathcal{E}^{\prime}_{i}$ is a partial
$H^{\prime}$-encoding. First, we prove that $\mathcal{T}^{\prime}$ is a tree
decomposition of $H^{\prime}$. Consider any edge $\\{x,y\\}\in E(H^{\prime})$.
As $H^{\prime}$ is an induced minor of $H$, there is an edge $\\{a,b\\}\in
E(H)$ such that $a\in\varphi(x)$ and $b\in\varphi(y)$. There is a bag $B$ of
$\mathcal{T}$ that contains $a$ and $b$. Hence, $\varphi^{-1}(B)$ contains $x$
and $y$.

Now consider some $x\in V(H^{\prime})$. Note that $x$ is contained in exactly
the bags $\varphi^{-1}(B)$ of $\mathcal{T}^{\prime}$, for which
$\varphi(x)\cap B\neq\emptyset$. Note that $\varphi(x)$ is a connected subset
of nodes of $H$. Nodes from a connected subset of nodes of $H$ lie in the bags
of a connected subtree of the tree decomposition $\mathcal{T}$ of $H$.
Therefore, $x$ lies in the bags of a connected subtree of
$\mathcal{T}^{\prime}$. Hence, $\mathcal{T}^{\prime}$ is a tree decomposition
of $H^{\prime}$. Furthermore, for each bag $B$ of $\mathcal{T}$, it is clear
that $S^{\prime}_{\varphi^{-1}(B)}$ is a submaterialization of
$\varphi^{-1}(B)$. Therefore, $\mathcal{E}^{\prime}_{i}$ is a partial
$H^{\prime}$-encoding.

It remains to show that $\mathcal{E}^{\prime}_{i}$ encodes exactly the
$H^{\prime}$-subgraphs of $G^{\prime}$ that correspond to the $H$-subgraphs of
$G$ encoded by $\mathcal{E}_{i}$. Consider some $H$-subgraph $\overline{u}$ in
$G$ encoded by $\mathcal{E}_{i}$. We have $\left.\overline{u}\right|_{B}\in
S_{B}$ for all bags $B$ of $\mathcal{T}$. By the definition of
$S^{\prime}_{\varphi^{-1}(B)}$, we have that
$I^{-1}(\left.\overline{u}\right|_{B})\in S^{\prime}_{\varphi{-1}(B)}$. As
$I^{-1}(\left.\overline{u}\right|_{B})=\left.I^{-1}(\overline{u})\right|_{\varphi^{-1}(B)}$,
we have that $\mathcal{E}^{\prime}_{i}$ encodes $I^{-1}(\overline{u})$.
Furthermore, if $\mathcal{E}^{\prime}_{i}$ encodes some $H^{\prime}$-subgraph
$\overline{u}^{\prime}$ of $G^{\prime}$, we have
$I(\left.\overline{u}^{\prime}\right|_{\varphi^{-1}(B)})\in S_{B}$ for all
bags $B$ of $\mathcal{T}$, and as
$I(\left.\overline{u}^{\prime}\right|_{\varphi^{-1}(B)})=\left.I(\overline{u}^{\prime})\right|_{B}$,
we have that $I(\overline{u}^{\prime})$ is encoded by $\mathcal{E}_{i}$.

See 2.16

######  Proof 6.5.

For the given host graph $G$, for each $i\in[k]$ solve $H[S_{i}\cup
C]$-Encoding on $G[H[S_{i}\cup C]]$ to obtain an encoding
$\mathcal{E}_{i,1},\ldots,\mathcal{E}_{i,k_{i}}$. We now consider all
combinations of partial $H[S_{i}\cup C]$-encodings over all $i\in[k]$, i.e.,
we consider all tuples $(\mathcal{E}_{1,i_{1}},\ldots,\mathcal{E}_{k,i_{k}})$
with $i_{j}\in\\{1,\ldots,k_{j}\\}$ for all $j\in\\{1,\ldots,k\\}$. Note that
there is a constant number of such combinations. By Lemma 3.1 and since $C$ is
a clique, each tree decomposition of each partial $H[S_{i}\cup C]$-encodings
has a bag that contains $C$. We connect such a bag from the tree decomposition
of $\mathcal{E}_{1,i_{1}}$ with the corresponding bags from the tree
decompositions of $\mathcal{E}_{2,i_{2}},\ldots,\mathcal{E}_{k,i_{k}}$.
Observe that this yields a tree decomposition of $H$. We preserve the already
created submaterializations of all bags, thus creating a partial $H$-encoding
of $G$. Note that any $H$-subgraph $\overline{v}$ of $G$ is encoded exactly
once, as for each of $H[S_{i}\cup C]$ we have that
$\left.\overline{v}\right|_{S_{i}\cup C}$ is encoded exactly once in the
solution of $H[S_{i}\cup C]$-Encoding, thus only the combination corresponding
to all such partial $H[S_{i}\cup C]$-encodings encodes $\overline{v}$.

We now analyze the time complexity. Running the algorithm of $H[S_{i}\cup
C]$-Encoding for all $i\in[k]$ takes time $\mathcal{O}(T(m)\cdot
k)=\mathcal{O}(T(m))$. As these algorithms work in time $\mathcal{O}(T(m))$,
all partial encodings have size $\mathcal{O}(T(m))$. Hence, combining the
partial encodings takes time $\mathcal{O}(T(m))$.

See 2.18

######  Proof 6.6 (Proof of Corollary 2.18).

We prove the lemma by induction on $|V(H)|$. If $H$ does not have a clique
separator, then $D(H)=\\{H\\}$, and the claim is obvious. Otherwise, there is
some minimal clique separator $C$ in $H$. Let $S_{1},S_{2},\ldots,S_{k}$ be
the connected components of $H-C$. Note that by Lemma 1.4, we have
$D(H[S_{i}\cup C])\subseteq D(H)$ for each $i$. Hence, for each $H^{\prime}\in
D(H[S_{i}\cup C])$, $H^{\prime}$-Encoding can be solved in time
$\mathcal{O}(T(m))$. Consequently, by the induction hypothesis, $H[S_{i}\cup
C]$-Encoding can be solved in time $\mathcal{O}(T(m))$ for each $i$. Applying
Lemma 2.16, we get that $H$-Encoding can be solved in time
$\mathcal{O}(T(m))$. Since $H$ has constant size, the number of induction
steps is constant, so the overhead remains constant.

##  7 Algorithms for Patterns in $\mathcal{P}$

In this section we prove the following lemma that was stated in Section 2.

See 2.19

Throughout this section, $\alpha,\beta$, and $\gamma$ denote integers with
$\alpha\geq\beta\geq 3$ and $\gamma\geq 1$. We start by considering three
simple graph families, see Lemmas 7.1, 7.3 and 7.5. Then in Section 7.1 we
cover all graphs of the form $P(\alpha,\gamma\times 2)$, and in Section 7.2 we
cover all graphs of the form $P(\alpha,\beta,\gamma\times 2)$. Finally, in
Section 7.3 we put the pieces together to prove Lemma 2.11.

######  Lemma 7.1.

For $H=K_{2}$, $H$-Encoding can be solved in time $\mathcal{O}(m)$.

######  Proof 7.2.

We create a single tree decomposition consisting of a single bag $B\coloneqq
V(K_{2})$. It takes $\mathcal{O}(m)$ time to materialize $B$ by picking
adjacent pairs of nodes.

######  Lemma 7.3.

For $H=C_{k}$, $H$-Encoding can be solved in time
$\mathcal{O}(m^{2-1/\left\lceil\frac{k}{2}\right\rceil})$ for any $k\geq 3$.

######  Proof 7.4.

We prove the lemma for even values of $k$ because for odd values of $k$, the
desired time complexity for $C_{k}$ is the same as for $C_{k+1}$, and thus by
Lemma 2.15, the claim follows from the even case.

Denote the nodes of $C_{k}$ by $a_{1}$, $a_{2}$, $\ldots$, $a_{k}$ in
counterclockwise order. Define $\ell\coloneqq\frac{k}{2}$ (so $k=2\ell$). We
want to solve the problem in time $\mathcal{O}(m^{2-1/\ell})$.

Consider some $H$-subgraph $\overline{v}$ of $G$. We create several partial
$H$-encodings of $G$ and claim that exactly one of them encodes
$\overline{v}$.

We split the nodes in $V_{a_{1}},V_{a_{2}},\ldots,V_{a_{k}}$ into the ones
that have degrees smaller than $m^{1/\ell}$ (low-degree nodes, sets
$V_{a_{i}}^{\textup{lo}}$) and the ones that have degrees at least
$m^{1/\ell}$ (high-degree nodes, sets $V_{a_{i}}^{\textup{hi}}$). For each of
the $2^{k}$ choices of high or low degrees in all parts, we construct a
partial $H$-encoding that encodes exactly the $H$-subgraphs that satisfy these
degree constraints. As $\overline{v}$ satisfies exactly one of these $2^{k}$
cases, it will be encoded exactly once. Once we fix for each part of $G$
whether we consider a low-degree or a high-degree node in that part, we filter
out all other nodes. We distinguish two cases.

  * •

_Case 1: $v_{a_{i}}$ has high degree for some $i$._ In this case Section 3.4
implies $|V_{a_{i}}^{\textup{hi}}|\leq m^{1-1/\ell}$. Since $H-\\{a_{i}\\}$ is
a tree, it has a tree decomposition where each bag consists of two adjacent
nodes. Adding $a_{i}$ to every bag, we obtain a tree decomposition of $H$ (see
Figure 14). All of these bags can be materialized in time
$\mathcal{O}(m^{2-1/\ell})$ because there are $\mathcal{O}(m)$ choices for the
two adjacent nodes and $\mathcal{O}(m^{1-1/\ell})$ choices for a node from
$V_{a_{i}}^{\textup{hi}}$.

Figure 14: An example of a tree decomposition of $C_{k}$ for Case 1 of Lemma
7.3 for $k=8$ and $i=4$. Here and later solid black lines inside a bag
represent edges used to create a submaterialization of the bag, and dotted
grey edges represent all other edges that this bag covers.

  * •

_Case 2: $v_{a_{i}}$ has low degree for all $i$._ In this case we create a
tree decomposition of $H$ consisting of two bags:
$B_{1}\coloneqq\\{a_{1},a_{2},\ldots,a_{\ell+1}\\}$ and
$B_{2}\coloneqq\\{a_{\ell+1},a_{\ell+2},\ldots,a_{k},a_{1}\\}$. It is easy to
see that it is indeed a valid tree decomposition of $H$ (see Figure 15). To
materialize $B_{1}$, note that there are $\mathcal{O}(m)$ choices for a pairs
of adjacent nodes from $V_{a_{1}}^{\textup{lo}}$ and
$V_{a_{2}}^{\textup{lo}}$, and then for each $i\in[3,\ell+1]$ there are
$\mathcal{O}(m^{1/\ell})$ choices for a neighbor in $V_{a_{i}}^{\textup{lo}}$
of the chosen node in $V_{a_{i-1}}^{\textup{lo}}$, because all these nodes
have degree at most $m^{1/\ell}$. Thus, we materialize $B_{1}$ in time
$\mathcal{O}(m^{1+(\ell-1)\cdot 1/\ell})=\mathcal{O}(m^{2-1/\ell})$ in total.
Bag $B_{2}$ is materialized analogously.

Figure 15: An example of a tree decomposition of $C_{k}$ for Case 2 of Lemma
7.3 for $k=8$.

The cases are mutually exclusive and cover all $H$-subgraphs of $G$.

######  Lemma 7.5.

Let $H=K_{2,k}$ for $k\geq 2$. $H$-Encoding can be solved in time
$\mathcal{O}(m^{2-\frac{1}{k}})$.

######  Proof 7.6.

Denote the nodes in the first part of the bipartite graph as $a_{1}$, $a_{2}$,
and the nodes in the second part as $b_{1}$, $b_{2}$, $\ldots$, $b_{k}$.

Consider some $H$-subgraph $\overline{v}$ of $G$. We create several partial
$H$-encodings of $G$ and claim that exactly one of them encodes
$\overline{v}$.

We split the nodes in $V_{a_{1}}$ and $V_{a_{2}}$ into the ones that have
degrees smaller than $m^{1/k}$ (low-degree nodes, sets
$V_{a_{1}}^{\textup{lo}}$ and $V_{a_{2}}^{\textup{lo}}$) and the ones that
have degrees at least $m^{1/k}$ (high-degree nodes, sets
$V_{a_{1}}^{\textup{hi}}$ and $V_{a_{2}}^{\textup{hi}}$). For each of the four
choices of high or low degrees in parts $V_{a_{1}}$ and $V_{a_{2}}$, we
construct a partial $H$-encoding that encodes exactly the $H$-subgraphs that
satisfy these degree constraints. As $\overline{v}$ satisfies exactly one of
these four cases, it will be encoded exactly once. Once we fix for $V_{a_{1}}$
and $V_{a_{2}}$ whether we consider a low-degree or a high-degree node in that
part, we filter out all other nodes. We distinguish three cases.

  * •

_Case 1: $v_{a_{1}}$ has high degree._ In this case Observation 3.4 implies
$|V_{a_{1}}^{\textup{hi}}|\leq m^{1-1/k}$. Since $H-\\{a_{1}\\}$ is a tree, it
has a tree decomposition where each bag consists of two adjacent nodes. Adding
$a_{1}$ to every bag, we obtain a tree decomposition of $H$. All of these bags
can be materialized in time $\mathcal{O}(m^{2-1/k}$ because there are
$\mathcal{O}(m)$ choices for the two adjacent nodes and
$\mathcal{O}(m^{1-1/k})$ choices for a node from $V_{a_{1}}^{\textup{hi}}$.

  * •

_Case 1’: $v_{a_{1}}$ has low degree and $v_{a_{2}}$ has high degree._ This
case is symmetric to the previous one.

  * •

_Case 2: $v_{a_{1}}$ and $v_{a_{2}}$ have low degrees._ In this case we create
a tree decomposition of $H$ consisting of two adjacent bags:
$B_{1}\coloneqq\\{a_{1},b_{1},b_{2},\ldots,b_{k}\\}$ and
$B_{2}\coloneqq\\{a_{2},b_{1},b_{2},\ldots,b_{k}\\}$. It is easy to see that
it is indeed a valid tree decomposition of $H$. To materialize $B_{1}$, note
that there are $\mathcal{O}(m)$ choices for a pairs of adjacent nodes from
$V_{a_{1}}^{\textup{lo}}$ and $V_{b_{1}}$, and then for each $i\in[2,k]$ there
are $\mathcal{O}(m^{1/k})$ choices for a neighbor in $V_{b_{i}}$ of the chosen
node in $V_{a_{1}}^{\textup{lo}}$, because all nodes in
$V_{a_{1}}^{\textup{lo}}$ have degree at most $m^{1/k}$. Thus, we materialize
$B_{1}$ in time $\mathcal{O}(m^{1+(k-1)\cdot 1/k})=\mathcal{O}(m^{2-1/k})$.
Bag $B_{2}$ is materialized analogously.

The cases are mutually exclusive and cover all $H$-subgraphs of $G$.

###  7.1 Algorithm for $P(\alpha,\gamma\times 2)$

######  Lemma 7.7 (Biased Cycle).

Let $H$ be a $(k+1)$-cycle on nodes $d_{0},d_{1},\ldots,d_{k}$. Let $H$ be a
host graph, such that between all adjacent parts except $V_{d_{0}}$ and
$V_{d_{k}}$ there are at most $m$ blue edges, and between $V_{d_{0}}$ and
$V_{d_{k}}$ there are $\mathcal{O}(m^{2-\ell f})$ red edges for some
$\ell\in\mathbb{N}$ and $f\in(0,1)$. Say $\delta_{i}\in\mathbb{N}$ for
$i\in[0,k]$ are such that all nodes in part $V_{d_{i}}$ have at most
$m^{\delta_{i}f}$ blue adjacent edges. Furthermore, if $\delta_{i}>1$, then
$|V_{d_{i}}|\leq m^{1-f}$. We call such a graph $G$ _an instance of Biased
Cycle_. Then there is an algorithm that solves $H$-Encoding on $G$ in the
following time with a single partial $H$-encoding.

  * •

$\mathcal{O}(m^{2-f}+m^{1+(\delta_{\ell.\,.k-\ell}+\ell-1)f})$ if
$\ell\leq\frac{k+1}{2}$, where $\delta_{x.\,.y}\coloneqq\sum_{x\leq i\leq
y}\delta_{i}$ for any $x,y\in[0,k]$.555Note that if $\ell=\frac{k+1}{2}$, we
have $\delta_{\ell.\,.k-\ell}=\delta_{\ell.\,.\ell-1}=0$.

  * •

$\mathcal{O}(m^{2-f})$ if $\ell>\frac{k+1}{2}$.

Furthermore, if $\ell\leq\frac{k+1}{2}$ and $\delta_{r}>1$ for some
$r\in\\{0,\ldots,\ell-1,k-\ell+1,\ldots,k\\}$, the algorithm works in time
$\mathcal{O}(m^{2-f})$. We call such an instance of Biased Cycle _$\ell$
-reachable_.

######  Proof 7.8.

We consider four cases depending on given values $\delta$, and for each case
present a single partial $H$-encoding of $G$ that encodes all $H$-subgraphs in
$G$.

  * •

_Case 1: $\delta_{r}>1$ for some $r\in[0,\min\\{\ell-1,k-1\\}]$._ Choose
minimal such $r$. We create the following tree decomposition of $H$. Bag
$B_{0}$ consists of nodes $d_{k},d_{0},d_{1},\ldots,d_{r}$. Furthermore, we
create bags $B_{i}\coloneqq\\{d_{r},d_{i},d_{i+1}\\}$ for $i\in[r+1,k-1]$. We
connect them in a line: $B_{0}\leftrightline B_{k-1}\leftrightline
B_{k-2}\leftrightline\cdots\leftrightline B_{r+1}$. It is clear that this is a
tree decomposition of $H$. Note that as $\delta_{r}>1$, the statement of the
lemma implies $|V_{d_{r}}|\leq m^{1-f}$. Hence, each bag $B_{i}$ for
$i\in[r+1,k-1]$ can be materialized in time $\mathcal{O}(m^{2-f})$ because
there are $\mathcal{O}(m)$ choices for the two adjacent nodes from $V_{d_{i}}$
and $V_{d_{i+1}}$ and $\mathcal{O}(m^{1-f})$ choices for a node from
$V_{d_{r}}$. To materialize $B_{0}$, note that there are
$\mathcal{O}(m^{2-\ell f})$ choices for an adjacent pair of nodes from
$V_{d_{0}}$ and $V_{d_{k}}$, and for each $i\in[r]$ we pick a node from
$V_{d_{i}}$ as one of the $\mathcal{O}(m^{f})$ neighbors of the chosen node
from $V_{d_{i-1}}$. Thus, we materialize $B_{0}$ in time
$\mathcal{O}(m^{2-\ell f}\cdot m^{rf})\leq\mathcal{O}(m^{2-f})$ as
$r\leq\ell-1$.

  * •

_Case 1’: $\delta_{r}=1$ for all $r\in[0,\min\\{\ell-1,k-1\\}]$ and
$\delta_{r}>1$ for some $r\in[\max\\{k-\ell+1,1\\},k]$._ This case is
symmetric to the previous one.

  * •

_Case 2: $\delta_{r}=1$ for all
$r\in[0,\min\\{\ell-1,k-1\\}]\cup[\max\\{k-\ell+1,1\\},k]$ and
$\ell>\frac{k+1}{2}$._ In this case $k\leq 2\ell-2$. Hence, $\delta_{r}=1$ for
all $r\in[0,k]$. We create a tree decomposition of $H$ consisting of two bags:
$B_{1}\coloneqq\\{d_{k},d_{0},d_{1},\ldots,d_{\min\\{\ell-1,k-1\\}\\}}$ and
$B_{2}\coloneqq\\{d_{0},d_{k},d_{k-1},\ldots,d_{\max\\{k-\ell+1,1\\}\\}}$. It
is easy to see that it is a tree decomposition of $H$. To materialize $B_{1}$,
note that there are $\mathcal{O}(m^{2-\ell f})$ choices for an adjacent pair
of nodes from $V_{d_{0}}$ and $V_{d_{k}}$, and then for each
$i\in[\min\\{\ell-1,k-1\\}]$ there are $\mathcal{O}(m^{f})$ choices to pick a
node from $V_{d_{i}}$ as a neighbor of the chosen node from $V_{d_{i-1}}$.
Hence, we materialize $B_{1}$ in time $\mathcal{O}(m^{2-\ell f}\cdot
m^{\min\\{\ell-1,k-1\\}\cdot f})\leq\mathcal{O}(m^{2-f})$. Bag $B_{2}$ can be
materialized in time $\mathcal{O}(m^{2-f})$ analogously.

  * •

_Case 3: $\delta_{r}=1$ for all
$r\in[0,\min\\{\ell-1,k-1\\}]\cup[\max\\{k-\ell+1,1\\},k]$ and
$\ell\leq\frac{k+1}{2}$._ In this case $\min\\{\ell-1,k-1\\}=\ell-1$ and
$\max\\{k-\ell+1,1\\}=k-\ell+1$. Furthermore, $\ell-1<k-\ell+1$. We create a
tree decomposition of $H$ consisting of two bags:
$B_{1}\coloneqq\\{d_{k},d_{0},d_{1},\ldots,d_{\ell-1}\\}$ and
$B_{2}\coloneqq\\{d_{\ell-1},d_{\ell},\ldots,d_{k}\\}$. It is easy to see that
it is a tree decomposition of $H$. We materialize $B_{1}$ in time
$\mathcal{O}(m^{2-f})$ the same way it was materialized in the previous case.
To materialize $B_{2}$, note that there are $\mathcal{O}(m)$ choices for an
adjacent pair of nodes from $V_{d_{k}}$ and $V_{d_{k-1}}$, and then for each
$i\in\\{k-2,k-3,\ldots,\ell-1\\}$ there are at most $m^{\delta_{i+1}f}$
choices to pick a node from $V_{d_{i}}$ as a neighbor of the chosen node from
$V_{d_{i+1}}$. Hence, we materialize $B_{2}$ in time $\mathcal{O}(m\cdot
m^{\delta_{\ell.\,.k-1}f})$. As we know that
$\delta_{k-\ell+1}=\delta_{k-\ell+2}=\cdots=\delta_{k-1}=1$, we get that
$\mathcal{O}(m\cdot
m^{\delta_{\ell.\,.k-1}f})=\mathcal{O}(m^{1+(\delta_{\ell.\,.k-\ell}+\ell-1)f})$.
Hence, we materialize both $B_{1}$ and $B_{2}$ in time
$\mathcal{O}(m^{2-f}+m^{1+(\delta_{\ell.\,.k-\ell}+\ell-1)f})$.

Note that if $\ell>\frac{k+1}{2}$, only Cases 1 and 2 appear, and if $G$ is an
$\ell$-reachable instance of Biased Cycle, only Case 1 appears, and thus the
time complexity is $\mathcal{O}(m^{2-f})$.

######  Lemma 7.9.

For $\alpha\geq 3$, $\gamma\geq 2$, and $H=P(\alpha,\gamma\times 2)$,
$H$-subgraph isomorphism encoding can be solved in time
$\mathcal{O}(m^{2-1/(2\gamma+\left\lfloor\frac{\alpha-1}{2}\right\rfloor)})$.

######  Proof 7.10.

We prove the lemma for even values of $\alpha$ because for odd values of
$\alpha$, the desired time complexity for $P(\alpha,\gamma\times 2)$ is the
same as for $P(\alpha+1,\gamma\times 2)$, and thus by Lemma 2.15, the claim
follows from the even case.

Define $\ell\coloneqq\frac{\alpha-2}{2}$ (so $\alpha=2\ell+2$) and
$f\coloneqq\frac{1}{2\gamma+\ell}$. We need to solve the problem in time
$\mathcal{O}(m^{2-f})=\mathcal{O}(m^{1+(2\gamma+\ell-1)f})$.

Consider some $H$-subgraph $\overline{v}$ of $G$. We create several partial
$H$-encodings of $G$ and claim that exactly one of them encodes
$\overline{v}$.

We split the nodes in $V_{a_{0}},V_{a_{1}},V_{a_{2}},\ldots,V_{a_{\alpha}}$ of
$G$ into the ones that have degrees smaller than $m^{f}$ (low-degree nodes,
sets $V_{a_{i}}^{\textup{lo}}$) and the ones that have degrees at least
$m^{f}$ (high-degree nodes, sets $V_{a_{i}}^{\textup{hi}}$). For each of the
$2^{\alpha+1}=\mathcal{O}(1)$ choices of high and low degrees, we construct
several partial $H$-encodings that encode exactly the $H$-subgraphs that
satisfy these degree constraints. As $\overline{v}$ satisfies exactly one of
these $2^{\alpha+1}$ cases, it will be encoded exactly once. Once we fix for
each of the parts $V_{a_{0}}\ldots,V_{a_{\alpha}}$ whether we consider a low-
degree or a high-degree node in that part, we filter out all other nodes. By a
slight abuse of notation we still call the new filtered graph $G$.

We consider four cases.

  * •

_Case 1: $v_{a_{0}}$ has high degree._ In this case
$|V_{a_{0}}^{\textup{hi}}|\leq m^{1-f}$ due to Section 3.4. Since
$H-\\{a_{0}\\}$ is a tree, it has a tree decomposition where every bag
consists of exactly two adjacent nodes. Adding $a_{0}$ to all these bags, we
obtain a tree decomposition of $H$. Each one of these bags can be materialized
in time $\mathcal{O}(m^{2-f})$ because there are $\mathcal{O}(m)$ choices for
the two adjacent nodes and $|V_{a_{0}}^{\textup{hi}}|=\mathcal{O}(m^{1-f})$
choices for $v_{a_{0}}$.

  * •

_Case 1’: $v_{a_{0}}$ has low degree, and $v_{a_{\alpha}}$ has high degree._
This case is symmetric to the previous one.

  * •

_Case 2:
$v_{a_{0}},v_{a_{1}},\ldots,v_{a_{\ell}},v_{a_{\alpha-\ell}},\ldots,v_{a_{\alpha-1}}$,
and $v_{a_{\alpha}}$ have low degrees._ As $\alpha-\ell=\ell+2$, all nodes
$v_{a_{i}}$ except for $v_{a_{\ell+1}}$ have low degrees. We create a tree
decomposition consisting of two adjacent bags:
$B_{1}\coloneqq\\{a_{0},a_{1},\ldots,a_{\ell+1},c_{1},c_{2},\ldots,c_{\gamma}\\}$
and
$B_{2}\coloneqq\\{a_{\ell+1},a_{\ell+2},\ldots,a_{\alpha},c_{1},c_{2},\allowbreak\ldots,c_{\gamma}\\}$.
It is easy to see that it is a tree decomposition of $H$ (see Figure 16). To
materialize $B_{1}$, note that there are $\mathcal{O}(m)$ choices for an
adjacent pair of nodes from $V_{a_{0}}^{\textup{lo}}$ and
$V_{a_{1}}^{\textup{lo}}$. Then, for each $c_{i}$, for $i\in[\gamma]$, there
are $\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor
of the chosen node in $V_{a_{0}}^{\textup{lo}}$. Finally, for each
$i\in[2,\ell]$, there are $\mathcal{O}(m^{f})$ choices to pick a node in
$V_{a_{i}}^{\textup{lo}}$ as a neighbor of the chosen node in
$V_{a_{i-1}}^{\textup{lo}}$, and there are $\mathcal{O}(m^{f})$ choices to
pick a node in $V_{a_{\ell+1}}$ as a neighbor of the chosen node in
$V_{a_{\ell}}^{\textup{lo}}$. In total, to materialize $B_{1}$, we use
$\mathcal{O}(m^{1+\gamma f+\ell
f})\leq\mathcal{O}(m^{1+(2\gamma+\ell-1)f})=\mathcal{O}(m^{2-f})$ time. We
materialize $B_{2}$ analogously.

Figure 16: An example of a tree decomposition of $P(\alpha,\gamma\times 2)$
for Case 2 of Lemma 7.9 for $\alpha=4$ and $\gamma=2$.

  * •

_Case 3: $v_{a_{0}}$ and $v_{a_{\alpha}}$ have low degrees, and at least one
of $v_{a_{1}},\ldots,v_{a_{\ell}},v_{a_{\alpha-\ell}},\ldots,v_{a_{\alpha-1}}$
has a high degree._ As the degrees of nodes in $V_{a_{0}}^{\textup{lo}}$ are
smaller than $m^{f}$, in time $\mathcal{O}(m^{1+(\gamma-1)f})$ we can
materialize a bag $B_{a_{0}\to
c}\coloneqq\\{a_{0},c_{1},c_{2},\ldots,c_{\gamma}\\}$: there are
$\mathcal{O}(m)$ choices for an adjacent pair of nodes from
$V_{a_{0}}^{\textup{lo}}$ and $V_{c_{1}}$, and there are $\mathcal{O}(m^{f})$
choices to pick a node in $V_{c_{i}}$ as a neighbor of the chosen node in
$V_{a_{0}}^{\textup{lo}}$, for each $i\in[2,\gamma]$. By using a binary search
tree as a dictionary we can store for every tuple of nodes from parts
$V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$ all their common neighbors in
$V_{a_{0}}^{\textup{lo}}$ in time
$\widetilde{\mathcal{O}}(m^{1+(\gamma-1)f})\leq\mathcal{O}(m^{1+(2\gamma+\ell-1)f})=\mathcal{O}(m^{2-f})$.
Note that $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is one of the listed tuples as
they have a common neighbor $v_{a_{0}}\in V_{a_{0}}^{\textup{lo}}$. Now we
split the listed tuples of nodes into the ones that have less than $m^{\gamma
f}$ common neighbors in $V_{a_{0}}^{\textup{lo}}$ (low-degree tuples) and the
ones that have at least $m^{\gamma f}$ common neighbors (high-degree tuples).
Similarly to nodes from parts $V_{a_{i}}$, we deal with low- and high-degree
tuples separately. We distinguish two cases.

    * –

_Case 3.1: $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a high-degree tuple._ The
total number of copies of $B_{a_{0}\to c}$ that we generated is at most
$m^{1+(\gamma-1)f}$. Hence, there are at most $m^{1-f}$ high-degree tuples of
nodes from parts $V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$. Consider the
graph $H-\\{c_{1},\ldots,c_{\gamma}\\}$. Since it is a tree, it has a tree
decomposition where each bag consists of two adjacent nodes. Adding
$c_{1},c_{2},\ldots,c_{\gamma}$ to every bag, we obtain a tree decomposition
of $H$ (see Figure 17). We can materialize each bag in time
$\mathcal{O}(m^{2-f})$, because there are $\mathcal{O}(m)$ choices for the two
adjacent nodes and at most $m^{1-f}$ choices for a high-degree tuple from
$V_{c_{1}}\times V_{c_{2}}\times\cdots\times V_{c_{\gamma}}$. Note that this
partial $H$-encoding encodes exactly such $H$-subgraphs $\overline{v}$, for
which $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a high-degree tuple because for
all bags, only high-degree tuples $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ are
listed.

Figure 17: An example of a tree decomposition of $P(\alpha,\gamma\times 2)$
for Case 3.1 of Lemma 7.9 for $\alpha=4$ and $\gamma=2$.

    * –

_Case 3.2: $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple._ In time
$\mathcal{O}(m^{1+(\gamma-1)f})$ we materialize a bag $B_{a_{\alpha}\to
c}\coloneqq\\{a_{\alpha},c_{1},c_{2},\ldots,c_{\gamma}\\}$ analogously to the
materialization of $B_{a_{0}\to c}$. If the chosen nodes from parts
$V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$ form a low-degree tuple, we spend
time $\mathcal{O}(m^{\gamma f})$ to materialize all their common neighbors in
$V_{a_{0}}$ by accessing the dictionary. This way we create a
submaterialization $S_{\textup{down}}$ of $B_{\textup{down}}\coloneqq
B_{a_{\alpha}\to c}\cup\\{a_{0}\\}$ in time
$\mathcal{O}(m^{1+(\gamma-1)f}\cdot(\log m+m^{\gamma
f}))=\mathcal{O}(m^{1+(2\gamma-1)f})=\mathcal{O}(m^{2-(\ell+1)f})$. Note that
for an $H$-subgraph $\overline{v}$, we have that
$(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple if and only if
$\left.\overline{v}\right|_{B_{\textup{down}}}\in S_{\textup{down}}$. Thus, it
remains to attach a decomposition of the path $a$ to $B_{\textup{down}}$. We
attach a bag $B_{\textup{ends}}\coloneqq\\{a_{0},a_{\alpha}\\}$ to
$B_{\textup{down}}$ and create its submaterialization $S_{\textup{ends}}$ as a
set of projections of the elements of $S_{\textup{down}}$ onto
$B_{\textup{ends}}$. This takes time
$\widetilde{\mathcal{O}}(|S_{\textup{down}}|)=\widetilde{\mathcal{O}}(m^{2-(\ell+1)f})\leq\widetilde{\mathcal{O}}(m^{2-2f})\leq\mathcal{O}(m^{2-f})$,
and we have
$|S_{\textup{ends}}|\leq|S_{\textup{down}}|=\mathcal{O}(m^{2-(\ell+1)f})$. We
consider $V_{a_{0}},\ldots,V_{a_{\alpha}}$ as an instance of Biased Cycle,
where we think of edges of $G$ between $V_{a_{i-1}}$ and $V_{a_{i}}$ for
$i\in[\alpha]$ as the blue edges, and we think of $S_{\textup{ends}}$ as the
red edges between $V_{a_{0}}$ and $V_{a_{\alpha}}$. The values $\delta_{i}$
are defined as 1 if we pick low-degree nodes in $V_{a_{i}}$, and as $1/f$ if
we pick high-degree nodes in $V_{a_{i}}$. Since at least one of
$v_{a_{1}},\ldots,v_{a_{\ell}},v_{a_{\alpha-\ell}},\ldots,v_{a_{\alpha-1}}$
has high degree in this case and $\ell+1\leq\frac{\alpha+1}{2}$, such an
instance of Biased Cycle is $(\ell+1)$-reachable. Thus, we can apply Lemma 7.7
to create a full encoding of this Biased Cycle in time $\mathcal{O}(m^{2-f})$.
As there is an edge $\\{a_{0},a_{\alpha}\\}$ in this instance of Biased Cycle,
we can attach the resulting tree decomposition with a partial encoding to
$B_{\textup{ends}}$ by a bag containing both $a_{0}$ and $a_{\alpha}$. Hence,
we create a partial $H$-encoding of $G$. Note that this partial $H$-encoding
encodes exactly such $H$-subgraphs $\overline{v}$, for which
$(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple, because for
$B_{\textup{ends}}$ only low-degree tuples $(v_{c_{1}},\ldots,v_{c_{\gamma}})$
are listed.

We note that the cases are mutually exclusive and cover all $H$-subgraphs
$\overline{v}$ in $G$. Hence, we create a full $H$-encoding of $G$.

###  7.2 Algorithm for $P(\alpha,\beta,\gamma\times 2)$

######  Lemma 7.11.

For $\alpha\geq\beta\geq 3$, $\gamma\geq 1$, and
$H=P(\alpha,\beta,\gamma\times 2)$, $H$-Encoding can be solved in time
$\mathcal{O}(m^{2-\frac{1}{\mathcal{F}(\alpha,\beta,\gamma)}})$.

######  Proof 7.12.

Let $f\coloneqq\frac{1}{\mathcal{F}(\alpha,\beta,\gamma)}$. We want to solve
the problem in time
$\mathcal{O}(m^{2-f})=\mathcal{O}(m^{1+(\mathcal{F}(\alpha,\beta,\gamma)-1)f})$.

Consider some $H$-subgraph $\overline{v}$ of $G$. We create several partial
$H$-encodings of $G$ and claim that exactly one of them encodes
$\overline{v}$.

We split the nodes in
$V_{a_{0}},V_{a_{1}},V_{a_{2}},\ldots,V_{a_{\alpha}},V_{b_{1}},V_{b_{2}},\ldots,V_{b_{\beta-1}}$
of $G$ into groups called subparts by their degrees: degrees in $[1,m^{f})$
(sets $V_{a_{i}}^{1}$ and $V_{b_{i}}^{1}$), in $[m^{f},m^{2f})$ (sets
$V_{a_{i}}^{2}$ and $V_{b_{i}}^{2}$), $\ldots$, in
$[m^{(\mathcal{F}(\alpha,\beta,\gamma)-1)\cdot f},m]$ (sets
$V_{a_{i}}^{\mathcal{F}(\alpha,\beta,\gamma)}$ and
$V_{b_{i}}^{\mathcal{F}(\alpha,\beta,\gamma)}$). For each of the
$\mathcal{F}(\alpha,\beta,\gamma)^{\alpha+\beta}=\mathcal{O}(1)$ choices of
subparts in parts $V_{a_{i}}$ and $V_{b_{i}}$, we construct several partial
$H$-encodings that encode exactly the $H$-subgraphs that satisfy these degree
constraints. As $\overline{v}$ satisfies exactly one of these
$\mathcal{F}(\alpha,\beta,\gamma)^{\alpha+\beta}$ cases, it will be encoded
exactly once. Let $\delta_{d}$ be such that $v_{d}$ belongs to
$V_{d}^{\delta_{d}}$ for any $d\in\\{a_{i}\mid
i\in[0,\alpha]\\}\cup\\{b_{i}\mid i\in[\beta-1]\\}$. Note that all nodes in
$V_{d}^{\delta_{d}}$ have degrees at most $m^{\delta_{d}f}$, and
$|V_{d}^{\delta_{d}}|\leq m^{1-(\delta_{d}-1)f}$ due to Section 3.4 as all
nodes in $V_{d}^{\delta_{d}}$ have degrees at least $m^{(\delta_{d}-1)f}$ in
$G$. Denote $\delta_{\max}\coloneqq\max\\{\delta_{d}\mid d\in\\{a_{i}\mid
i\in[0,\alpha]\\}\cup\\{b_{i}\mid i\in[\beta-1]\\}\\}$ and
$d_{\max}\coloneqq\operatorname*{arg\,max}\\{\delta_{d}\mid d\in\\{a_{i}\mid
i\in[0,\alpha]\\}\cup\\{b_{i}\mid i\in[\beta-1]\\}\\}$. Furthermore, we denote
$\delta_{a_{x.\,.y}}\coloneqq\sum_{x\leq i\leq y}\delta_{a_{i}}$ for any
$x,y\in[0,\alpha]$ and $\delta_{b_{x.\,.y}}\coloneqq\sum_{x\leq i\leq
y}\delta_{b_{i}}$ for any $x,y\in[0,\beta]$. Once we fix for each of the parts
$V_{a_{i}}$ and $V_{b_{i}}$ to which subpart belongs the corresponding node of
$\overline{v}$, we filter out all other nodes. By a slight abuse of notation
we still call the new filtered graph $G$.

After the degree splitting, in some cases simple algorithms are already
applicable. We first deal with some such cases.

####  7.2.1 High-degree-low-degree Algorithms

We consider seven special cases. The exact condition of each case includes
negations of all previous cases, but we omit them for conciseness.

##### Special Case 1: $\delta_{a_{0}}\geq 2$.

In this case $|V_{a_{0}}^{\delta_{a_{0}}}|\leq m^{1-f}$. Since $H-\\{a_{0}\\}$
is a tree, it has a tree decomposition where every bag consists of exactly two
adjacent nodes. Adding $a_{0}$ to all these bags, we obtain a tree
decomposition of $H$. Each one of these bags can be materialized in time
$\mathcal{O}(m^{2-f})$ because there are $\mathcal{O}(m)$ choices for the two
adjacent nodes and $|V_{a_{0}}^{\delta_{a_{0}}}|\leq m^{1-f}$ choices for a
node in $V_{a_{0}}^{\delta_{a_{0}}}$.

##### Special Case 1’: $\delta_{a_{\alpha}}\geq 2$.

This case is symmetric to the previous one.

Hence, from now on we may assume $\delta_{a_{0}}=\delta_{a_{\alpha}}=1$.

##### Special Case 2: $\delta_{\max}\leq 2\gamma+1$ and $\alpha=\beta$.

We create a tree decomposition of $H$ consisting of two adjacent bags:

$B_{1}\coloneqq\\{a_{0},a_{1},\ldots,a_{\alpha-1},b_{1},c_{1},c_{2},\ldots,c_{\gamma}\\}$

and

$B_{2}\coloneqq\\{a_{\alpha-1},b_{1},b_{2},\ldots,b_{\beta-1},b_{\beta},c_{1},c_{2},\ldots,c_{\gamma}\\}.$

It is easy to see that it is indeed a valid tree decomposition of $H$ (see
Figure 18).

To materialize $B_{1}$, note that there are $\mathcal{O}(m)$ choices for an
adjacent pair of nodes from $V_{a_{0}}^{\delta_{a_{0}}}$ and
$V_{b_{1}}^{\delta_{b_{1}}}$. Then, for each $i\in[\gamma]$, there are
$\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor of
the chosen node in $V_{a_{0}}^{\delta_{a_{0}}}$. Furthermore, for each
$i\in[\alpha-1]$, there are $\mathcal{O}(m^{\delta_{a_{i-1}}f})$ choices to
pick a node in $V_{a_{i}}^{\delta_{a_{i}}}$ as a neighbor of the chosen node
in $V_{a_{i-1}}^{\delta_{a_{i-1}}}$. In total, this takes time

$\displaystyle\mathcal{O}(m^{1+(\gamma+\delta_{a_{0.\,.\alpha-2}})f})$
$\displaystyle\leq\mathcal{O}(m^{1+(\gamma+1+(\alpha-2)\cdot\delta_{\max})f})$
$\displaystyle\leq\mathcal{O}(m^{1+(\gamma+1+(\alpha-2)\cdot(2\gamma+1))f})$
$\displaystyle=\mathcal{O}(m^{1+((2\alpha-3)\gamma+\alpha-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}),$

where the last inequality holds due to Lemma 8.21.

We materialize $B_{2}$ analogously. Hence, we get a full $H$-encoding of $G$.

Figure 18: An example of a tree decomposition of $P(\alpha,\beta,\gamma\times
2)$ for Special Case 2 of Lemma 7.11 for $\alpha=\beta=6$ and $\gamma=3$.

##### Special Case 3: $\delta_{\max}\leq 2\gamma+1$ and $\alpha>\beta$.

We create a tree decomposition of $H$. See Figure 19. Let
$B_{b}\coloneqq\\{b_{0},b_{1},\ldots,b_{\beta}\\}$. To create a
submaterialization $S_{b}$ of $B_{b}$, note that there are $\mathcal{O}(m)$
choices for an adjacent pair of nodes from $V_{b_{0}}^{\delta_{b_{0}}}$ and
$V_{b_{1}}^{\delta_{b_{1}}}$. Then, for each $i\in[2,\beta]$, there are
$\mathcal{O}(m^{\delta_{b_{i-1}}f})\leq\mathcal{O}(m^{\delta_{\max}f})$
choices to pick a node in $V_{b_{i}}^{\delta_{b_{i}}}$ as a neighbor of the
chosen node in $V_{b_{i-1}}^{\delta_{b_{i-1}}}$. Hence, we materialize $B_{b}$
in time
$\mathcal{O}(m^{1+(\beta-1)\delta_{\max}f})\leq\mathcal{O}(m^{1+(\beta-1)(2\gamma+1)f})=\mathcal{O}(m^{2-\ell
f})$, where
$\ell\coloneqq\mathcal{F}(\alpha,\beta,\gamma)-(\beta-1)\cdot(2\gamma+1)$.
Note that $\ell\geq 2$ due to Lemma 8.23.

Furthermore, we create bags $B_{c_{i}}\coloneqq B_{b}\cup\\{c_{i}\\}$ for all
$i\in[\gamma]$. We materialize $B_{c_{i}}$ by starting from the
submaterialization $S_{b}$ of $B_{b}$ and extending each tuple $u\in S_{b}$ by
picking a node in $V_{c_{i}}$ as one of the
$\mathcal{O}(m^{\delta_{b_{0}}f})=\mathcal{O}(m^{f})$ neighbors of the node in
$V_{b_{0}}^{\delta_{b_{0}}}$ that is picked by $u$. Hence, each $B_{c_{i}}$ is
materialized in time $\mathcal{O}(m^{(2-\ell f)+f})\leq\mathcal{O}(m^{2-f})$.
Furthermore, we create a bag
$B_{\textup{ends}}\coloneqq\\{a_{0},a_{\alpha}\\}$ and create its
materialization $S_{\textup{ends}}$ as a set of projections of the elements of
$S_{b}$ onto $B_{\textup{ends}}$. This takes time
$\widetilde{\mathcal{O}}(|S_{b}|)=\widetilde{\mathcal{O}}(m^{2-\ell
f})\leq\mathcal{O}(m^{2-f})$, and we have
$|S_{\textup{ends}}|\leq|S_{b}|=\mathcal{O}(m^{2-\ell f})$.

We connect the created bags in a line: $B_{b}\leftrightline
B_{c_{1}}\leftrightline B_{c_{2}}\leftrightline\cdots\leftrightline
B_{c_{\gamma}}\leftrightline B_{\textup{ends}}$. To create a tree
decomposition of $H$, it remains to attach a decomposition of the path
$a_{0}\leftrightline a_{1}\leftrightline\cdots\leftrightline a_{\alpha}$ to
$B_{\textup{ends}}$.

We consider
$V_{a_{0}}^{\delta_{a_{0}}},\ldots,V_{a_{\alpha}}^{\delta_{a_{\alpha}}}$ as an
instance of Biased Cycle, where we think of edges of $G$ between
$V_{a_{i-1}}^{\delta_{a_{i-1}}}$ and $V_{a_{i}}^{\delta_{a_{i}}}$ for
$i\in[\alpha]$ as the blue edges, and we think of $S_{\textup{ends}}$ as the
red edges between $V_{a_{0}}^{\delta_{a_{0}}}$ and
$V_{a_{\alpha}}^{\delta_{a_{\alpha}}}$. We apply Lemma 7.7 to create a full
encoding of this Biased Cycle. If $\ell>\frac{\alpha+1}{2}$, it works in time
$\mathcal{O}(m^{2-f})$, and if $\ell\leq\frac{\alpha+1}{2}$, it works in time

$\displaystyle\mathcal{O}(m^{2-f}+m^{1+(\delta_{a_{\ell.\,.\alpha-\ell}}+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+((\alpha-2\ell+1)\cdot\delta_{\max}+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+((\alpha-2\ell+1)\cdot(2\gamma+1)+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}),$

where the last inequality holds due to Lemma 8.25.

As there is an edge $\\{a_{0},a_{\alpha}\\}$ in this instance of Biased Cycle,
we can attach the resulting tree decomposition with a partial encoding to
$B_{\textup{ends}}$ by a bag containing both $a_{0}$ and $a_{\alpha}$.
Therefore, we create a full $H$-encoding of $G$.

Figure 19: An example of a tree decomposition of $P(\alpha,\beta,\gamma\times
2)$ for Special Case 3 of Lemma 7.11 for $\alpha=6$, $\beta=4$, and
$\gamma=2$.

Hence, from now on we may assume $\delta_{\max}\geq 2\gamma+2$.

##### Special Case 4: for some positive integer $\ell\leq\alpha-1$, we have
$\delta_{a_{1}}=\delta_{a_{2}}=\cdots=\delta_{a_{\ell-1}}=1$,
$\delta_{a_{\ell}}\geq\gamma+2$, and $\delta_{b_{\beta-1}}\geq\gamma+\ell+1$.

We create the following tree decomposition of $H$ (see Figure 20). We define a
bag

$B_{1}\coloneqq\\{a_{0},a_{1},a_{2},\ldots,a_{\ell},b_{\beta-1},c_{1},c_{2},\ldots,c_{\gamma}\\},$

a bag

$B_{2}\coloneqq\\{a_{\ell},b_{\beta-1},b_{\beta},c_{1},c_{2},\ldots,c_{\gamma}\\},$

bags $B_{b_{i}}\coloneqq\\{b_{i-1},b_{i},b_{\beta-1}\\}$ for $i\in[\beta-2]$,
and bags $B_{a_{i}}\coloneqq\\{a_{\ell},a_{i},a_{i+1}\\}$ for
$i\in[\ell+1,\alpha-1]$. We connect these bags in a line:
$B_{b_{\beta-2}}\leftrightline
B_{b_{\beta-3}}\leftrightline\cdots\leftrightline B_{b_{1}}\leftrightline
B_{1}\leftrightline B_{2}\leftrightline B_{a_{\alpha-1}}\leftrightline
B_{a_{\alpha-2}}\leftrightline\cdots\leftrightline B_{a_{\ell+1}}$. It is easy
to see that it is indeed a valid tree decomposition of $H$.

To materialize $B_{1}$, note that the number of choices to pick a node from
$V_{b_{\beta-1}}^{\delta_{b_{\beta-1}}}$ is
$\mathcal{O}(|V_{b_{\beta-1}}^{\delta_{b_{\beta-1}}}|)=\mathcal{O}(m^{1-(\delta_{b_{\beta-1}}-1)f})\leq\mathcal{O}(m^{1-(\gamma+\ell)f})$.
There are $\mathcal{O}(m)$ choices for an adjacent pair of nodes from
$V_{a_{0}}^{\delta_{a_{0}}}$ and $V_{a_{1}}^{\delta_{a_{1}}}$. Then, for each
$i\in[\gamma]$, there are $\mathcal{O}(m^{f})$ choices to pick a node in
$V_{c_{i}}$ of the chosen node in $V_{a_{0}}^{\delta_{a_{0}}}$. Finally, for
each $i\in[2,\ell]$, there are
$\mathcal{O}(m^{\delta_{a_{i-1}}f})=\mathcal{O}(m^{f})$ choices to pick a node
in $V_{a_{i}}^{\delta_{a_{i}}}$ as a neighbor of the chosen node in
$V_{a_{i-1}}^{\delta_{a_{i-1}}}$. In total, this takes time
$\mathcal{O}(m^{(1-(\gamma+\ell)f)+1+(\gamma+(\ell-1))f})=\mathcal{O}(m^{2-f})$.

To materialize $B_{2}$, note that the number of choices to pick a node from
$V_{a_{\ell}}^{\delta_{a_{\ell}}}$ is
$\mathcal{O}(|V_{a_{\ell}}^{\delta_{a_{\ell}}}|)=\mathcal{O}(m^{1-(\delta_{a_{\ell}}-1)f})\leq\mathcal{O}(m^{1-(\gamma+1)f})$.
There are $\mathcal{O}(m)$ choices to pick an adjacent pair of nodes from
$V_{b_{\beta-1}}^{\delta_{b_{\beta-1}}}$ and
$V_{b_{\beta}}^{\delta_{b_{\beta}}}$. Then, for each $i\in[\gamma]$, there are
$\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor of
the chosen node in $V_{b_{\beta}}^{\delta_{b_{\beta}}}$. In total, this takes
time $\mathcal{O}(m^{(1-(\gamma+1)f)+1+\gamma f})=\mathcal{O}(m^{2-f})$.

Each bag $B_{b_{i}}$, for $i\in[\beta-2]$, can be materialized in time
$\mathcal{O}(m^{2-f})$, because there are $\mathcal{O}(m)$ choices for a pair
of adjacent nodes from $V_{b_{i-1}}^{\delta_{b_{i-1}}}$ and
$V_{b_{i}}^{\delta_{b_{i}}}$, and
$\mathcal{O}(|V_{b_{\beta-1}}^{\delta_{b_{\beta-1}}}|)\leq\mathcal{O}(m^{1-(\gamma+\ell)f})\leq\mathcal{O}(m^{1-f})$
choices for a node from $V_{b_{\beta-1}}^{\delta_{b_{\beta-1}}}$.

Analogously, bags $B_{a_{i}}$ for $i\in[\ell+1,\alpha-1]$ can also be
materialized in time $\mathcal{O}(m^{2-f})$. Hence, we get a full $H$-encoding
of $G$ in time $\mathcal{O}(m^{2-f})$.

Figure 20: An example of a tree decomposition of $P(\alpha,\beta,\gamma\times
2)$ for Special Case 4 of Lemma 7.11 for $\alpha=6$, $\beta=5$, $\gamma=2$,
and $\ell=2$.

##### Special Case 4’: for some positive integer $\ell\leq\alpha-1$, we have
$\delta_{a_{\alpha-\ell+1}}=\cdots=\delta_{a_{\alpha-2}}=\delta_{\alpha-1}=1$,
$\delta_{a_{\alpha-\ell}}\geq\gamma+2$, and $\delta_{b_{1}}\geq\gamma+\ell+1$.

This case is symmetric to the previous one.

##### Special Case 5: for some positive integer $\ell\leq\alpha/2$, we have
$\delta_{a_{r}}=1$ for all
$r\in\\{0,\ldots,\ell-1,\alpha-\ell+1,\ldots,\alpha\\}$,
$\delta_{a_{\ell}}\geq\gamma+2$, $\delta_{b_{1}}\leq\gamma+\ell$, and
$\beta=3$.

We create the following tree decomposition of $H$ (see Figure 21). We define a
bag

$B_{1}\coloneqq\\{a_{0},a_{1},\ldots,a_{\ell},b_{1},b_{2},c_{1},c_{2},\ldots,c_{\gamma}\\},$

a bag

$B_{2}\coloneqq\\{a_{\ell},b_{2},b_{3},c_{1},c_{2},\ldots,c_{\gamma}\\},$

and bags $B_{a_{i}}\coloneqq\\{a_{\ell},a_{i},a_{i+1}\\}$ for
$i\in[\ell+1,\alpha-1]$. We connect these bags in a line: $B_{1}\leftrightline
B_{2}\leftrightline B_{a_{\alpha-1}}\leftrightline
B_{a_{\alpha-2}}\leftrightline\cdots\leftrightline B_{a_{\ell+1}}$. It is easy
to see that it is indeed a valid tree decomposition of $H$.

To materialize $B_{1}$, note that there are $\mathcal{O}(m)$ choices for an
adjacent pair of nodes from $V_{a_{0}}^{\delta_{a_{0}}}$ and
$V_{b_{1}}^{\delta_{b_{1}}}$. Then there are
$\mathcal{O}(m^{\delta_{b_{1}}f})\leq\mathcal{O}(m^{(\gamma+\ell)f})$ choices
to pick a node in $V_{b_{2}}^{\delta_{b_{2}}}$ as a neighbor of the chosen
node in $V_{a_{0}}^{\delta_{a_{0}}}$. Then, for each $i\in[\gamma]$, there are
$\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor of
the chosen node in $V_{a_{0}}^{\delta_{a_{0}}}$. Finally, for each
$i\in[\ell]$, there are
$\mathcal{O}(m^{\delta_{a_{i-1}}f})=\mathcal{O}(m^{f})$ choices to pick a node
in $V_{a_{i}}^{\delta_{a_{i}}}$ as a neighbor of the chosen node in
$V_{a_{i-1}}^{\delta_{a_{i-1}}}$. In total, this takes time
$\mathcal{O}(m^{1+((\gamma+\ell)+\gamma+\ell)f})\leq\mathcal{O}(m^{1+(2\gamma+\alpha)f})\leq\mathcal{O}(m^{2-f})$
due to the fact that $\ell\leq\alpha/2$ and Lemma 8.27.

To materialize $B_{2}$, note that the number of choices to pick a node in
$V_{a_{\ell}}^{\delta_{a_{\ell}}}$ is
$\mathcal{O}(|V_{a_{\ell}}^{\delta_{a_{\ell}}}|)=\mathcal{O}(m^{1-(\delta_{a_{\ell}}-1)f})\leq\mathcal{O}(m^{1-(\gamma+1)f})$.
There are $\mathcal{O}(m)$ choices to pick an adjacent pair of nodes
$V_{b_{2}}^{\delta_{b_{2}}}$ and $V_{b_{3}}^{\delta_{b_{3}}}$. Then, for each
$i\in[\gamma]$, there are $\mathcal{O}(m^{f})$ choices to pick a node in
$V_{c_{i}}$ as a neighbor of the chosen node in $V_{b_{3}}^{\delta_{b_{3}}}$.
In total, this takes time $\mathcal{O}(m^{(1-(\gamma+1)f)+1+\gamma
f})=\mathcal{O}(m^{2-f})$.

Each bag $B_{a_{i}}$, for $i\in[\ell+1,\alpha-1]$, can be materialized in time
$\mathcal{O}(m^{2-f})$, because there are $\mathcal{O}(m)$ choices for a pair
of adjacent nodes from $V_{a_{i}}^{\delta_{a_{i}}}$ and
$V_{a_{i+1}}^{\delta_{a_{i+1}}}$, and the number of choices for a node from
$V_{a_{\ell}}^{\delta_{a_{\ell}}}$ is
$\mathcal{O}(|V_{a_{\ell}}^{\delta_{a_{\ell}}}|)\leq\mathcal{O}(m^{1-(\gamma+1)f})\leq\mathcal{O}(m^{1-f})$.
Hence, we get a full $H$-encoding of $G$ in time $\mathcal{O}(m^{2-f})$.

Figure 21: An example of a tree decomposition of $P(\alpha,\beta,\gamma\times
2)$ for Special Case 5 of Lemma 7.11 for $\alpha=7$, $\beta=3$, $\gamma=2$,
and $\ell=3$.

This concludes the list of high-degree-low-degree algorithms we use. We now
turn to the general case.

####  7.2.2 General Case: Algorithms Involving “Hyperdegree” Splitting

Let us recall which assumptions we already have. We have
$\delta_{a_{0}}=\delta_{a_{\alpha}}=1$, $\delta_{\max}\geq 2\gamma+2$, and
none of the cases above are applicable.

We first build a partial $H$-encodings $\mathcal{E}_{1}$ of $G$ and a partial
$H^{\prime}$-encoding $\mathcal{E}^{\prime}_{2}$ of $G[H^{\prime}]$, where
$H^{\prime}\coloneqq H-\\{a_{1},\ldots,a_{\alpha-1}\\}$, such that
$\mathcal{E}^{\prime}_{2}$ has
$B_{\textup{ends}}\coloneqq\\{b_{0},b_{\beta}\\}$ as one of the bags of its
underlying tree decomposition. We will later extend $\mathcal{E}^{\prime}_{2}$
to a partial $H$-encoding $\mathcal{E}_{2}$ of $G$, such that
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ together constitute a full
$H$-encoding of $G$. That is, each $H$-subgraph $\overline{v}$ of $G$ is
encoded by exactly one of them.

We have two options of how we will accomplish that.

##### Option 1

In the first option in time $\mathcal{O}(m^{2-f})$ we create $\mathcal{E}_{1}$
and $\mathcal{E}^{\prime}_{2}$, where the submaterialization
$S_{\textup{ends}}$ of $B_{\textup{ends}}$ in $\mathcal{E}^{\prime}_{2}$ has
size $\mathcal{O}(m^{2-kf})$ for $k\coloneqq\delta_{\max}-2\gamma\geq 2$.

As the degrees of nodes in $V_{b_{0}}^{\delta_{b_{0}}}$ are smaller than
$m^{f}$, in time $\mathcal{O}(m^{1+(\gamma-1)f})$ we can materialize a bag
$B_{b_{0}\to c}\coloneqq\\{b_{0},c_{1},c_{2},\ldots,c_{\gamma}\\}$: there are
$\mathcal{O}(m)$ choices for an adjacent pair of nodes from
$V_{b_{0}}^{\delta_{b_{0}}}$ and $V_{c_{1}}$, and there are
$\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor of
the chosen node in $V_{b_{0}}^{\delta_{b_{0}}}$, for each $i\in[2,\gamma]$. By
using a binary search tree as a dictionary we can store for every tuple of
nodes from parts $V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$ all their common
neighbors in $V_{b_{0}}^{\delta_{b_{0}}}$ in time
$\widetilde{\mathcal{O}}(m^{1+(\gamma-1)f})\leq\mathcal{O}(m^{2-f})$ (due to
Lemma 8.11). Note that $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is one of the
listed tuples as they have a common neighbor $v_{b_{0}}\in
V_{b_{0}}^{\delta_{b_{0}}}$. Now we split the listed tuples of nodes into the
ones that have less than $m^{1-(\delta_{\max}-\gamma-1)f}$ common neighbors in
$V_{b_{0}}^{\delta_{b_{0}}}$ (low-degree tuples $C^{\textup{lo}}$) and the
ones that have at least $m^{1-(\delta_{\max}-\gamma-1)f}$ common neighbors
(high-degree tuples $C^{\textup{hi}}$). Similarly to nodes from parts
$V_{a_{i}}$ and $V_{b_{i}}$, we deal with low- and high-degree tuples
separately. We distinguish two cases, in one of which we create
$\mathcal{E}_{1}$, and in the other one we create $\mathcal{E}^{\prime}_{2}$.

###### Option 1: Case 1: $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a high-degree
tuple.

The total number of copies of $B_{b_{0}\to c}$ that we generated is at most
$m^{1+(\gamma-1)f}$. Hence, there are
$\mathcal{O}(m^{1+(\gamma-1)f}/m^{1-(\delta_{\max}-\gamma-1)f})=\mathcal{O}(m^{(\delta_{\max}-2)f})$
high-degree tuples of nodes from parts
$V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$. Furthermore, due to Section 3.4,
there are at most $m^{1-(\delta_{\max}-1)f}$ nodes in
$V_{d_{\max}}^{\delta_{d_{\max}}}$. Consider the graph
$H-\\{d_{\max},c_{1},\ldots,c_{\gamma}\\}$. Since it is a tree, it has a tree
decomposition where each bag consists of two adjacent nodes. Adding
$d_{\max},c_{1},c_{2},\ldots,c_{\gamma}$ to every bag, we obtain a tree
decomposition of $H$ (see Figure 22).

We materialize each bag from this tree decomposition as follows. There are
$\mathcal{O}(m)$ choices for the two adjacent nodes. There are
$\mathcal{O}(m^{(\delta_{\max}-2)f})$ choices for a high-degree tuple from
$V_{c_{1}}\times V_{c_{2}}\times\cdots\times V_{c_{\gamma}}$. Finally, there
are at most $m^{1-(\delta_{\max}-1)f}$ choices for a node from
$V_{d_{\max}}^{\delta_{d_{\max}}}$. Hence, we can materialize these bags in
time
$\mathcal{O}(m^{1+(\delta_{\max}-2)f+(1-(\delta_{\max}-1)f)})=\mathcal{O}(m^{2-f})$.

Note that this partial $H$-encoding $\mathcal{E}_{1}$ encodes exactly such
$H$-subgraphs $\overline{v}$ of $G$, for which
$(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a high-degree tuple because for all
bags, only high-degree tuples $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ are listed.

Figure 22: An example of a tree decomposition of $P(\alpha,\beta,\gamma\times
2)$ for Case 1 of Option 1 of Lemma 7.11 for $\alpha=6$, $\beta=4$,
$\gamma=2$, and $d_{\max}=a_{4}$.

###### Option 1: Case 2: $(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree
tuple.

In time $\mathcal{O}(m^{1+(\gamma-1)f})$ we materialize a bag $B_{b_{\beta}\to
c}\coloneqq\\{b_{\beta},c_{1},c_{2},\ldots,c_{\gamma}\\}$ analogously to the
materialization of $B_{b_{0}\to c}$. Then for each low-degree tuple of nodes
from $V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$, we spend time
$\mathcal{O}(m^{1-(\delta_{\max}-\gamma-1)f})$ to materialize all their common
neighbors in $V_{b_{0}}^{\delta_{b_{0}}}$ by accessing the dictionary. This
way we create a submaterialization $S_{\textup{down}}$ of
$B_{\textup{down}}\coloneqq B_{b_{\beta}\to c}\cup\\{b_{0}\\}$ in time
$\mathcal{O}(m^{1+(\gamma-1)f}\cdot(\log
m+m^{1-(\delta_{\max}-\gamma-1)f}))=\mathcal{O}(m^{2-(\delta_{\max}-2\gamma)f})=\mathcal{O}(m^{2-kf})\leq\mathcal{O}(m^{2-2f})$.
Note that for an $H$-subgraph $\overline{v}$, we have that
$(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple if and only if
$\left.\overline{v}\right|_{B_{\textup{down}}}\in S_{\textup{down}}$. We
attach a bag $B_{\textup{ends}}\coloneqq\\{b_{0},b_{\beta}\\}$ to
$B_{\textup{down}}$ and create its submaterialization $S_{\textup{ends}}$ as a
set of projections of the elements of $S_{\textup{down}}$ onto
$B_{\textup{ends}}$. This takes time
$\widetilde{\mathcal{O}}(|S_{\textup{down}}|)=\widetilde{\mathcal{O}}(m^{2-kf})\leq\widetilde{\mathcal{O}}(m^{2-2f})\leq\mathcal{O}(m^{2-f})$,
and we have $|S_{\textup{ends}}|\leq|S_{\textup{down}}|=\mathcal{O}(m^{2-kf})$
as promised. It remains to attach the decomposition of the path
$b_{0}\leftrightline b_{1}\leftrightline\cdots\leftrightline b_{\beta}$ to
$B_{\textup{ends}}$ to complete the partial $H^{\prime}$-encoding
$\mathcal{E}^{\prime}_{2}$ of $G[H^{\prime}]$.

We consider $V_{b_{0}},\ldots,V_{b_{\beta}}$ as an instance of Biased Cycle
for $\ell=k$, where we think of edges of $G$ between $V_{b_{i-1}}$ and
$V_{b_{i}}$ for $i\in[\beta]$ as the blue edges, and we think of
$S_{\textup{ends}}$ as the red edges between $V_{b_{0}}$ and $V_{b_{\beta}}$.
We apply Lemma 7.7 to create a full encoding of this Biased Cycle. If
$k>\frac{\beta+1}{2}$, it works in time $\mathcal{O}(m^{2-f})$, and if
$k\leq\frac{\beta+1}{2}$, it works in time

$\displaystyle\mathcal{O}(m^{2-f}+m^{1+(\delta_{b_{k.\,.\beta-k}}+k-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+((\beta-2k+1)\cdot\delta_{\max}+k-1)f})$
$\displaystyle=\mathcal{O}(m^{2-f}+m^{1+((\beta-2k+1)\cdot(k+2\gamma)+k-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}),$

where the last inequality holds due to Lemma 8.29.

As there is an edge $\\{b_{0},b_{\beta}\\}$ in this instance of Biased Cycle,
we can attach the resulting tree decomposition with a partial encoding to
$B_{\textup{ends}}$ by a bag containing both $b_{0}$ and $b_{\beta}$. Hence,
we create a partial $H^{\prime}$-encoding $\mathcal{E}^{\prime}_{2}$ of
$G[H^{\prime}]$. Note that $\mathcal{E}^{\prime}_{2}$ encodes exactly such
$H^{\prime}$-subgraphs $\overline{v}$ of $G[H^{\prime}]$, for which
$(v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple because for
$B_{\textup{ends}}$, only low-degree tuples
$(v_{c_{1}},\ldots,v_{c_{\gamma}})$ are listed.

Combining the two cases together, we get that $\mathcal{E}_{1}$ encodes only
such $H$-subgraphs $\overline{v}$ of $G$, for which
$\left.\overline{v}\right|_{\\{c_{1},\ldots,c_{\gamma}\\}}$ is a high-degree
tuple, and $\mathcal{E}^{\prime}_{2}$ encodes only such $H^{\prime}$-subgraphs
$\overline{v}^{\prime}$ of $G[H^{\prime}]$, for which
$\left.\overline{v}^{\prime}\right|_{\\{c_{1},\ldots,c_{\gamma}\\}}$ is a low-
degree tuple. Hence, when we extend $\mathcal{E}^{\prime}_{2}$ to
$\mathcal{E}_{2}$, no $H$-subgraph of $G$ can be encoded by both
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. And on the other hand, for each
$H$-subgraph $\overline{v}$ of $G$, we have that
$\left.\overline{v}\right|_{\\{c_{1},\ldots,c_{\gamma}\\}}$ is either a high-
degree tuple or a low-degree tuple. Hence, either $\overline{v}$ is encoded by
$\mathcal{E}_{1}$ or $\left.\overline{v}\right|_{V(H^{\prime})}$ is encoded by
$\mathcal{E}^{\prime}_{2}$, and thus we later will encode $\overline{v}$ by
$\mathcal{E}_{2}$.

##### Option 2

In the second option in time
$\mathcal{O}(m^{2-f})+\widetilde{\mathcal{O}}(m^{2-k^{\prime}f})$ we create
$\mathcal{E}_{1}$ and $\mathcal{E}^{\prime}_{2}$, where the submaterialization
$S_{\textup{ends}}$ of $B_{\textup{ends}}$ in $\mathcal{E}^{\prime}_{2}$ has
size $\mathcal{O}(m^{2-k^{\prime}f})$ for
$k^{\prime}\coloneqq\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+\delta_{b_{1}}+\delta_{b_{3.\,.\beta-1}})$.

We materialize the bag

$B_{1}\coloneqq\\{b_{0},b_{1},b_{2},c_{1},c_{2},\ldots,c_{\gamma}\\}.$

To this end, note that there are $\mathcal{O}(m)$ choices for a pair of
adjacent nodes from $V_{b_{0}}^{\delta_{b_{0}}}$ and
$V_{b_{1}}^{\delta_{b_{1}}}$. Then there are
$\mathcal{O}(m^{\delta_{b_{1}}f})$ choices to pick a node in
$V_{b_{2}}^{\delta_{b_{2}}}$ as a neighbor of the chosen node in
$V_{b_{1}}^{\delta_{b_{1}}}$. Finally, for each $i\in[\gamma]$, there are
$\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor of
the chosen node in $V_{b_{0}}^{\delta_{b_{0}}}$. In total, this takes time
$\mathcal{O}(m^{1+(\delta_{b_{1}}+\gamma)f})\leq\mathcal{O}(m^{2-k^{\prime}f})$.
By using a binary search tree as a dictionary we can store for every tuple of
nodes from parts
$V_{b_{2}}^{\delta_{b_{2}}},V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$ all
their common pairs of neighbors in $V_{b_{0}}^{\delta_{b_{0}}}$ and
$V_{b_{1}}^{\delta_{b_{1}}}$ in time
$\widetilde{\mathcal{O}}(m^{1+(\delta_{b_{1}}+\gamma)f})\leq\mathcal{O}(m^{2-k^{\prime}f})$.
Note that $(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ is one of the listed
tuples as they have a common pair of neighbors $(v_{b_{0}},v_{b_{1}})\in
V_{b_{0}}^{\delta_{b_{0}}}\times V_{b_{1}}^{\delta_{b_{1}}}$. Now we split the
listed tuples of nodes into the ones that have less than
$m^{(\gamma+\delta_{b_{1}}+1)f}$ common pairs of neighbors in
$V_{b_{0}}^{\delta_{b_{0}}}$ and $V_{b_{1}}^{\delta_{b_{1}}}$ (low-degree
tuples $D^{\textup{lo}}$) and the ones that have at least
$m^{(\gamma+\delta_{b_{1}}+1)f}$ common pairs of neighbors (high-degree tuples
$D^{\textup{hi}}$). Similarly to nodes from parts $V_{a_{i}}$ and $V_{b_{i}}$,
we deal with low- and high-degree tuples separately. We distinguish two cases,
in one of which we create $\mathcal{E}_{1}$, and in the other one we create
$\mathcal{E}^{\prime}_{2}$.

###### Option 2: Case 1: $(v_{b_{1}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a
high-degree tuple.

The total number of copies of $B_{1}$ that we generated is
$\mathcal{O}(m^{1+(\delta_{b_{1}}+\gamma)f})$. Hence, there are
$\mathcal{O}(m^{1+(\delta_{b_{1}}+\gamma)f}/m^{(\gamma+\delta_{b_{1}}+1)f})=\mathcal{O}(m^{1-f})$
high-degree tuples of nodes from parts
$V_{b_{2}}^{\delta_{b_{2}}},V_{c_{1}},\ldots,V_{c_{\gamma}}$. Consider the
graph $H-\\{b_{2},c_{1},\ldots,c_{\gamma}\\}$. Since it is a tree, it has a
tree decomposition, where each bag consists of two adjacent nodes. Adding
$b_{2},c_{1},c_{2},\ldots,c_{\gamma}$ to every bag, we obtain a tree
decomposition of $H$. For each bag of this tree decomposition, we create its
submaterialization in time $\mathcal{O}(m^{2-f})$, as there are
$\mathcal{O}(m)$ choices for the two adjacent nodes and $\mathcal{O}(m^{1-f})$
choices for a high-degree tuple.

Note that this partial $H$-encoding $\mathcal{E}_{1}$ encodes exactly such
$H$-subgraphs $\overline{v}$, for which
$(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a high-degree tuple as for
all bags, only high-degree tuples
$(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ are listed.

###### Option 2: Case 2: $(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a
low-degree tuple.

We materialize the bag

$B_{2}\coloneqq\\{b_{2},b_{3},\ldots,b_{\beta},c_{1},c_{2},\ldots,c_{\gamma}\\}.$

To this end, note that there are $\mathcal{O}(m)$ choices for a pair of
adjacent nodes from $V_{b_{\beta}}^{\delta_{b_{\beta}}}$ and
$V_{b_{\beta-1}}^{\delta_{b_{\beta-1}}}$. Then, for each $i\in[\gamma]$, there
are $\mathcal{O}(m^{f})$ choices to pick a node in $V_{c_{i}}$ as a neighbor
of the chosen node in $V_{b_{\beta}}^{\delta_{b_{\beta}}}$. Finally, for each
$i\in\\{\beta-2,\beta-3,\ldots,2\\}$, there are
$\mathcal{O}(m^{\delta_{b_{i+1}}})$ choices to pick a node in
$V_{b_{i}}^{\delta_{b_{i}}}$ as a neighbor of the chosen node in
$V_{b_{i+1}}^{\delta_{b_{i+1}}}$. In total, this takes time
$\mathcal{O}(m^{1+(\gamma+\delta_{b_{3.\,.\beta-1}})f})\leq\mathcal{O}(m^{2-k^{\prime}f})$.

If the chosen nodes from parts
$V_{b_{2}},V_{c_{1}},V_{c_{2}},\ldots,V_{c_{\gamma}}$ form a low-degree tuple,
we spend time $\mathcal{O}(m^{(\gamma+\delta_{b_{1}}+1)f})$ to materialize all
their common pairs of neighbors in $V_{b_{0}}^{\delta_{b_{0}}}$ and
$V_{b_{1}}^{\delta_{b_{1}}}$ by accessing the dictionary. This way we create a
submaterialization $S_{\textup{down}}$ of $B_{\textup{down}}\coloneqq
B_{2}\cup\\{b_{0},b_{1}\\}$ in time

$\mathcal{O}(m^{1+(\gamma+\delta_{b_{3.\,.\beta-1}})f}\cdot(\log
m+m^{(\gamma+\delta_{b_{1}}+1)f}))=\mathcal{O}(m^{1+(2\gamma+\delta_{b_{1}}+\delta_{b_{3.\,.\beta-1}}+1)f})=\mathcal{O}(m^{2-k^{\prime}f}).$

Note that for an $H$-subgraph $\overline{v}$, we have that
$(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple if and
only if $\left.\overline{v}\right|_{B_{\textup{down}}}\in S_{\textup{down}}$.
We attach a bag $B_{\textup{ends}}\coloneqq\\{b_{0},b_{\beta}\\}$ to
$B_{\textup{down}}$ and create its submaterialization $S_{\textup{ends}}$ as a
set of projections of the elements of $S_{\textup{down}}$ onto
$B_{\textup{ends}}$. It takes time
$\widetilde{\mathcal{O}}(|S_{\textup{down}}|)=\widetilde{\mathcal{O}}(m^{2-k^{\prime}f})$,
and we have
$|S_{\textup{ends}}|\leq|S_{\textup{down}}|=\mathcal{O}(m^{2-k^{\prime}f})$ as
promised. Note that $B_{\textup{down}}\leftrightline B_{\textup{ends}}$ is a
tree decomposition of $H^{\prime}$, hence we get the partial
$H^{\prime}$-encoding $\mathcal{E}^{\prime}_{2}$ of $G[H^{\prime}]$. Note that
$\mathcal{E}^{\prime}_{2}$ encodes exactly such $H^{\prime}$-subgraphs
$\overline{v}$ of $G[H^{\prime}]$, for which
$(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ is a low-degree tuple because
for $B_{\textup{ends}}$, only low-degree tuples
$(v_{b_{2}},v_{c_{1}},\ldots,v_{c_{\gamma}})$ are listed.

Combining the two cases together, we get that $\mathcal{E}_{1}$ encodes only
such $H$-subgraphs $\overline{v}$ of $G$, for which
$\left.\overline{v}\right|_{\\{b_{2},c_{1},\ldots,c_{\gamma}\\}}$ is a high-
degree tuple, and $\mathcal{E}^{\prime}_{2}$ encodes only such
$H^{\prime}$-subgraphs $\overline{v}^{\prime}$ of $G[H^{\prime}]$, for which
$\left.\overline{v}^{\prime}\right|_{\\{b_{2},c_{1},\ldots,c_{\gamma}\\}}$ is
a low-degree tuple. Hence, when we extend $\mathcal{E}^{\prime}_{2}$ to
$\mathcal{E}_{2}$, no $H$-subgraph of $G$ can be encoded by both
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. And on the other hand, for each
$H$-subgraph $\overline{v}$ of $G$, we have that
$\left.\overline{v}\right|_{\\{b_{2},c_{1},\ldots,c_{\gamma}\\}}$ is either a
high-degree tuple or a low-degree tuple. Hence, either $\overline{v}$ is
encoded by $\mathcal{E}_{1}$ or $\left.\overline{v}\right|_{V(H^{\prime})}$ is
encoded by $\mathcal{E}^{\prime}_{2}$, and thus we later will encode
$\overline{v}$ by $\mathcal{E}_{2}$.

We now decide on which of the two options we use. Let
$\ell\coloneqq\max\\{k,k^{\prime}\\}$, where we recall that
$k=\delta_{\max}-2\gamma\geq 2$ and
$k^{\prime}=\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+\delta_{b_{1}}+\delta_{b_{3.\,.\beta-1}})$.
We claim that in time $\mathcal{O}(m^{2-f})$ we can create a partial
$H$-encoding $\mathcal{E}_{1}$ of $G$ and a partial $H^{\prime}$-encoding
$\mathcal{E}^{\prime}_{2}$ of $G[H^{\prime}]$, such that
$\mathcal{E}^{\prime}_{2}$ has
$B_{\textup{ends}}\coloneqq\\{b_{0},b_{\beta}\\}$ as one of its bags with
submaterialization $S_{\textup{ends}}$ of size $\mathcal{O}(m^{2-\ell f})$. To
do that, we use Option 1 if $k\geq k^{\prime}$ and Option 2 if $k^{\prime}\geq
k$. Hence, indeed $|S_{\textup{ends}}|=\mathcal{O}(m^{2-\ell f})$.
Furthermore, in Option 1 we work in time $\mathcal{O}(m^{2-f})$, and in the
second option we work in time
$\mathcal{O}(m^{2-f})+\widetilde{\mathcal{O}}(m^{2-k^{\prime}f})$. We use the
second option only if $k^{\prime}\geq k\geq 2$, and hence we have
$\mathcal{O}(m^{2-f})+\widetilde{\mathcal{O}}(m^{2-k^{\prime}f})=\mathcal{O}(m^{2-f})$.

We have a partial $H^{\prime}$-encoding $\mathcal{E}^{\prime}_{2}$ of
$G[H^{\prime}]$, and now we need to extend it to a partial $H$-encoding
$\mathcal{E}_{2}$ of $G$, such that $\mathcal{E}_{2}$ encodes some
$H$-subgraph $\overline{v}$ if and only if $\mathcal{E}^{\prime}_{2}$ encodes
$\left.\overline{v}\right|_{V(H^{\prime})}$.

We consider
$V_{a_{0}}^{\delta_{a_{0}}},\ldots,V_{a_{\alpha}}^{\delta_{a_{\alpha}}}$ as an
instance of Biased Cycle, where we think of edges of $G$ between
$V_{a_{i-1}}^{\delta_{a_{i-1}}}$ and $V_{a_{i}}^{\delta_{a_{i}}}$ for
$i\in[\alpha]$ as the blue edges, and we think of $S_{\textup{ends}}$ as the
red edges between $V_{a_{0}}^{\delta_{a_{0}}}$ and
$V_{a_{\alpha}}^{\delta_{a_{\alpha}}}$. We apply the algorithm from Lemma 7.7
to create a full encoding of this Biased Cycle. As we prove later, it works in
time $\mathcal{O}(m^{2-f})$. As there is an edge $\\{a_{0},a_{\alpha}\\}$ in
this instance of Biased Cycle, we can attach the resulting tree decomposition
with a partial encoding to $B_{\textup{ends}}$ by a bag containing both
$a_{0}$ and $a_{\alpha}$. Hence, we create the desired partial $H$-encoding
$\mathcal{E}_{2}$ of $G$.

It remains to show that when we use the algorithm from Lemma 7.7, it runs in
$\mathcal{O}(m^{2-f})$ time. To prove it, we consider eight cases. The exact
condition of each case includes negations of all previous cases, but we
sometimes omit them for conciseness. One can verify that it is a complete set
of cases.

###### Case 1: $\alpha\leq 2\ell-2$.

In this case $\ell>\frac{\alpha+1}{2}$, and the algorithm from Lemma 7.7 works
in time $\mathcal{O}(m^{2-f})$.

###### Case 2: $\alpha=2\ell-1$.

In this case the algorithm from Lemma 7.7 works in time

$\displaystyle\mathcal{O}(m^{2-f}+m^{1+(\delta_{a_{\ell.\,.\alpha-\ell}}+\ell-1)f})$
$\displaystyle=\mathcal{O}(m^{2-f}+m^{1+(\ell-1)f})$
$\displaystyle=\mathcal{O}(m^{2-f}+m^{1+(\alpha-1)/2\cdot f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}),$

where the last inequality holds due to Lemma 8.11.

###### Case 3: $\alpha\geq 2\ell$ and $\delta_{a_{r}}\geq 2$ for some
$r\in\\{0,\ldots,\ell-1,\alpha-\ell+1,\ldots,\alpha\\}$.

In this case the instance of Biased Cycle is $\ell$-reachable, and the
algorithm from Lemma 7.7 works in time $\mathcal{O}(m^{2-f})$.

###### Case 4: $\alpha\geq 2\ell$, $\delta_{a_{r}}=1$ for all
$r\in\\{0,\ldots,\ell-1,\alpha-\ell+1,\ldots,\alpha\\}$,
$\delta_{a_{\ell}}\geq\gamma+2$, and $\delta_{b_{\beta-1}}\geq\gamma+\ell+1$.

This cannot happen as Special Case 4 (see 7.2.1) would be applicable.

###### Case 4’: $\alpha\geq 2\ell$, $\delta_{a_{r}}=1$ for all
$r\in\\{0,\ldots,\ell-1,\alpha-\ell+1,\ldots,\alpha\\}$,
$\delta_{a_{\alpha-\ell}}\geq\gamma+2$, and $\delta_{b_{1}}\geq\gamma+\ell+1$.

This cannot happen as Special Case 4’ (see 7.2.1) would be applicable.

###### Case 5: $\alpha\geq 2\ell$ and $\delta_{a_{\ell}}\leq\gamma+1$.

In this case the algorithm from Lemma 7.7 runs time

$\displaystyle\mathcal{O}(m^{2-f}+m^{1+(\delta_{a_{\ell.\,.\alpha-\ell}}+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+(\delta_{a_{\ell}}+(\alpha-2\ell)\cdot\delta_{\max}+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+(\gamma+1+(\alpha-2\ell)\cdot(2\gamma+k)+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+(\gamma+(\alpha-2\ell)\cdot(2\gamma+\ell)+\ell)f})$
$\displaystyle=\mathcal{O}(m^{2-f}).$

The last equality holds as $\ell\geq k\geq 2$,

$\displaystyle\ell$ $\displaystyle\geq k^{\prime}$
$\displaystyle=\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+\delta_{b_{1}}+\delta_{b_{3.\,.\beta-1}})$
$\displaystyle\geq\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+(\beta-2)\cdot\delta_{\max})$
$\displaystyle=\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+(\beta-2)\cdot(2\gamma+k))$
$\displaystyle\geq\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+(\beta-2)\cdot(2\gamma+\ell)),$

and because of Lemma 8.35.

###### Case 5’: $\alpha\geq 2\ell$ and $\delta_{a_{\alpha-\ell}}\leq\gamma+1$.

This case is symmetric to the previous one.

###### Case 6: $\alpha\geq 2\ell$, $\delta_{b_{1}}\leq\gamma+\ell$,
$\delta_{b_{\beta-1}}\leq\gamma+\ell$, and $\beta\geq 4$.

In this case the algorithm from Lemma 7.7 runs in time

$\displaystyle\mathcal{O}(m^{2-f}+m^{1+(\delta_{a_{\ell.\,.\alpha-\ell}}+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+((\alpha-2\ell+1)\cdot\delta_{\max}+\ell-1)f})$
$\displaystyle=\mathcal{O}(m^{2-f}+m^{1+((\alpha-2\ell+1)\cdot(2\gamma+k)+\ell-1)f})$
$\displaystyle\leq\mathcal{O}(m^{2-f}+m^{1+((\alpha-2\ell+1)\cdot(2\gamma+\ell)+\ell-1)f})$
$\displaystyle=\mathcal{O}(m^{2-f}).$

The last equality holds as $\ell\geq k\geq 2$,

$\displaystyle\ell$ $\displaystyle\geq k^{\prime}$
$\displaystyle=\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+\delta_{b_{1}}+\delta_{b_{3.\,.\beta-1}})$
$\displaystyle\geq\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+(\gamma+\ell)+(\beta-4)\cdot\delta_{\max}+(\gamma+\ell))$
$\displaystyle=\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+(\gamma+\ell)+(\beta-4)\cdot(2\gamma+k)+(\gamma+\ell))$
$\displaystyle\geq\mathcal{F}(\alpha,\beta,\gamma)-(2\gamma+1+(\beta-4)\cdot(2\gamma+\ell)+2\cdot(\gamma+\ell)),$

and because of Lemma 8.37.

###### Case 7: $\alpha\geq 2\ell$, $\delta_{a_{r}}=1$ for all
$r\in\\{0,\ldots,\ell-1,\alpha-\ell+1,\ldots,\alpha\\}$,
$\delta_{a_{\ell}}\geq\gamma+2$, $\delta_{b_{1}}\leq\gamma+\ell$, and
$\beta=3$.

This cannot happen as Special Case 5 (see 7.2.1) would be applicable.

This concludes the proof of Lemma 7.11.

###  7.3 Proof of Lemma 2.19

Now we can put the pieces together to prove Lemma 2.19.

See 2.19

######  Proof 7.13 (Proof of Lemma 2.19).

Let $(\alpha,\beta,\gamma)\in\mathcal{P}^{\prime}$.

For $(\alpha,\beta,\gamma)=(1,0,0)$, $H$-Encoding can be solved in time
$\mathcal{O}(m)=\mathcal{O}(m^{2-1/1})$ by Lemma 7.1 and
$\mathcal{F}(\alpha,\beta,\gamma)=1$ by Lemma 8.3. For
$(\alpha,\beta,\gamma)=(2,1,0)$, $H$-Encoding can be solved in time
$\mathcal{O}(m^{2-1/2})$ by Lemma 7.3 and $\mathcal{F}(\alpha,\beta,\gamma)=2$
by Lemma 8.5. For $(\alpha,\beta,\gamma)=(k-2,2,0)$ with $k\geq 4$,
$H$-Encoding can be solved in time $\mathcal{O}(m^{2-\left\lceil
k/2\right\rceil})$ by Lemma 7.3 and
$\mathcal{F}(\alpha,\beta,\gamma)=\left\lceil k/2\right\rceil$ by Lemma 8.15.

Otherwise, we have $\alpha\geq\beta\geq 2$ and $\gamma\geq 1$. If
$\alpha=\beta=2$, then $H$-Encoding can be solved in time
$\mathcal{O}(m^{2-1/(\gamma+2)})$ by Lemma 7.5 and
$\mathcal{F}(\alpha,\beta,\gamma)=\gamma+2$ by Lemma 8.17. If
$\alpha>\beta=2$, then
$\mathcal{F}(\alpha,\beta,\gamma)=2\gamma+2+\left\lfloor\frac{\alpha-1}{2}\right\rfloor$
by Lemma 8.19, and Lemma 7.9 shows an algorithms with the desired time
complexity. Finally, if $\alpha\geq\beta>2$, Lemma 7.11 shows an algorithm
with the desired time complexity.

##  8 Algebraic Lemmas

Here we prove inequalities on $\mathcal{F}(\alpha,\beta,\gamma)$ that we used
in the previous sections.

In this section numbers $\alpha$, $\beta$, $\gamma$, $k$, and $\ell$ are
always assumed to be integers.

Let us recall that $\mathcal{F}(\alpha,\beta,\gamma)=$

$\begin{cases}2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{\beta}{2}-\frac{\alpha}{2}-2\gamma+2,&\text{if
$\alpha+\beta$ even, $\alpha>\beta$, and $\beta<\gamma+2$;}\\\
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\frac{3\beta}{2}-\frac{\alpha}{2}-3\gamma,&\text{if
$\alpha+\beta$ even, $3\beta<\alpha+6\gamma+8$, and ($\alpha=\beta$ or
$\beta\geq\gamma+2$);}\\\
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+3\beta-\alpha-6\gamma-4,&\text{if
$\alpha+\beta$ even, $2\beta\leq\alpha+4\gamma+6$, and
$3\beta\geq\alpha+6\gamma+8$;}\\\
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+\beta-\frac{\alpha}{2}-2\gamma+\frac{3}{2},&\text{if
$\alpha+\beta$ odd and $\beta<2\gamma+3$;}\\\
2\beta\gamma+\frac{\alpha\beta}{2}-\frac{\beta^{2}}{2}+2\beta-\frac{\alpha}{2}-4\gamma-\frac{3}{2},&\text{if
$\alpha+\beta$ odd, $2\beta\leq\alpha+4\gamma+6$, and $\beta\geq
2\gamma+3$;}\\\
2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2},&\text{if
$\alpha=0\bmod 4$ and $2\beta>\alpha+4\gamma+6$;}\\\
2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2}+\frac{3}{8},&\text{if
$\alpha$ is odd and $2\beta>\alpha+4\gamma+6$;}\\\
2\gamma^{2}+\alpha\gamma+\frac{\alpha^{2}}{8}+\frac{\alpha}{2}+\frac{1}{2},&\text{if
$\alpha=2\bmod 4$ and $2\beta>\alpha+4\gamma+6$.}\\\ \end{cases}$

######  Lemma 8.1.

The function $\mathcal{F}$ is well defined. That is, the eight cases from the
definition of $\mathcal{F}$ are disjoint and cover all
$(\alpha,\beta,\gamma)\in\mathbb{Z}^{3}_{\geq 0}$.

######  Proof 8.2.

Fix some $(\alpha,\beta,\gamma)\in\mathbb{Z}^{3}_{\geq 0}$. We prove that
there exists exactly one case from the definition of $\mathcal{F}$ that
$(\alpha,\beta,\gamma)$ satisfies.

If $2\beta>\alpha+4\gamma+6$, then the last three cases from the definition of
$\mathcal{F}$ disjointly cover all triples
$(\alpha,\beta,\gamma)\in\mathbb{Z}^{3}_{\geq 0}$ depending on the reminder of
$\alpha$ modulo four. On the other hand, if $2\beta>\alpha+4\gamma+6$, none of
the first five cases are applicable. Case one fails as
$2\beta>\alpha+4\gamma+6>2\gamma+4$ contradicts $\beta<\gamma+2$. Case two
fails as $2\beta>\alpha+4\gamma+6$ implies $3\beta=3/2\cdot(2\beta)\geq
3/2\alpha+3/2\cdot(4\gamma)+3/2\cdot 6\geq\alpha+6\gamma+9$, contradicting
$3\beta<\alpha+6\gamma+8$. Conditions of case three directly contradict