$\operatorname{tw}:=\operatorname{tw}(H)\geq 3$. We continue using the
notation and terminology (e.g. “configuration”) as described in Section 3.2.

We apply Lemma 5.2 to convert the tree decomposition into a
$\operatorname{tw}$-wise tree decomposition
$\mathcal{T}_{2}=(T_{2},\\{X_{t}\\}_{t\in V(T_{2})})$. Since
$|T_{1}|=\operatorname{poly}(k)$, the time this conversion takes is certainly
negligible. Furthermore, $|T_{2}|=\operatorname{poly}(k)$. To simplify our
algorithm further, we also modify $\mathcal{T}_{2}$ further. Specifically, we
introduce a new type of helper node, a binary-merge node, which replaces merge
nodes. It is a node that has either zero or two children, both with the same
bag as itself. Those children are either binary-merge nodes or intermediate-
result nodes. We convert $\mathcal{T}_{2}$ into a new tree decomposition
$\mathcal{T}:=(T,\\{X_{t}\\}_{t\in V(T)})$ that has binary-merge nodes instead
of merge nodes by repeatedly taking any remaining merge node $t$ with more
than two children, splitting its set of children into two non-empty sets $A$
and $B$, creating two new children $t^{\prime}$ and $t^{\prime\prime}$ of $t$
and making the vertices from $A$ children of $t^{\prime}$ and the vertices of
$B$ children of $t^{\prime\prime}$. For any merge node $t$ with only a single
child, we create a new leaf with the same bag and let it be a child of $t$.
Correctness and negligibility of the conversion time is immediate, and the new
tree decomposition still has size $\operatorname{poly}(k)$. We now do dynamic
programming over $\mathcal{T}$.

In deviation from the proof of Theorem 5.4, our dynamic programming table is
structured differently. Instead of having only a single function of finite
domain for each helper node $t$, we have one function for each $t$ and each
achievable weight. Since the instance is edge-weighted, the achievable weights
must all lie in $\mathcal{W}:=\\{-k^{2}W,\ldots,k^{2}W\\}$.

Specifically, for each helper node $t\in\operatorname{help}(T)$ and each
weight $W^{\prime}\in\mathcal{W}$ we store the following function of finite
domain from configurations of $X_{t}$ to truth values. Remember that
$\operatorname{ParSolE}(R;I;J;W)$ is true if and only if $R$ is a partial
solution of $I$ in $J$ with an extension of weight $W$.

$\displaystyle d_{t,W^{\prime}}$
$\displaystyle:\mathcal{Conf}(X_{t})\to\\{\mathrm{true},\mathrm{false}\\}$
$\displaystyle d_{t,W^{\prime}}(R)$
$\displaystyle:=\operatorname{ParSolE}(R;X_{t};V_{t};W^{\prime})$

i.e. we store for each configuration whether it is a partial solution of
$X_{t}$ in the cone $V_{t}$ that has an extension of weight $W^{\prime}$. We
call these functions DP functions (where DP stands for dynamic programming).
Since there are $n^{\operatorname{tw}}$ many configurations for $X_{t}$, each
DP function $d_{t,W^{\prime}}$ can be specified using $n^{\operatorname{tw}}$
many bits.

We calculate the DP functions $d_{t}$ for all $t\in\operatorname{help}(T)$ in
a bottom-up manner. The overall picture of the algorithm is as follows: At a
non-leaf binary-merge node $t$, we take the DP functions of both children and
do a boolean convolution. At an intermediate-vertex node $t$, we first convert
the DP functions of the children of its $\operatorname{tw}$-wise child to
tensors with Laurent polynomials as entries, calculate their
$\operatorname{tw}$-wise matrix product, convert it back to a DP function and
then do a boolean convolution with the DP function of its merge node child.

We now describe the algorithm in detail, beginning with the leaves of $T$.
Hence $t$ be a merge node with no children. Since $X_{t}=V_{t}$, we have that
$d_{t,W^{\prime}}(R)$ is true if and only if $R$ is a valid configuration and
$W^{\prime}=0$. Clearly this takes total time at most
$O(n^{\operatorname{tw}}W\operatorname{poly}(k))$.

Now let $t\in\operatorname{help}(T)$ be an inner node of $T$. There are two
cases: either $t$ is an intermediate-result node, or $t$ is a merge node.

$t$ is a binary-merge node:

Let $t$ be a binary-merge node with children $t^{\prime}$ and
$t^{\prime\prime}$. For each configuration $R$ we have

$\displaystyle d_{t,W^{\prime}}(R)$
$\displaystyle=\operatorname{ParSolE}(R;X_{t};V_{t};W^{\prime})=\operatorname{ParSolE}(R;X_{t};V_{t^{\prime}}\cup
V_{t^{\prime\prime}};W^{\prime})$ $\displaystyle=\exists
W_{1}:\operatorname{ParSolE}(R;X_{t^{\prime}};V_{t^{\prime}};W_{1})\land\operatorname{ParSolE}(R;X_{t^{\prime\prime}};W^{\prime}-W_{1})$
$\displaystyle=\exists W_{1}:d_{t^{\prime},W_{1}}(R)\land
d_{t^{\prime\prime},W^{\prime}-W_{1}}(R)$

This can be calculated using a boolean convolution for each configuration.
Specifically, for each configuration $R$ we define the finitely supported
functions $f_{R},g_{R}:\mathbb{Z}\to\\{\mathrm{true},\mathrm{false}\\}$ as
$f_{R}(x):=d_{t^{\prime},x}(R)$ if $x\in\mathcal{W}$ and $\mathrm{false}$
otherwise, and analogously $g_{R}(x):=d_{t^{\prime\prime},x}(R)$ if
$x\in\mathcal{W}$ and $\mathrm{false}$ otherwise. We now use the boolean
convolution of these functions, defined as $(f_{R}\ast
g_{R})(x):=\bigvee_{z=-\infty}^{\infty}f_{R}(z)\land g_{R}(x-z)$. We have that
$(f_{R}\ast g_{R})(W^{\prime})=(\exists W_{1}:f_{R}(W_{1})\land
g_{R}(W^{\prime}-W_{1}))=d_{t,W^{\prime}}(R)$. Since $f_{R}$ and $g_{R}$ only
have non-zero values in a range of size $O(W\operatorname{poly}(k))$, the
boolean convolution $f_{R}\ast g_{R}$ can be calculated in time $O(W\log
W\operatorname{poly}(k))$888This is a standard result which can be achieved
e.g. by using the Fast Fourier Transform..

Since there are at most $n^{\operatorname{tw}}$ many possible configurations
$R$, $d_{t,W^{\prime}}$ can be calculated for all $W^{\prime}$ in time
$O(n^{\operatorname{tw}}W\log W\operatorname{poly}(k))$. Hence this is the
maximum running time we need per binary-merge node.

$t$ is an intermediate-result node:

Let $t$ be an intermediate-result node with $\operatorname{tw}$-wise child
node $t^{\prime}$ and merge node $t^{\prime\prime}$. By definition we have
$X_{t}=X_{t^{\prime\prime}}$. Furthermore
$|\operatorname{children}(t^{\prime})|=\operatorname{tw}$, and we can
(temporarily) rename the nodes in $X_{t^{\prime}}$ to
$X_{t^{\prime}}=\\{v,u_{1},\ldots,u_{\operatorname{tw}}\\}$ such that
$X_{t^{\prime}}=X_{t}\cup\\{v\\}$ and $\forall i\in[k]:\exists
c(i)\in\operatorname{children}(t^{\prime}):X_{t^{\prime}}=X_{c(i)}\cup\\{u_{i}\\}$.

First, we deal with calculating the weight of an extension for a configuration
of the bag of the $\operatorname{tw}$-wise node. Let $R$ be a partial solution
of $X_{t^{\prime}}$ in $V_{t^{\prime}}$ and let $S$ be an extension of $R$
(i.e. a compatible configuration of $V_{t}$). Notice that we get the following
formula for the weight of the extension $S$:

$w_{ext}(S,R)\overset{\text{def.}}{=}w(S)-w(S|_{X_{t^{\prime}}})=\underbrace{\left(\sum_{i\in[\operatorname{tw}]}w_{ext}(S|_{V_{c(i)}},S|_{X_{c(i)}})\right)}_{\text{Part
A}}+\underbrace{w_{ext}(S|_{X_{t^{\prime}}},S|_{X_{t^{\prime}}\setminus\\{v\\}})}_{\text{Part
B}}$

Part A is the combined weight of the edges which are not in $X_{t^{\prime}}$.
Compared to the left hand side, it is missing the weight of all edges going
from $v$ to $X_{t^{\prime}}\setminus\\{v\\}$, which is exactly what is then
added in Part B. Recall that
$w_{ext}(S|_{X_{t^{\prime}}},S|_{X_{t^{\prime}}\setminus\\{v\\}})=\sum_{u\in
X_{t^{\prime}}\setminus\\{v\\}}w(S(v)S(u))$.

Hence we can calculate the DP function for $t$ as follows for each
configuration $R$:

$\displaystyle d_{t,W^{\prime}}(R)$
$\displaystyle=\operatorname{ParSolE}(R;X_{t};V_{t};W^{\prime})$
$\displaystyle=\exists
W_{v}:\operatorname{ParSolE}(R;X_{t^{\prime\prime}};V_{t^{\prime\prime}};W_{v})\land\exists
W_{1},\ldots,W_{\operatorname{tw}}:\exists v^{\prime}\in f^{-1}(v):$
$\displaystyle\phantom{{}={}}w_{ext}((R\cup\\{v\mapsto
v^{\prime}\\}),R)+\sum_{i=1}^{\operatorname{tw}}W_{i}=W^{\prime}-W_{v}\land{}$
$\displaystyle\phantom{{}={}}\forall
i\in[\operatorname{tw}]:\operatorname{ParSolE}((R\cup\\{v\mapsto
v^{\prime}\\})|_{X_{c(i)}};X_{c(i)};V_{c(i)};W_{i})$ $\displaystyle=\exists
W_{v}:d_{t^{\prime\prime},W_{v}}(R)\land\exists
W_{1},\ldots,W_{\operatorname{tw}}:\exists v^{\prime}\in f^{-1}(v):$
$\displaystyle\phantom{{}={}}w_{ext}((R\cup\\{v\mapsto
v^{\prime}\\}),R)+\sum_{i=1}^{\operatorname{tw}}W_{i}=W^{\prime}-W_{v}\land{}$
$\displaystyle\phantom{{}={}}\forall
i\in[\operatorname{tw}]:d_{c(i),W_{i}}((R\cup\\{v\mapsto
v^{\prime}\\})|_{X_{c(i)}})$ (${\dagger}$)

We show how to calculate the values of $d_{t,W^{\prime}}$ for all $W^{\prime}$
via a $\operatorname{tw}$-wise matrix product of Laurent polynomials. We
continue using the notation and nomenclature for indexing tensors via
configurations, as described in the proof of part 1 of Theorem 5.4, and
continue using truth values and 0/1 interchangeably.

We now define one 0-1-tensors $p_{i,W^{\prime}}$ for each
$i\in[\operatorname{tw}]$ and $W^{\prime}\in\mathcal{W}$, which is indexed by
configurations of $X_{c(i)}=X_{t^{\prime}}\setminus\\{u_{i}\\}$ with ordering
$(u_{1},\ldots,u_{i-1},v,u_{i+1},\ldots,u_{\operatorname{tw}})$. For a
configuration $R$ of $X_{c(i)}$ we define

$\displaystyle p_{i,W^{\prime}}[R]$
$\displaystyle:=\begin{cases}d_{c(1),W^{\prime}-\sum_{i=2}^{\operatorname{tw}}w(R(v)R(u_{i}))}(R)&\text{
if $i=1$}\\\ d_{c(2),W^{\prime}-w(R(v)R(u_{1}))}(R)&\text{ if $i=2$}\\\
d_{c(i),W^{\prime}}(R)&\text{ otherwise}\end{cases}$

Note that the weight of the part B above is now encoded in these tensors,
specifically in the ones for $i=1$ and $i=2$. In particular, we can expand
equation (${\dagger}$) as

$\displaystyle=\exists W_{v}:d_{t^{\prime\prime},W_{v}}(R)\land\exists
W_{1},\ldots,W_{\operatorname{tw}}:\sum_{i=1}^{\operatorname{tw}}W_{i}=W^{\prime}-W_{v}\land{}$
$\displaystyle\phantom{{}={}}\exists v^{\prime}\in f^{-1}(v):\forall
i\in[\operatorname{tw}]:p_{i,W_{i}}((R\cup\\{v\mapsto
v^{\prime}\\})|_{X_{c(i)}})$

Analogously to the computation of $p_{\text{res}}[R]$ in the proof of part 1
of Theorem 5.4, we have

$\displaystyle=\exists W_{v}:d_{t^{\prime\prime},W_{v}}(R)\land\exists
W_{1},\ldots,W_{\operatorname{tw}}:\sum_{i=1}^{\operatorname{tw}}W_{i}=W^{\prime}-W_{v}\land
MP_{\operatorname{tw}}(p_{1,W_{1}},\ldots,p_{\operatorname{tw},W_{\operatorname{tw}}})[R]$

We now show how to compute tensors $D_{W^{\prime}}$ for each
$W^{\prime}\in\mathcal{W}$ such that $D_{W^{\prime}}(R)=\exists
W_{1},\ldots,W_{\operatorname{tw}}:\sum_{i=1}^{\operatorname{tw}}W_{i}=W^{\prime}-W_{v}\land
MP_{\operatorname{tw}}(p_{1,W_{1}},\ldots,p_{\operatorname{tw},W_{\operatorname{tw}}})[R]$,
which would simplify the above to

$\displaystyle=\exists W_{v}:d_{t^{\prime\prime},W_{v}}(R)\land
D_{W^{\prime}-W_{v}}(R)$

and hence make it computable via a boolean convolution in time
$O(n^{\operatorname{tw}}W\log W\operatorname{poly}(k))$ (given the tensors
$D_{W^{\prime}}$).

We want to compute $D_{\widetilde{W}}$ for each $\widetilde{W}\in\mathcal{W}$.
Note how, when defining the OR of tensors to be calculated entrywise, we have

$\displaystyle D_{W^{\prime}}$
$\displaystyle=\bigvee_{\begin{subarray}{c}W_{1},\ldots,W_{\operatorname{tw}}\in\mathcal{W}\\\
W_{1}+\ldots+W_{\operatorname{tw}}=W^{\prime}\end{subarray}}\operatorname{MP}_{\operatorname{tw}}(p_{1,W_{1}},\ldots,p_{\operatorname{tw},W_{\operatorname{tw}(H)}})$

Indeed, the right-hand side can be calculated using a single
$\operatorname{tw}$-wise matrix product of tensors with polynomials as
entries. Let $T_{\operatorname{tw}}$ be the group of
order-$\operatorname{tw}(H)$ tensors of dimensions $n\times\ldots\times n$
with entries from $\\{\mathrm{true},\mathrm{false}\\}$. Define
$T_{\operatorname{tw}}[X,X^{-1}]$ as the group of Laurent polynomials with
elements of $T_{\operatorname{tw}(H)}$ as coefficients. Note how elements of
$T_{\operatorname{tw}}[X,X^{-1}]$ may also be viewed as tensors with Laurent
polynomials as entries, or as functions $f:\\{0,1\\}\to
T_{\operatorname{tw}(H)}$ when using the usual definition of scalar-tensor
AND.

We define $p_{i}(X):=\sum_{j\in\mathcal{W}}\,p_{i,j}\cdot X^{j}\in
T_{\operatorname{tw}(H)}[X,X^{-1}]$ for all $i$. Viewing them as tensors of
polynomials, we may calculate their $\operatorname{tw}(H)$-wise matrix
product. Viewing $\operatorname{MP}_{\operatorname{tw}}(p_{1},\ldots
p_{\operatorname{tw}})$ as polynomial again, it can be easily seen that the
coefficient tensor for $X^{W^{\prime}}$ is exactly

$\displaystyle\sum_{\begin{subarray}{c}W_{1},\ldots,W_{\operatorname{tw}}\in\mathcal{W}\\\
W_{1}+\ldots+W_{\operatorname{tw}}=W^{\prime}\end{subarray}}\operatorname{MP}_{\operatorname{tw}}(p_{1,W_{1}},\ldots,p_{\operatorname{tw},W_{\operatorname{tw}}})$

Thus, to compute $D_{W^{\prime}}$ for all $W^{\prime}$, it suffices to compute
$\operatorname{MP}_{\operatorname{tw}}(p_{1},\ldots,p_{\operatorname{tw}})$.

Hence, we have reduced the problem of calculating the tensors
$D_{\widetilde{W}}$ to computing the $\operatorname{tw}(H)$-wise matrix
product of tensors whose entries are Laurent polynomials of degree bounded (in
both directions) by $O(W\operatorname{poly}(k))$. By Lemma 5.9, this can be
done in time $O((n^{\operatorname{tw}(H)+1}W+n^{\operatorname{tw}(H)}W\log
W)poly(k))$.

Hence we have an overall running time of
$O((n^{\operatorname{tw}(H)+1}W+n^{\operatorname{tw}(H)}W\log W)poly(k))$ per
intermediate-result node.

Again, since the tree decomposition has $\operatorname{poly}(k)$ nodes, the
overall time the algorithm takes is
$O((n^{\operatorname{tw}(H)+1}W+n^{\operatorname{tw}(H)}W\log Wpoly(k))$.

After calculating $d_{t^{\prime},W^{\prime}}$ for each $t^{\prime}\in
T,W^{\prime}\in\mathcal{W}$, outputting the result is simple. We simply
extract the answer from the DP function of the root node. Let $r$ be the root
of $T$. We output YES if and only if $\exists R:d_{r,-w(R)}(R)=\mathrm{true}$.
By the definition of $d_{t^{\prime},-w(R)}$, this is the case if and only if
$R$ is a partial solution of $X_{r}$ in the cone $V_{r}=V(H)$ with an
extension of weight $-w(R)$. This is the case if and only if $R$ can be
expanded to a configuration for all of $V(H)$ such that its total weight is
$-w(R)+w(R)=0$. Hence, $\exists R:d_{t^{\prime},-w(R)}(R)=\mathrm{true}$ if
and only if the instance has a solution. Checking whether such an $R$ exists
can obviously be done in time
$O(n^{\operatorname{tw}(H)}\operatorname{poly}(k))$.

We now consider the second part of the theorem. Similarly to the weighted
case, it suffices to employ the algorithm from part 1.

######  Proof 5.12 (Proof (of part 2 of Theorem 5.8)).

In the algorithm for part 1, all running times except for the
$\operatorname{tw}(H)$-wise matrix product are bounded by
$O(n^{\operatorname{tw}}W\log W\operatorname{poly}(k))$. For
$\operatorname{tw}=2$, the $\operatorname{tw}$-wise matrix product is simply
matrix multiplication, which can be done in $O(n^{\omega})$. Thus, for
$\operatorname{tw}=2$ the running time is
$O(n^{\omega}W\operatorname{poly}(k)+n^{2}W\log W\operatorname{poly}(k))$.

Finally, we come to the third part of the theorem. For reasons outlined in the
proof of the previous theorem, the algorithm from part 1 does not work for
$\operatorname{tw}(H)=1$. Again, however, the result turns out to be quite
simple for this case.

######  Proof 5.13 (Proof (of part 3 of Theorem 5.8)).

Again, we only sketch the result, since it is easy to see. A simple dynamic
programming algorithm on trees can be applied, storing for each node which
configurations together with which weights can be achieved.

###  5.5 Colored Subgraph Isomorphism for Bounded Pathwidth

Surprisingly, Colored Subgraph Isomorphism can be solved slightly faster on
graphs of bounded pathwidth. This algorithm leverages rectangular matrix
multiplication.

We briefly discuss (rectangular) matrix multiplication and current algorithms
solving it. Multiplication of $n\times n$ by $n\times n$ matrices is perhaps
the most ubiquitous open problem in computer science, with the central
question being whether it can be done in $O(n^{2})$ time. The matrix
multiplication exponent $\omega$ has been slowly inching toward, but not quite
reaching, a value of 2 over the last few decades. In our algorithms, however,
we also multiply rectangular matrices. It turns out that the techniques used
in these fast algorithms for square matrix multiplication can also be
generalized to the rectangular case. In the following, let
$\operatorname{MM}(s,r,t)$ denote the time needed to multiply a matrix of size
$r\times s$ with a matrix of size $s\times t$. We are mostly interested in the
case that $s=n,r=n$ and $t=n^{k}$ for some $k\in\mathbb{R}^{+}$.

A simple, well-known result is that $\operatorname{MM}$ is both convex and
symmetrical in its arguments (see e.g. [52, 64]). In particular, we have
$\forall x\in\mathbb{R}^{+}:\operatorname{MM}(n,n,n^{k+x})\leq n^{x}\cdot
MM(n,n,n^{k})$ and
$\operatorname{MM}(n,n,n^{k})=\operatorname{MM}(n,n^{k},n)$. Letting
$\omega(k):=\log_{n}MM(n,n,n^{k})$, we immediately get $\forall k\geq
1:\omega(k)<k+1.373$ via the current bounds of $\omega(1)=\omega<2.373$ [49].

We can, however, do better: Le Gall [41] has shown that there are faster
algorithms based on the Coppersmith-Winograd method [30, 49] used for square
matrix multiplication. Among other values, he shows $\omega(0.31)=2$,
$\omega(2)<3.26$, $\omega(3)<4.2$, $\omega(4)<5.18$ and $\omega(5)<6.16$ (see
[41] for an extensive table of such values).

We now show how rectangular matrix multiplication can be used for bounded-
pathwidth pattern graphs.

######  Theorem 5.14.

There is an algorithm which, given an arbitrary instance $\phi=(H,G,f)$ of
Colored Subgraph Isomorphism, solves $\phi$ in time

  1. 1.

$O(n^{\omega(\operatorname{pw}(H)-1)}\operatorname{poly}(k)+g(k))$ when
$\operatorname{pw}(H)\geq 2$, and

  2. 2.

$O(n^{2}\operatorname{poly}(k))+g(k)$ when $\operatorname{pw}(H)=1$

where $k:=|H|$, $n$ is the size of the preimages of $f$, and $g$ is a
computable function.

This theorem implies Theorem 1.6 from the results section.

######  Proof 5.15.

Part 2 of the theorem is trivial, since for any graph, its treewidth is
smaller than its pathwidth. Hence, by application of Theorem 5.4, we achieve
the desired running time.

For part 1, let $G$, $H$ and $f:V(G)\to V(H)$ be given. The algorithm first
computes an optimal path decomposition $\mathcal{P}=(P,\\{X_{t}\\}_{t\in
V(T)})$ of $H$ in time $g(k)$ (see preliminaries), then does dynamic
programming over $\mathcal{P}$.

To unify nomenclature and notation with the case of treewidth, we talk about a
path as a tree rooted at one of its endpoints. As in the proof of Theorem 5.4,
we modify the path decomposition $\mathcal{P}$ to satisfy certain properties.
Specifically, we wish to obtain the following properties:

  1. 1.

The bags of the root and leaf of the path have size $\operatorname{pw}(H)$,
and every other bag has size $\operatorname{pw}(H)+1$

  2. 2.

For every $t\in V(P)$ with child $t^{\prime}$, we have $|X_{t}\cap
X_{t^{\prime}}|=\operatorname{pw}(H)$

These properties can be obtained with similar techniques as described in the
proof of part 1 of Theorem 5.4.

We now do dynamic programming on this modified path decomposition. We only
store values for each configuration of the separators $X_{t}\cap
X_{t^{\prime}}$. In particular, let $t^{\prime}$ be a node other than the
root, and let $t$ be its parent. As in Theorem 5.4, we only store

$\displaystyle d_{t^{\prime}}$ $\displaystyle:\mathcal{Conf}(X_{t}\cap
X_{t^{\prime}})\to\\{\mathrm{true},\mathrm{false}\\}$ $\displaystyle
d_{t^{\prime}}(R)$ $\displaystyle:=\operatorname{ParSol}(R;X_{t}\cap
X_{t^{\prime}};V_{t^{\prime}})$ (1)

We calculate these functions bottom-up. The case that $t^{\prime}$ is the leaf
is analogous to the corresponding case in Theorem 5.4, taking time
$O(n^{\operatorname{pw}(H)}\operatorname{poly}(k))$.

Now let $t^{\prime}$ with parent $t$ and child $t^{\prime\prime}$ be an inner
node of $P$. We define $\hat{v}$ to be the unique element with $\hat{v}\in
X_{t^{\prime}}\setminus X_{t}$ and similarly, $\hat{w}\in
X_{t^{\prime}}\setminus X_{t^{\prime\prime}}$ (or, if we would have
$\hat{v}=\hat{w}$, we take $\hat{w}$ to be some vertex from
$X_{t^{\prime}}\setminus\\{\hat{v}\\}$ instead), and finally
$E:=X_{t^{\prime}}\setminus\\{\hat{v},\hat{w}\\}$. Now if
$\hat{v}\hat{w}\notin E(H)$, the calculation is easy. Hence assume
$\hat{v}\hat{w}\in E(H)$. For a configuration $R$ of $X_{t}\cap
X_{t^{\prime}}$, we get the following alternate characterization of
$d_{t^{\prime}}(R)$:

$\displaystyle d_{t^{\prime}}(R)=$
$\displaystyle\operatorname{ValConf}(R;\\{\hat{w}\\}\cup E)\land{}$
$\displaystyle\exists v^{\prime}\in
f^{-1}(\hat{v}):\operatorname{ParSol}((R\cup\\{\hat{v}\mapsto
v^{\prime}\\})|_{X_{t^{\prime}}\setminus\\{\hat{w}\\}};\\{\hat{v}\\}\cup
E;V_{t^{\prime\prime}})\land v^{\prime}R(w)\in E(G)$

We describe how to calculate $d_{t^{\prime}}$ via rectangular matrix
multiplication. Much like in Theorem 5.4, the matrices are indexed by
configurations. In contrast to the former, however, one of the two dimensions
of the matrix might correspond to the configuration of multiple vertices.
Formally, for a vertex subset $Y\subseteq V(H)$ and a vertex $x\in
V(H),x\notin Y$, we call a matrix $A$ indexed by configurations of $(x,Y)$
when it is of dimensions $n\times n^{|Y|}$. We use two arbitrary bijections
$g_{\\{x\\}}:\mathcal{Conf}(\\{x\\})\to[n]$ and
$g_{Y}:\mathcal{Conf}(Y)\to[n^{|Y|}]$ which will help us map configurations of
$x$ and $Y$ to indices of the matrix. Hence, for a configuration $R$ of
$\\{x\\}\cup Y$, we define $A[R]:=A[g_{x}(R|_{\\{x\\}}),g_{Y}(R|_{Y})]$.

For our rectangular matrix product, we define a $n\times
n^{\operatorname{pw}(H)-1}$ matrix $B_{t^{\prime}}$ indexed by configurations
of $(\hat{v},E)$. For a configuration $R^{\prime}$ of $\\{\hat{v}\\}\cup E$,
we define

$\displaystyle
B_{t^{\prime}}[R^{\prime}]:=d_{t^{\prime\prime}}(R^{\prime})=\operatorname{ParSol}(R^{\prime};\\{\hat{v}\\}\cup
E;V_{t^{\prime\prime}})$

Now consider the adjacency matrix $Adj_{\hat{v},\hat{w}}$ of $f^{-1}(\hat{v})$
and $f^{-1}(\hat{w})$, indexed by configurations of $(\hat{w},\\{\hat{v}\\})$.
We make sure that the indexing bijection $g_{\\{\hat{v}\\}}$ as defined above
is the same for both $Adj_{\hat{v},\hat{w}}$ and $B_{t^{\prime}}$ and then
calculate the matrix product $Adj_{\hat{v},\hat{w}}\cdot B_{t^{\prime}}$.
Naturally, the product is indexed by configurations of $(\hat{w},E)$ and can
be expressed as

$\displaystyle(Adj_{\hat{v},\hat{w}}\cdot B_{t^{\prime}})[R^{\prime}]$
$\displaystyle\phantom{stuff}=\exists v^{\prime}\in
f^{-1}(\hat{v}):\operatorname{ParSol}((R^{\prime}\cup\\{\hat{v}\mapsto
v^{\prime}\\})|_{X_{t^{\prime}}\setminus\\{\hat{w}\\}};\\{\hat{v}\\}\cup
E;V_{t^{\prime\prime}})\land v^{\prime}R(w)\in E(G)$

Hence, we may write $d_{t^{\prime}}(R)$ as

$\displaystyle d_{t^{\prime}}(R)=\operatorname{ValConf}(R;\\{\hat{w}\\}\cup
E)\land(Adj_{\hat{v},\hat{w}}\cdot B_{t^{\prime}})[R]$ (1)

The algorithm to calculate $d_{t^{\prime}}$ is immediate. First, we calculate
the rectangular matrix product of $Adj_{\hat{v},\hat{w}}$ and $B_{t^{\prime}}$
in time $O(n^{\omega(\operatorname{pw}(H)-1)})$, then calculate
$d_{t^{\prime}}$ via formula 1. Checking whether $R$ is a valid configuration
of $\\{\hat{w}\\}\cup E$ can be done in time
$\operatorname{poly}(\operatorname{pw}(H))\leq\operatorname{poly}(k)$, giving
us a total time of at most
$O(n^{\omega(\operatorname{pw}(H)-1)}\operatorname{poly}(k))$ per inner node.

To output the answer, consider the child $r^{\prime}$ of the root $r$. We have
by definition that $d_{r^{\prime}}(R)$ is 1 if and only if $R$ is a partial
solution for $X_{r}$ in $V(H)$. Thus, the input is a YES-instance for Colored
Subgraph Isomorphism if and only if there is an $R$ such that
$d_{r^{\prime}}(R)$ is 1.

Since there is only a single leaf and $\operatorname{poly}(k)$ inner nodes,
total running time of the dynamic programming algorithm is
$O(n^{\omega(\operatorname{pw}(H)-1)}\operatorname{poly}(k))$.

###  5.6 Exact Weight Colored Subgraph Isomorphism for Bounded Pathwidth

The techniques of using rectangular matrix multiplication for the case of
pathwidth can also be applied to the weighted case, and they lead to
improvements in the expected way. Again, the instances may be either node- or
edge-weighted.

######  Theorem 5.16.

There is an algorithm which, given an arbitrary instance $\phi=(H,G,f,w)$ of
the Exact Weight Colored Subgraph Isomorphism problem, solves $\phi$ in time

  1. 1.

$O((n^{\omega(\operatorname{pw}(H)-1)}W+n^{\operatorname{pw}(H)}W\log
W)\operatorname{poly}(k)+g(k))$ when $\operatorname{pw}(H)\geq 2$, and

  2. 2.

$O((n^{2}W+nW\log W)\operatorname{poly}(k)+g(k))$ when
$\operatorname{pw}(H)=1$

where $k:=|V(H)|$, $n$ is the size of the preimages of $f$, $W$ is the maximum
absolute weight in the image of $w$, and $g$ is a computable function.

From this, Theorem 1.8 from the results section follows directly via Lemma
3.1.

######  Lemma 5.17.

Let two matrices $A,B$ of dimensions $r\times s$ and $s\times t$ be given,
such that each of their entries $A_{i,j},B_{j,k}\in\mathbb{C}[X,X^{-1}]$ (for
all $i\in[r],j\in[s],k\in[t]$) is a Laurent polynomial of degree bounded by
$W$ in both the positive and the negative direction. Then their product can be
computed in time $O(MM(r,s,t)W+(rs+st)W\log W)$

######  Proof 5.18.

Analogous to Lemma 5.9.

######  Proof 5.19 (Proof (of theorem 5.16)).

Again, we only need to prove an algorithm for the edge-weighted case due to
Proposition 4.17.

Part 2 is a corollary of Theorem 5.8, since for any graph, its treewidth is
smaller than its pathwidth.

For part 1, we only sketch the proof, since it is a straightforward
combination of the techniques used in the proofs of Theorems 5.8 and 5.14. We
use notation and phrasing from both of those proofs without further mention.

Given $G,H$ and $f$, we compute an optimal path decomposition
$(P,\\{X_{t}\\}_{t\in V(P)})$ for $H$ and do dynamic programming on the
modified path decomposition as described in the proof of Theorem 5.14. For
each non-root node $t^{\prime}\in P$ with parent $t$, for each weight
$W^{\prime}\in\mathcal{W}$ and for each configuration $R$ of $X_{t}\cap
X_{t^{\prime}}$, we store

$\displaystyle d_{t^{\prime},W^{\prime}}:=\operatorname{ParSolE}(R;X_{t}\cap
X_{t^{\prime}};V_{t^{\prime}};W^{\prime})$

The case that $t^{\prime}$ is a leaf is clear. For the case that $t^{\prime}$
is an inner node with parent $t$ and child $t^{\prime\prime}$, let
$\hat{v},\hat{w}$ be the unique elements with $\hat{v}\in
X_{t^{\prime}}\setminus X_{t},\hat{w}\in X_{t^{\prime}}\setminus
X_{t^{\prime\prime}}$ (or, if we would have $\hat{v}=\hat{w}$, we take
$\hat{w}$ to be some vertex from $X_{t^{\prime}}\setminus\\{\hat{v}\\}$
instead) and $E=X_{t^{\prime}}\setminus\\{\hat{v},\hat{w}\\}$. If
$\hat{v}\hat{w}\notin E(H)$, the calculation is easy, hence assume
$\hat{v}\hat{w}\in E(H)$. For each weight $W^{\prime}$, we build a rectangular
matrix $A_{t^{\prime}}^{W^{\prime}}$ indexed by $(\hat{v},E)$. The entry
corresponding to a configuration $R$ of $\\{\hat{v}\\}\cup E$ tells us whether
$R$ has an extension of weight $W^{\prime}+x$, where $x$ is the weight
contributed by $\hat{v}$ in $\\{\hat{v}\\}\cup E$. In particular
$x:=\sum_{\hat{u}\in E}w(R|_{\\{\hat{u},\hat{v}\\}})$.

We also use, for each weight $W^{\prime}$, an adjacency matrix
$Adj_{\hat{v},\hat{w}}^{W^{\prime}}$ defined for node-weighted instances as

$\displaystyle
Adj_{\hat{v},\hat{w}}^{W^{\prime}}[v^{\prime},w^{\prime}]=v^{\prime}w^{\prime}\in
E(G)\land w(v^{\prime}w^{\prime})=W^{\prime}$

We then create two Laurent polynomials of degree $|\mathcal{W}|$, one with the
matrices $Adj_{\hat{v},\hat{w}}^{W^{\prime}}$ as coefficients, one with the
matrices $A_{t^{\prime}}^{W^{\prime}}$. These can also be seen as matrices
with Laurent polynomials as entries. Using Lemma 5.17, we then calculate their
matrix product, which tells us for each weight $W^{\prime}$ and each
configuration $R$ of $\\{\hat{w}\\}\cup E$ if $R$ is a potential solution of
$\\{\hat{w}\\}\cup E$ in $V_{t^{\prime}}$ with an extension of weight
$W^{\prime}$, potentially missing edges between the preimage of $w$ and the
preimages of $E$. The latter can be checked for each entry. This leads to the
desired running time.

###  5.7 Improvements for the Node-Weighted Case

In the case of node weights instead of edge weights, some of the algorithms
can be slightly improved using rectangular matrix multiplication. However,
these improvements only work for the case that that the treewidth of $H$ is 1
and for the case of bounded pathwidth.

Specifically, we show the following two results, which imply Theorems 1.9 and
1.10 from the results section.

######  Theorem 5.20.

There is an algorithm which, given an arbitrary instance $\phi=(H,G,f,w)$ of
the node-weighted Exact Weight Colored Subgraph Isomorphism problem where $H$
is a tree, solves $\phi$ in time
$O(\operatorname{MM}(n,n,W)\operatorname{poly}(k)+nW\log
W\operatorname{poly}(k))$.

######  Theorem 5.21.

There is an algorithm which, given an arbitrary instance $\phi=(H,G,f,w)$ of
the node-weighted Exact Weight Colored Subgraph Isomorphism problem, solves
$\phi$ in time
$O(MM(n,n,n^{\operatorname{pw}(H)-1}W)\operatorname{poly}(k)+g(k))$.

######  Proof 5.22 (Proof (of Theorem 5.20)).

Let $G,f:V(G)\to V(H)$ and $w:V(G)\to\mathbb{Z}$ be given. All achievable
total weights must lie in $\mathcal{W}:=\\{-kW,\ldots,kW\\}$.

We do dynamic programming on the tree $H$. Rooting $H$ in an arbitrary vertex,
we define $T_{u}$ to be the subtree rooted at a node $u\in H$. For each weight
$W\in\mathcal{W}$, each node $v\in H$, we store the following function of
finite domain:

$\displaystyle d_{v,W}$
$\displaystyle:\mathcal{Conf}(\\{v\\})\to\\{\mathrm{true},\mathrm{false}\\}$
$\displaystyle d_{v,W}(R)$
$\displaystyle:=\operatorname{ParSolE}(R;\\{v\\};T_{v};W)$

We calculate the entries of these functions bottom-up, starting at the leaves
of $H$. If $v$ is a leaf, $d_{v,W}(R)$ is 1 if and only if $W=0$. Now suppose
$v$ is a non-leaf node of $H$ with set of children $C_{v}$. For each child
$u\in C_{v}$, we construct a rectangular matrix $p_{v}^{u}$. This matrix is
indexed by $w$ and $\mathcal{W}$. Formally, we call a matrix $A$ indexed by
$w$ and $\mathcal{W}$ if it has dimensions $n\times|\mathcal{W}|$. We use two
arbitrary bijections $g_{\\{v\\}}:\mathcal{Conf}(\\{v\\})\to[n]$ and
$g_{\mathcal{W}}:\mathcal{W}\to[|\mathcal{W}|]$ to help us map weights from
$\mathcal{W}$ and configurations of $v$ to indices of $A$. Correspondingly, we
define $A[R,W]:=A[g_{v}(R),g_{W}(W)]$.

We define $p_{v}^{u}$ as

$\displaystyle p_{v}^{u}[R,W]:=\operatorname{ParSolE}(R;\\{v\\};\\{v\\}\cup
T_{u};W)$

We may calculate this as follows. Let $Adj_{\\{v,u\\}}$ be the adjacency
matrix of $f^{-1}(v)$ and $f^{-1}(u)$ indexed by $(v,\\{u\\})$ (as defined in
the proof of Theorem 5.14), and let $\widetilde{d}_{u}$ be the rectangular
matrix indexed by $u$ and $\mathcal{W}$ and defined as
$\widetilde{d}_{u}[R,W]:=d_{u,W-w(R)}(R)$. We make sure that the indexing
bijection $g_{\\{u\\}}$ as defined above is the same for both $Adj_{v,u}$ and
$\widetilde{d}_{u}$ and then calculate the matrix product
$Adj_{v,u}\cdot\widetilde{d}_{u}$. The product is indexed by configurations of
$v$ and $\mathcal{W}$ and can be expressed as

$\displaystyle(Adj_{v,u}\cdot\widetilde{d}_{u})[R,W]$ $\displaystyle=\exists
u^{\prime}\in f^{-1}(u):R(v)u^{\prime}\in
E(G)\land\operatorname{ParSolE}(R;\\{u\\};T_{u};W-w(u^{\prime}))$
$\displaystyle=\operatorname{ParSolE}(R;\\{v\\};\\{v\\}\cup T_{u};W)$
$\displaystyle=p_{v}^{u}[R,W]$ Writing $C_{v}=\\{u_{1},\ldots,u_{c}\\}$ with
$c=|C_{v}|$, the function $d_{v,W}$ may then be expressed as $\displaystyle
d_{v,W}(R)$ $\displaystyle=\exists
W_{1},\ldots,W_{c}:\sum_{i=1}^{c}W_{i}=W\land\forall i:p_{v}^{u_{i}}[R,W_{i}]$

Similarly to the proof of Theorem 5.8, this may be calculated using a boolean
convolution. Accordingly, we define for each configuration $R$ of $v$ the
finitely supported functions
$f_{v,R}^{1},\ldots,f_{v,R}^{c}:\mathbb{Z}\to\\{\mathrm{true},\mathrm{false}\\}$
as $f_{v,R}^{i}(x):=p_{v}^{u_{i}}(R)$ if $x\in\mathcal{W}$, and 0 otherwise.
By a simple calculation, we get $d_{v,W}(R)=(f_{v,R}^{1}\ast\ldots\ast
f_{v,R}^{c})(W)$.

Finally, after having calculated all values of $d_{t^{\prime},W}(R)$ for all
$t^{\prime},W$ and $R$, we wish to output the result. Let $r$ be the root of
$H$. By definition of $d_{r,W}$, there is some configuration $R$ of $r$ such
that $d_{r,-w(R)}(R)=\mathrm{true}$ if and only if the instance has a
solution.

It remains to analyze the running time. For the leaves of $H$, the calculation
takes time $O(nW)$. For inner nodes, the calculation of the matrix product
$Adj_{\\{v,u\\}}\cdot\widetilde{d}_{u}$ takes time $\operatorname{MM}(n,n,W)$.
Finally, calculating the discrete convolutions takes time $O(nW\log W)$, since
any vertex of $v$ is involved as a child in at most one discrete convolution.
Hence, we arrive at the running time from the theorem.

######  Proof 5.23 (Proof (of Theorem 5.21)).

The proof uses a combination of the techniques from the proofs of Theorem 5.20
and Theorem 5.14.

Let $G,H,f:V(G)\to V(H)$ and $w:V(G)\to\mathbb{Z}$ be given. We compute an
optimal path decomposition in time $g(k)$, modify it as described in Theorem
5.14, obtaining a modified path decomposition
$\mathcal{P}=(P,\\{X_{t}\\}_{t\in P})$, and then do dynamic programming on
$\mathcal{P}$. Note that all achievable weights must lie in
$\mathcal{W}:=\\{-kW,\ldots,kW\\}$.

We store, for each non-root node $t^{\prime}$ with parent $t$ of $P$, the
following function of finite domain:

$\displaystyle d_{t^{\prime},W}(R):=\operatorname{ParSolE}(R;X_{t}\cap
X_{t^{\prime}};V_{t^{\prime}};W)$

For $t^{\prime}$ a leaf, the calculations is clear. Let $t^{\prime}$ be an
inner node with parent $t$ and child $t^{\prime\prime}$ and define $\hat{v}$
to be the unique element with $\hat{v}\in X_{t^{\prime}}\setminus X_{t}$ and
similarly $\hat{w}\in X_{t^{\prime}}\setminus X_{t^{\prime\prime}}$ (or, if we
would have $\hat{v}=\hat{w}$, we take $\hat{w}$ to be some arbitrary vertex
from $X_{t^{\prime}}\setminus\\{v\\}$ instead) and finally
$E:=X_{t^{\prime}}\setminus\\{\hat{v},\hat{w}\\}$. If $\hat{v}\hat{w}\notin
E(H)$, the calculation is easy, hence assume $\hat{v}\hat{w}\in E(H)$. For a
configuration $R$ of $X_{t}\cap X_{t^{\prime}}$, we get the following
alternate characterization of $d_{t^{\prime},W}(R)$:

$\displaystyle d_{t^{\prime},W}(R)=$
$\displaystyle\operatorname{ValConf}(R;\\{\hat{w}\\}\cup E)\land\exists
v^{\prime}\in f^{-1}(\hat{v}):v^{\prime}R(\hat{w})\in E(G)\ \land{}$
$\displaystyle\operatorname{ParSolE}((R\cup\\{\hat{v}\mapsto
v^{\prime}\\})|_{X_{t^{\prime}}\setminus\\{\hat{w}\\}};\\{\hat{v}\\}\cup
E;V_{t^{\prime\prime}};W-w(v^{\prime}))$

We now set up our rectangular matrix product. For a vertex $x\in V(H),x\notin
E$, we call a matrix $A$ indexed by $x,E$ and $\mathcal{W}$ if it has
dimensions $n\times n^{|E|}|\mathcal{W}|$. We use two arbitrary bijections
$g_{\\{x\\}}:\mathcal{Conf}(\\{x\\})\to[n]$ and
$g_{E,\mathcal{W}}:\mathcal{Conf}(E)\times\mathcal{W})\to[n^{|E|}|\mathcal{W}|]$
to help index the matrix and define, for a configuration $R$ of $\\{x\\}\cup
E$, $A[R,W]:=A[g_{x}(R|_{x}),g_{E,\mathcal{W}}(R|_{E},W)]$.

We define the $n\times n^{\operatorname{pw}(H)-1}|\mathcal{W}|$ matrix
$B_{t^{\prime}}$, which is to be indexed by $\hat{v},E$ and $\mathcal{W}$, as
follows:

$\displaystyle
B_{t^{\prime}}[R^{\prime},W^{\prime}]:=d_{t^{\prime},W^{\prime}-w(R^{\prime}|_{\hat{v}})}(R^{\prime})$

As in the proof of Theorem 5.14, we also use the adjacency matrix
$Adj_{\hat{v},\hat{w}}$ indexed by configurations of
$(\hat{w},\\{\hat{v}\\})$. Ensuring that the indexing bijections
$g_{\\{\hat{v}\\}}$ are the same for both $B_{t^{\prime}}$ and
$Adj_{\hat{v},\hat{w}}$, we calculate $Adj_{\hat{v},\hat{w}}\cdot
B_{t^{\prime}}$ and obtain a matrix indexed by $\hat{w},E$ and $\mathcal{W}$.
Its entries can be expressed as

$\displaystyle(Adj_{\hat{v},\hat{w}}\cdot
B_{t^{\prime}})[R^{\prime},W^{\prime}]=$ $\displaystyle\exists v^{\prime}\in
f^{-1}(\hat{v}):v^{\prime}R^{\prime}(w)\in E(G)\land{}$
$\displaystyle\operatorname{ParSolE}((R^{\prime}\cup\\{\hat{v}\mapsto
v^{\prime}\\})|_{X_{t^{\prime}}\setminus\\{\hat{w}\\}};\\{\hat{v}\\}\cup
E;V_{t^{\prime\prime}};W^{\prime}-w(v^{\prime}))$

Thus, $d_{t^{\prime}}(R)$ can be expressed as

$\displaystyle d_{t^{\prime},W}(R)=\operatorname{ValConf}(R;\\{\hat{w}\\}\cup
E)\land(Adj_{\hat{v},\hat{w}}\cdot B_{t^{\prime}})[R,W]$

This concludes the description of the computation of $d_{t^{\prime},W}$. For
the computation of the answer, consider the child $r^{\prime}$ of the root
$r$. By definition of $d_{r^{\prime},W}(R)$, we have that there exists a
configuration $R$ such that $d_{t^{\prime},-w(R|_{X_{r}}}(R)=\mathrm{true}$ if
and only if the instance has a solution.

By a simple argument, this dynamic programming algorithm has a running time of
$O(MM(n,n,n^{\operatorname{pw}(H)-1}W)\operatorname{poly}(k))$.

##  6 Interconnections Between Subgraph Isomorphism, Boolean $k$-Wise Matrix
Products and Hyperclique

We have seen in the proof of the conditional lower bound for the unweighted
Colored Subgraph Isomorphism problem that for any $t\in\mathbb{N}$ there is a
polynomial-time reduction from $h$-uniform $h(t+1)$-Hyperclique with $n$ nodes
to Colored Subgraph Isomorphism on pattern graphs of treewidth $t$ with
$n^{h}$ nodes. Hence we have the following corollary, which follows directly
from the Unweighted Lemma.

######  Corollary 6.1.

If there is a $t\geq 3$ such that the Colored Subgraph Isomorphism problem for
pattern graphs of treewidth $t$ can be solved in time $O(n^{t+1-\varepsilon})$
(for some $\varepsilon>0$), then for any $3\leq h\leq t$ the $h$-uniform
$h(t+1)$-Hyperclique problem can be solved in time
$O(n^{h(t+1)-\varepsilon^{\prime}})$ (for some $\varepsilon^{\prime}>0$).

But what about the other direction? Can we also provide a conditional lower
bound for Hyperclique under the hypothesis that Colored Subgraph Isomorphism
cannot be solved faster, hence proving an equivalence? Indeed we can! However,
the “equivalence” we get is not as strong as one might hope.

Specifically, it turns out that the algorithm we described for Colored
Subgraph Isomorphism already gives a Turing reduction from Colored Subgraph
Isomorphism with treewidth $t$ to the Boolean $t$-wise Matrix Product
problem999Defined as: Given $t$ tensors $A^{1},\ldots,A^{t}$ of order $t$ with
dimensions $n\times\ldots\times n$, calculate their boolean $t$-wise matrix
product $\operatorname{MP}_{t}(A^{1},\ldots,A^{t})$.. Indeed, it can also be
seen that the Boolean $t$-wise Matrix Product problem is equivalent to the
$t$-uniform $(t+1)$-Hyperclique problem. More formally, we have the following
two lemmas.

######  Lemma 6.2.

For any $t\geq 3$, if the Boolean $t$-wise Matrix Product problem can be
solved in time $O(n^{t+1-\varepsilon})$, then Colored Subgraph Isomorphism
problem on pattern graphs of treewidth $t$ can be solved in time
$O(n^{t+1-\varepsilon})$.

######  Proof 6.3.

As was already mentioned in the algorithms for Colored Subgraph Isomorphism
(see the proof of Theorem 5.4), the boolean $\operatorname{tw}(H)$-wise matrix
product is the bottleneck for the running time. All other operations run in
time $O(n^{\operatorname{tw}(H)}\operatorname{poly}(|V(H)|))$. Hence a
$O(n^{t+1-\varepsilon})$ algorithm for Boolean $t$-wise Matrix Product
translates directly to a $O(n^{t+1-\varepsilon})$ algorithm for Colored
Subgraph Isomorphism with $\operatorname{tw}(H)=t$.

######  Lemma 6.4.

If the $t$-uniform $(t+1)$-Hyperclique problem can be solved in time
$O(n^{t+1-\varepsilon})$ (for some $\varepsilon>0$), then the Boolean $t$-wise
Matrix Product problem can be solved in time $O(n^{t+1-\varepsilon^{\prime}})$
(for some $\varepsilon^{\prime}>0$).

We defer the proof of Lemma 6.4 to Appendix B.2. Indeed, in appendix B, we
also show the other direction, i.e. we show that the existence of fast
algorithms for these two problems is actually equivalent. This is a natural
generalization of methods from [68], where this result is proven for
combinatorial algorithms for the case $t=2$.

Composing these two lemmas, we get the following theorem.

######  Theorem 6.5.

If the $t$-uniform $(t+1)$-Hyperclique problem can be solved in time
$O(n^{t+1-\varepsilon})$ (for some $\varepsilon>0$), then the Colored Subgraph
Isomorphism problem on pattern graphs of treewidth $t$ can be solved in time
$O(n^{t+1-\varepsilon^{\prime}})$ (for some $\varepsilon^{\prime}>0$).

Looking at Corollary 6.1 and Theorem 6.5, we have reductions in both
directions, but they do not give a full equivalence. This is because the
reduction from Corollary 6.1 only gives an algorithm for $h$-uniform
$h(t+1)$-Hyperclique (for any $h\geq 3$), but Theorem 6.5 needs an algorithm
for the much “denser” $t$-uniform $(t+1)$-Hyperclique problem.

##  7 The Colored Problems are Equivalent to the Uncolored Problems

We now show Lemma 3.1 from the preliminaries (restated in a modified form
below), which shows that the (Exact Weight) Subgraph Isomorphism and (Exact
Weight) Colored Subgraph Isomorphism problems are essentially equivalent with
respect to running times. Hence, for most of our purposes, we can treat them
as equal, which simplifies both the proofs of the algorithms and the lower
bounds since the colored version is much more structured.

The reductions from (Exact Weight) Subgraph Isomorphism to (Exact Weight)
Colored Subgraph Isomorphism and the reduction from Exact Weight Colored
Subgraph Isomorphism to Exact Weight Subgraph Isomorphism leaves $H$
unmodified. The reduction from Colored Subgraph Isomorphism to Subgraph
Isomorphism, however, modifies $H$ in such a way that preserves treewidth, but
may modify pathwidth.

We say that Subgraph Isomorphism or Colored Subgraph Isomorphism have a
$T(n,k,\rho(H))$ algorithm (for some graph parameter $\rho$) if there is an
algorithm $\mathcal{A}$ which decides a given instance $\phi=(H,G,f)$ of
either problem in time $T(n,k,\rho(H))$. Analogously, we define the phrase
that Exact Weight Subgraph Isomorphism or Exact Weight Colored Subgraph
Isomorphism has a $T(n,k,\rho(H),W)$ algorithm, the only difference being that
$\phi=(H,G,f,w)$. $W$ denotes the maximum absolute value of the weight
function $w$.

Parts 1 and 2 of the lemma follows directly from the Color Coding technique
[12].

######  Lemma 7.1 (reformulation of Lemma 3.1).

Let $\rho$ be any graph parameter.

  1. 1.

If there is a $T(n,k,\rho(H))$ time deterministic algorithm for Colored
Subgraph Isomorphism, then there is a $O(T(kn,k,\rho(H))g(k))$ expected time
algorithm and furthermore a $\widetilde{O}(T(kn,k,\rho(H))g(k))$ time
deterministic algorithm for Subgraph Isomorphism, for some computable function
$g$.

  2. 2.

If there is a $T(n,k,\rho(H),W)$ time deterministic algorithm for Exact Weight
Colored Subgraph Isomorphism, then there is a $O(T(kn,k,\rho(H),W)g(k))$
expected time algorithm and furthermore a
$\widetilde{O}(T(kn,k,\rho(H),W)g(k))$ time deterministic algorithm for Exact
Weight Subgraph Isomorphism, for some computable function $g$.

  3. 3.

Let $\operatorname{tw}(H)\geq 2$. If there is a $T(n,k,\operatorname{tw}(H))$
time algorithm for Subgraph Isomorphism, then there is a
$O(T(\operatorname{poly}(k)n,\operatorname{poly}(k),\operatorname{tw}(H))+\operatorname{poly}(k)n^{2})$
time algorithm for Colored Subgraph Isomorphism.

  4. 4.

If there is a $T(n,k,\rho(H),W)$ time algorithm for Exact Weight Subgraph
Isomorphism, then there is a
$O(T(2n,2k,\rho(H),2^{k}W)+\operatorname{poly}(k)n^{2})$ time algorithm for
Exact Weight Colored Subgraph Isomorphism.

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

We start by showing part 1 and part 2. As mentioned, this follows directly
from a standard application of the Color Coding technique [12]. Briefly
speaking, they use random colorings of the vertices of $G$ to make the
potential solution subgraph multicolored with some probability depending only
on $k$. In our case, we may then try all $k!$ mappings from colors to vertices
of $H$ to obtain the randomized algorithm; we delete any monochromatic edges
to make sure that $f$ is a homomorphism. The authors of [12] also explain how
to derandomize the algorithm using $k$-perfect hash functions, which results
in the deterministic algorithm with an additional factor of $2^{O(k)}\log(n)$.

The factor of $k$ in front of $n$ in $T(kn,k,\operatorname{tw}(H))$ comes from
the fact that in the Colored Subgraph Isomorphism problem, we consider $n$ to
be the size of the preimages of $f$, while in the Subgraph Isomorphism
problem, we consider it to be the size of $V(G)$.

Now we show part 3. Given an instance $\phi$ of Colored Subgraph Isomorphism,
where $H$ has $k$ vertices, with preimages in $G$ of $n$ vertices each, we
construct an equivalent Subgraph Isomorphism instance $\phi^{\prime}$. This is
done in two steps. First, we modify $\phi$ into an equivalent, but more
structured Colored Subgraph Isomorphism instance $\widetilde{\phi}$, which we
then reduce to $\phi^{\prime}$. See Figure 4 for an example of this reduction.

Subdividing all edges:

In the first step, we construct $\widetilde{H}$, which consists of a
subdivided copy of $H$, where each vertex has a unique “signature” structure
attached to it. These signatures have a triangle as a key component. Abusing
notation, we write $V(H)=\\{1,\ldots,k\\}$ and use the vertices as numbers.
First, for each $i\in V(H)$, we add a vertex $\widetilde{i}$ to
$\widetilde{H}$. Then, for each edge $ij\in E(H)$ with $i<j$, we add a vertex
$\widetilde{x}_{ij}$ and create two edges $\widetilde{i}\widetilde{x_{ij}}$
and $\widetilde{x}_{ij}\widetilde{j}$, hence subdividing the edge $ij$. This
ensures that for now, the new graph has no triangles. In $\widetilde{G}$, we
populate the preimages as follows: For each $i\in V(H)$, let
$f^{-1}(i)=\\{a_{i}^{1},\ldots,a_{i}^{n}\\}$ and add $n$ vertices
$\\{\widetilde{a}_{i}^{1},\ldots,\widetilde{a}_{i}^{n}\\}$ to
$f^{-1}(\widetilde{i})$. For each $\ell$, the vertex
$\widetilde{a}_{i}^{\ell}$ corresponds to $a_{i}^{\ell}$. The preimages of
$\widetilde{x}_{ij}$ are populated with $n$ vertices
$\\{b_{ij}^{1},\ldots,b_{ij}^{n}\\}$ via $\widetilde{f}$. For each edge $ij\in
E(H)$ with $i<j$, we add an edge $a_{i}^{\ell}b_{ij}^{\ell}$ for every
$\ell\in[n]$. We also go through each edge $a_{i}^{\ell}a_{j}^{m}\in E(G)$ and
add a corresponding edge $b_{ij}^{\ell}\widetilde{a}_{j}^{m}$ to
$E(\widetilde{G})$.

Signatures:

We now add the signatures. For each $i\in[k]$, we add a new vertex
$\widetilde{t}_{i}$ and a new triangle
$\widetilde{u}_{i}\widetilde{v}_{i}\widetilde{w}_{i}$ to $\widetilde{H}$, and
connect $\widetilde{t}_{i}$ to both $\widetilde{u}_{i}$ and $\widetilde{i}$
from $V(\widetilde{H})$. Furthermore, we connect $\widetilde{v}_{i}$ to $i+1$
other newly created vertices
$\widetilde{y}_{i}^{1},\ldots\widetilde{y}_{i}^{i+1}$. Let the set of all
newly created vertices
$\widetilde{t}_{i},\widetilde{u}_{i},\widetilde{v}_{i},\widetilde{w}_{i},\widetilde{y}_{i}^{\ell}$
($i\in[n],\ell\in[i+1]$) be named $X$. In $\widetilde{G}$, we populate the
preimages of these new vertices by adding $n$ vertices
$\\{z_{1},\ldots,z_{n}\\}$ to $V(\widetilde{G})$ for each vertex $v\in X$,
with $\forall i\in[n]:\widetilde{f}(z_{i})=v$. Now, for each $u\in X$, we pick
an arbitrary node from $f^{-1}(u)$ and call it active. Furthermore, for all
$\widetilde{i}\in V(\widetilde{H})$, we call all vertices of $f^{-1}(i)$
active. Now for each $v\in X$, we connect its active vertex in $f^{-1}(v)$ to
all active vertices from the neighbourhood $f^{-1}(N(v))$. Note that of the
vertices in $f^{-1}(X)$, only the active ones have edges at all. Indeed, for
each $i\in[k]$, $\widetilde{G}$ contains exactly one triangle such that one of
its vertices has degree $i+3$.

$A$$B$

$\vdots$

$\ddots$ Corresponds to a choice of one vertex from each of the $h$ partitions
Corresponds to a hyperedge Corresponds to $h$ vertex partitions of the
hyperclique instance Corresponds to the set of hyperedges between its $h$
defining vertex partitions The edge exists if and only if the endpoints are
compatible, i.e. if for each hyperedge partition that involves both endpoints,
the vertex choice on one end agrees with the vertex of the hyperedge on the
other pattern graph $H$host graph $G$$S_{2}$$S_{1}$$P$$\vdots$$\vdots$

$\ddots$

$\ddots$$\ddots$

$\ddots$

intermediate-result tw-wise merge intermediate-result tw $\vdots$ $\vdots$
$\cdots$ $\cdots$
$H$$G$$\widetilde{H}$$\widetilde{G}$$f^{-1}(1)$$f^{-1}(2)$$1$$2$$3$$\widetilde{1}$$\widetilde{x_{12}}$$\widetilde{2}$$\widetilde{3}$$\widetilde{t_{2}}$$\widetilde{u_{2}}$$\widetilde{w_{2}}$$\widetilde{v_{2}}$$\widetilde{y_{2}^{1}}$$\widetilde{y_{2}^{2}}$$\widetilde{y_{2}^{3}}$$\widetilde{f}^{-1}(\widetilde{1})$$\widetilde{f}^{-1}(\widetilde{x_{12}})$$\widetilde{f}^{-1}(\widetilde{2})$$\widetilde{f}^{-1}(\widetilde{t_{2}})$$\widetilde{f}^{-1}(\widetilde{u_{2}})$$\widetilde{f}^{-1}(\widetilde{w_{2}})$$\widetilde{f}^{-1}(\widetilde{y_{2}^{1}})$$\widetilde{f}^{-1}(\widetilde{y_{2}^{3}})$$\widetilde{f}^{-1}(\widetilde{y_{2}^{2}})$$\widetilde{f}^{-1}(\widetilde{v_{2}})$

Figure 4: An example of the construction of the instance $\widetilde{\phi}$
from $\phi=(H,G,f)$ where $H$ is a triangle

We set $\widetilde{\phi}$ to be the instance
$(\widetilde{H},\widetilde{G},\widetilde{f})$. This concludes the construction
of $\widetilde{\phi}$.

Clearly, the new instance $\widetilde{\phi}$ has a solution if and only if
$\phi$ has one, and the size of the new instance is only a
$\operatorname{poly}(k)$ factor larger than the size of $\phi$. We must also
show that the reduction preserves treewidth. Note that $\widetilde{H}$ is
obtained from $H$ via two operations: Subdividing edges and connecting a graph
of smaller or equal treewidth via a single edge. It is easy to see that both
operations do not change the treewidth.

Now, to construct $\phi^{\prime}$, we simply get rid of the mapping
$\widetilde{f}$. In other words,
$\phi^{\prime}=(\widetilde{H},\widetilde{G})$. Obviously, if
$\widetilde{\phi}$ has a solution, then $\phi^{\prime}$ has one. For the other
direction, suppose $\phi^{\prime}$ has a solution, i.e. a subgraph
$S^{\prime}$ of $\widetilde{G}$ along with an isomorphism
$h:V(\widetilde{H})\to V(G[S^{\prime}])$ of $\widetilde{G}$. Since both
$\widetilde{H}$ and $\widetilde{G}$ have, for each $i$, exactly one triangle
with a vertex of degree $i$, $h$ must map these triangles to their respective
counterparts in $\widetilde{G}$. In particular, each of the vertices in $X$ is
mapped to the active vertex in its preimage. Since the active node in
$f^{-1}(\widetilde{t}_{i})$ is connected only to nodes of
$f^{-1}(\widetilde{i})$ (apart from the active node of
$f^{-1}(\widetilde{u}_{i})$, which is already in the image of
$h(\widetilde{u}_{i})$), we know that $h(\widetilde{i})\in
f^{-1}(\widetilde{i})$. Analogously, $h(\widetilde{x}_{ij})\in
f^{-1}(x_{ij})$. Hence, $S^{\prime}$ takes exactly one vertex from each
preimage of vertices from $\widetilde{H}$. Thus, $\widetilde{\phi}$ also has a
solution.

We thus obtain a way to reduce $\phi$ to $\phi^{\prime}$ with a size factor of
only $\operatorname{poly}(k)$. The reduction obviously runs in
$O(\operatorname{poly}(k)n^{2})$ time. This shows part 3.

Finally, we show part 4. We begin with the node-weighted version. Given an
instance $\phi$ of Exact Weight Colored Subgraph Isomorphism where the pattern
graph $H$ has $k$ vertices, we create an instance $\phi^{\prime}$ of Exact
Weight Subgraph Isomorphism by simply dropping $f$ and modifying the weights.
We have to ensure that a solution of $\phi^{\prime}$ takes exactly one node
from each preimage of $H$. To do this, we encode a checklist in the weights of
the nodes. Again, let $V(H)=\\{1,\ldots,k\\}$. Let $u\in f^{-1}(i)$ for $i\in
V(H)$, and consider its weight $w(u)$. We modify it by multiplying it with
$2^{k}$ and adding $2^{i}$. We call the added weight its “signature”. Now,
since any solution must pick exactly $k$ vertices, the only way that the
signatures of the solution vertices sum up to $2^{k}-1$ is to pick vertices
which have a sum of weight 0 according to the original weight function and
furthermore have exactly one vertex with added weight $2^{i}$ for each
$i=1,\ldots,k$. To complete our reduction, we pick an arbitrary vertex $v\in
V(G)$ and subtract $2^{k}-1$ from all vertices in $f^{-1}(v)$, making the new
target zero. This reduction does not alter $G$ or $H$, and instead only
modifies the weight function, resulting in the stated time bounds.

For the edge-weighted version, we can use essentially the same construction as
for the node-weighted version. Again, all weights are multiplied by $2^{k}$,
and each vertex of $H$ has a unique “signature”. However, this time, we have
to add the signatures to the edge weights. Consequently, for each $i\in
V(H)=\\{1,\ldots,k\\}$, we pick an arbitrary incident edge $e\in E(H)$. Let
$e=\\{i,j\\}$. We add the signature $2^{i}$ to every edge in the preimage of
$e$. That is, to every edge $\\{e^{\prime}\in E(G)\ |\
e^{\prime}=\\{u,v\\}\text{ and }f(u)=i\text{ and }f(v)=j\\}$. This way, we
must still pick a node from each preimage to ensure that the signatures sum to
$T:=2^{k}-1$. Again, we pick an arbitrary edge $e\in E(H)$ and subtract $T$
from all edges in its preimage. This almost completes the proof. However, we
still have to handle nodes of degree 0 in $H$, since we cannot pick an
incident edge for them. However, an isolated vertex $i$ in $H$ may be mapped
to any vertex in $G$. Hence, we may simply skip the signature of $i$. We also
have to modify the target $T$ to be $T-2^{i}$.

##  8 Open Problems

In this paper we discussed many different variants of the Subgraph Isomorphism
problem. For some of these variants we leave gaps, which gives rise to several
open problems:

  1. 1.

Can the algorithms for weighted trees be improved? We have shown that some
improvements can be made for node-weighted trees (see Theorem 1.9), but are
these optimal? What about edge-weighted trees?

  2. 2.

Are there fast algorithms for unweighted Subgraph Isomorphism on graphs of
bounded pathwidth that do not use rectangular matrix multiplication? Can the
gap between exponent $\omega(p-1)$ and exponent $p$ be closed? Similar
questions apply to the weighted case; see Theorems 1.6 and 1.8.

  3. 3.

Relatedly, are there good lower bounds for unweighted Subgraph Isomorphism on
graphs of bounded pathwidth? These could be attained via a modification of the
proof of part 2 of Lemma 3.1 for pathwidth (though we see no way to do this),
or with completely new techniques.

We conclude with some more general open problems:

  1. 1.

Do our algorithms and lower bounds also work for other types of graph
homomorphisms, and for counting the number of solutions? It seems like
techniques from [32] should apply.

  2. 2.

In this work we demonstrated the existence of maximally hard patterns for
which Subgraph Isomorphism requires time $n^{\operatorname{tw}(H)+1-o(1)}$.
Can we classify which (classes of) patterns are maximally hard?

  3. 3.

Changing our focus from hard patterns to easy patterns, we can ask: do classes
of patterns of unbounded treewidth exist for which Subgraph Isomorphism can be
solved in time $n^{o(\operatorname{tw}(H))}$? Recall that a conditional lower
bound rules out $n^{o(\operatorname{tw}(H)/\log\operatorname{tw}(H))}$ [54].

## References

  * [1] Amir Abboud and Greg Bodwin.  The 4/3 additive spanner exponent is tight.  Journal of the ACM (JACM), 64(4):1–20, 2017.
  * [2] Amir Abboud, Greg Bodwin, and Seth Pettie.  A hierarchy of lower bounds for sublinear additive spanners.  SIAM Journal on Computing, 47(6):2203–2236, 2018.
  * [3] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof.  More consequences of falsifying SETH and the Orthogonal Vectors conjecture.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 253–266, 2018.
  * [4] Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay.  SETH-based lower bounds for Subset Sum and Bicriteria Path.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41–57. SIAM, 2019.
  * [5] Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay.  Scheduling lower bounds via AND Subset Sum.  arXiv preprint arXiv:2003.07113, 2020.
  * [6] Amir Abboud and Kevin Lewi.  Exact weight subgraphs and the k-SUM conjecture.  In International Colloquium on Automata, Languages, and Programming, pages 1–12. Springer, 2013.
  * [7] Amir Abboud, Kevin Lewi, and Ryan Williams.  Losing weight by gaining edges.  In European Symposium on Algorithms, pages 1–12. Springer, 2014\.
  * [8] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 434–443. IEEE, 2014.
  * [9] Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann.  Consequences of faster alignment of sequences.  In International Colloquium on Automata, Languages, and Programming, pages 39–51. Springer, 2014.
  * [10] Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu.  Matching triangles and basing hardness on an extremely popular conjecture.  SIAM Journal on Computing, 47(3):1098–1122, 2018.
  * [11] Noga Alon.  Testing subgraphs in large graphs.  Random Structures & Algorithms, 21(3-4):359–370, 2002.
  * [12] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  Journal of the ACM (JACM), 42(4):844–856, 1995.
  * [13] Omid Amini, Fedor V Fomin, and Saket Saurabh.  Counting subgraphs via homomorphisms.  In International Colloquium on Automata, Languages, and Programming, pages 71–82. Springer, 2009.
  * [14] Zhao An, Qilong Feng, Iyad Kanj, and Ge Xia.  The complexity of tree partitioning.  In Workshop on Algorithms and Data Structures, pages 37–48. Springer, 2017.
  * [15] MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein.  Fast algorithms for knapsack via convolution and prediction.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1269–1282, 2018.
  * [16] Felix A Behrend.  On sets of integers which contain no three terms in arithmetical progression.  Proceedings of the National Academy of Sciences of the United States of America, 32(12):331, 1946.
  * [17] Markus Bläser.  Fast matrix multiplication.  Theory of Computing, pages 1–60, 2013.
  * [18] Hans L Bodlaender.  A tourist guide through treewidth.  Acta cybernetica, 11(1-2):1, 1994.
  * [19] Hans L Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM Journal on computing, 25(6):1305–1317, 1996.
  * [20] Hans L Bodlaender.  A partial k-arboretum of graphs with bounded treewidth.  Theoretical computer science, 209(1-2):1–45, 1998.
  * [21] Hans L Bodlaender.  Discovering treewidth.  In International Conference on Current Trends in Theory and Practice of Computer Science, pages 1–16. Springer, 2005.
  * [22] David Bremner, Timothy M Chan, Erik D Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian.  Necklaces, convolutions, and x+ y.  In European Symposium on Algorithms, pages 160–171. Springer, 2006\.
  * [23] Karl Bringmann.  Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661–670. IEEE, 2014.
  * [24] Karl Bringmann.  A near-linear pseudopolynomial time algorithm for Subset Sum.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073–1084. SIAM, 2017.
  * [25] Karl Bringmann and Marvin Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 79–97. IEEE, 2015.
  * [26] Danilo Bruschi, Lorenzo Martignoni, and Mattia Monga.  Detecting self-mutating malware using control-flow graph matching.  In International conference on detection of intrusions and malware, and vulnerability assessment, pages 129–143. Springer, 2006.
  * [27] Timothy M Chan and Moshe Lewenstein.  Clustered integer 3SUM via additive combinatorics.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 31–40, 2015.
  * [28] James W Cooley and John W Tukey.  An algorithm for the machine calculation of complex Fourier series.  Mathematics of computation, 19(90):297–301, 1965.
  * [29] Don Coppersmith.  Rapid multiplication of rectangular matrices.  SIAM Journal on Computing, 11(3):467–471, 1982.
  * [30] Don Coppersmith and Shmuel Winograd.  Matrix multiplication via arithmetic progressions.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 1–6, 1987.
  * [31] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT Press, 2009.
  * [32] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 210–223, 2017.
  * [33] Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström.  On problems as hard as CNF-SAT.  ACM Transactions on Algorithms (TALG), 12(3):1–24, 2016.
  * [34] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 4.  Springer, 2015.
  * [35] Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams.  Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1167–1178, 2019.
  * [36] Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya.  All non-trivial variants of 3-LDT are equivalent.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 974–981, 2020.
  * [37] Friedrich Eisenbrand and Fabrizio Grandoni.  On the complexity of fixed parameter clique and dominating set.  Theoretical Computer Science, 326(1-3):57–67, 2004.
  * [38] John A Ellis, Ivan Hal Sudborough, and Jonathan S Turner.  The vertex separation and search number of a graph.  Information and Computation, 113(1):50–79, 1994.
  * [39] Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh.  Almost optimal lower bounds for problems parameterized by clique-width.  SIAM Journal on Computing, 43(5):1541–1563, 2014.
  * [40] Fedor V Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and BV Raghavendra Rao.  Faster algorithms for finding and counting subgraphs.  Journal of Computer and System Sciences, 78(3):698–706, 2012.
  * [41] François Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029–1046. SIAM, 2018.
  * [42] Edinah K Gnang, Ahmed Elgammal, and Vladimir Retakh.  A spectral theory for tensors.  In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 20, pages 801–841, 2011.
  * [43] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-SAT.  Journal of Computer and System Sciences, 62(2):367–375, 2001.
  * [44] Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter.  Bin packing with fixed number of bins revisited.  Journal of Computer and System Sciences, 79(1):39–49, 2013.
  * [45] Ce Jin and Hongxun Wu.  A simple near-linear pseudopolynomial time randomized algorithm for subset sum.  In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [46] Konstantinos Koiliaris and Chao Xu.  A faster pseudopolynomial time algorithm for Subset Sum.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1062–1072. SIAM, 2017.
  * [47] Konstantinos Koiliaris and Chao Xu.  Subset Sum made simple.  arXiv preprint arXiv:1807.08248, 2018.
  * [48] Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider.  On the fine-grained complexity of one-dimensional dynamic programming.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [49] François Le Gall.  Powers of tensors and fast matrix multiplication.  In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296–303, 2014.
  * [50] Yuan Li, Alexander Razborov, and Benjamin Rossman.  On the AC0 complexity of Subgraph Isomorphism.  SIAM Journal on Computing, 46(3):936–971, 2017.
  * [51] Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams.  Tight hardness for shortest cycles and paths in sparse graphs.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1236–1252. SIAM, 2018.
  * [52] Grazia Lotti and Francesco Romani.  On the asymptotic complexity of rectangular matrix multiplication.  Theoretical Computer Science, 23(2):171–185, 1983.
  * [53] Josef Malík, Ondřej Suchỳ, and Tomáš Valla.  Efficient implementation of Color Coding algorithm for Subgraph Isomorphism problem.  In International Symposium on Experimental Algorithms, pages 283–299. Springer, 2019.
  * [54] Dániel Marx.  Can you beat treewidth?  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 169–179. IEEE, 2007.
  * [55] Dániel Marx and Michal Pilipczuk.  Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).  In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 542–553, Dagstuhl, Germany, 2014. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2014/4486, doi:10.4230/LIPIcs.STACS.2014.542.
  * [56] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon.  Network motifs: simple building blocks of complex networks.  Science, 298(5594):824–827, 2002.
  * [57] Jaroslav Nešetřil and Svatopluk Poljak.  On the complexity of the subgraph problem.  Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.
  * [58] Kevin Pratt.  Waring rank, parameterized and exact algorithms.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 806–823. IEEE, 2019.
  * [59] Andrzej Proskurowski and Jan Arne Telle.  Classes of graphs with restricted interval models.  Discrete Mathematics and Theoretical Computer Science, 3(4), 1999\.
  * [60] Bellman Richard.  Dynamic programming.  Princeton University Press, 89:92, 1957.
  * [61] Liam Roditty and Virginia Vassilevska Williams.  Fast approximation algorithms for the diameter and radius of sparse graphs.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 515–524, 2013.
  * [62] Gregory Rosenthal.  Beating treewidth for average-case subgraph isomorphism.  In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019\.
  * [63] Paul D Seymour and Robin Thomas.  Graph searching and a min-max theorem for tree-width.  Journal of Combinatorial Theory, Series B, 58(1):22–33, 1993.
  * [64] Andrew James Stothers.  On the complexity of matrix multiplication.  2010\.
  * [65] Volker Strassen.  Gaussian elimination is not optimal.  Numerische mathematik, 13(4):354–356, 1969.
  * [66] Edward H Sussenguth.  A graph-theoretic algorithm for matching chemical structures.  Journal of Chemical Documentation, 5(1):36–43, 1965.
  * [67] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.
  * [68] Virginia Vassilevska Williams and Ryan Williams.  Subcubic equivalences between path, matrix and triangle problems.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 645–654. IEEE, 2010.

##  Appendix A Proof of the Conditional Lower Bound for Subset Sum

In Section 4.3.1, we stated Theorem 4.23, which gives the following lower
bound on Subset Sum:

_For no $\varepsilon>0$ can there be an algorithm which solves Subset Sum in
time
$O(T^{1-\varepsilon}\operatorname{poly}(n))$ unless the $h$-uniform
Hyperclique hypothesis fails for all $h\geq 3$._

We now prove this.

###  A.1 Reduction from $k$-Sum to Subset Sum

Before proving the result, we need a lemma that shows that we can reduce
$k$-sum to Subset Sum with minimal overhead. This theorem is already known,
but we could not find a formal proof of it in the literature. Therefore we
provide one here.

######  Lemma A.1 (Reducing $k$-Sum to Subset Sum).

There is an algorithm $\mathcal{B}$ which, given as input a $k$-sum instance
with $N$ values from $[0,D]$ per set, as well as a target $T$, constructs an
equivalent Subset Sum instance with $k\cdot N$ values in $[0,Dg(k)]$ and a
target $T^{\prime}$ bounded by $Tg(k)$ for a computable function $g$.
Furthermore, for constant $k$, $\mathcal{B}$ runs in time linear in the input
size.

######  Proof A.2.

The values of the Subset Sum instance are the union of the $k$ sets. However,
we modify the weights and target as follows. At the front of the binary
representation of the weights and the target, we add a buffer of
$\lceil\log(k)\rceil$ zero bits to avoid overflow, then another $k$ bits
constituting a “checklist”, then in front of that another buffer of
$\lceil\log(k)\rceil$ zero bits and finally another $\lceil\log(k)\rceil$ bits
which contains a counter for the number of nodes of the solution.

The target $T$ has the binary representation of $k$ in the counter bits and
only ones in the checklist bits. Each weight has the binary representation of
$1$ in the counter bits, ensuring that we take exactly $k$ weights.
Furthermore, if the weight comes from the $i$-th set of the $k$-sum instances,
its checklist bits is zero except for the $i$-th position.

Now if one picks more than $2^{\lceil\log(k)\rceil}$ values, the counter at
the front overflows the length of the target, so that selection cannot be a
solution. Since $2^{\lceil\log(k)\rceil}<2k$ and since there is a buffer of
$\lceil\log(k)\rceil$ bits, the checklist cannot overflow into the counter.
Hence any solution must pick exactly $k$ weights. Hence, the only way to
achieve all ones in the checklist bits of a sum of $k$ weights is to pick
exactly one weight from each of the $k$ sets. This completes the reduction.

Since we add $3\lceil\log(k)\rceil+k$ bits to the weights and the target,
their value is multiplied by at most $2^{k}\cdot 2^{3}\cdot k^{3}$. Choosing
$g(k)=2^{k+3}k^{3}$, we obtain the bounds from the lemma.

###  A.2 Modifying the Weighted Lemma to Prove the Lower Bound

To prove the theorem above, we modify the Weighted Lemma by adding a special
case of parameters: All parameters are as before, but $\beta=1$ and $r_{2}=0$.
In this case, the preimages in the resulting instance $\mathcal{I}^{\prime}$
instead have size $n^{k/r_{1}}$, and the maximum weight is
$W=\Theta(n^{(1+\varepsilon)k})$.

To prove this special case of the Weighted Lemma, we can almost use the
reduction from its proof. We must simply purge all parts of the construction
that relate to the edges part. That is, no construction of $V_{2}$ in step 2,
no construction of $S^{\prime}_{2}$ in steps 3 and no construction of $S_{2}$
in step 5. The reduction then yields an instance $\mathcal{I}^{\prime}$ as
described above.

We now prove the theorem about Subset Sum. Essentially, the instances we get
from the special case of the Weighted Lemma are $k$-sum instances that we can
then reduce to Subset Sum via the lemma in Appendix A.1 above.

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

Let $h$ be given. Suppose there is an algorithm solving Subset Sum in time
$O(T^{1-\varepsilon}N^{z})$ for some $z\in\mathbb{N}$. We use the special case
of the Weighted Lemma with

  * •

some $\varepsilon^{\prime}$ chosen later,

  * •

$h^{\prime}:=h$, and

  * •

some arbitrary $r_{1}\in\mathbb{N}$ such that

    * –

$r_{1}>\frac{\hat{c}}{h}$ (this ensures, again, that the running time
$O(n^{2h-1}+n^{\hat{c}k/(hr_{1})})$ of the reduction is equal to
$O(n^{2h-1}+n^{k-\varepsilon})$ for some $\varepsilon>0$, and can hence be
ignored in the analysis), and

    * –

$r_{1}>z\varepsilon^{\prime}$ (this ensures that
$n^{zk/r_{1}}<n^{\varepsilon^{\prime}k}$).

This yields a $k\in\mathbb{N}$ and a reduction algorithm $\mathcal{A}$ with
the properties from the description of the special case above. In particular,
the reduction algorithm produces an Exact Weight Colored Subgraph Isomorphism
where $H$ consists only of isolated vertices with preimages of size
$O(n^{k/r_{1}})$ and maximum absolute weight $W=\Theta(n^{(1+\varepsilon)k})$.
We make all weights positive by adding a large number to each, such that the
target is $T=\Theta(n^{(1+\varepsilon)k})$. Note that this instance is also a
$(r_{1}+{hr_{1}\choose h})$-sum instance, with each set of numbers being the
set of weights in a preimage.

We now use the algorithm $\mathcal{B}$ from Lemma A.1 to convert this to a
Subset Sum instance with $N=O(n^{k/r_{1}})$ values in
$[0,\Theta(n^{(1+\varepsilon^{\prime})k})]$ and target
$T=\Theta(n^{(1+\varepsilon^{\prime})k})$.

We can now solve the instance in time
$O(n^{(1-\varepsilon)(1+\varepsilon^{\prime})k}n^{zk/r_{1}})=O(n^{((1-\varepsilon)(1+\varepsilon^{\prime})+\varepsilon^{\prime})k})$.
Hence it suffices to choose $\varepsilon^{\prime}$ such that

$\displaystyle(1-\varepsilon)(1+\varepsilon^{\prime})+\varepsilon^{\prime}<1\
\ \iff\ \ \varepsilon^{\prime}<\frac{\varepsilon}{2-\varepsilon}$

Since $\varepsilon\in(0,1)$ and hence
$\frac{\varepsilon}{2-\varepsilon}\in(0,1)$, this is always possible.

##  Appendix B Hyperclique and Boolean $k$-Wise Matrix Product are Equivalent

In this section, we show that $k$-uniform $(k+1)$-Hyperclique has a fast
algorithm if and only if the $k$-Wise Matrix Product problem has a fast
algorithm. More formally:

######  Theorem B.1.

The $k$-uniform $(k+1)$-Hyperclique problem has an algorithm running in time
$O(n^{k+1-\varepsilon})$ (for some $\varepsilon>0$) if and only if the
$k$-wise Matrix Product problem has an algorithm running in time
$O(n^{k+1-\varepsilon^{\prime}})$ (for some $\varepsilon^{\prime}>0$).

In the proofs of both directions, we will reduce from and to the Colored
Hyperclique problem instead of the Hyperclique problem. This is because these
problems are equivalent: In the one direction, we can use the reduction in
step 1 in the proof of the Unweighted Lemma (Section 4.2). In the other
direction, a trivial argument shows that simply throwing away the color
homomorphism is enough.

Reducing from and to the Colored Hyperclique problem simplifies the proofs of
both directions. Both are a straightforward generalization of the known proof
that the standard boolean matrix product and the triangle problem101010Given a
3-colored graph, check if it contains a triangle. Note that this is the
colored $k$-uniform $(k+1)$-Hyperclique problem for $k=2$. are subcubically
equivalent111111Meaning one problem has a $O(n^{3-\varepsilon})$ algorithm if
and only if the other has one. with respect to combinatorial algorithms. This
was proven in [68] for the more general result of subcubic equivalence of the
$(\min,+)$ matrix product121212This is the standard matrix product, but
addition is replaced by $\min$ and multiplication is replaced by addition. and
the Negative Triangle problem131313Given a 3-colored graph with edge weights,
check if it contains a triangle of negative total weight. and is a fundamental
result in Fine-Grained Complexity Theory.

###  B.1 From Hyperclique to Boolean $k$-Wise Matrix Product

######  Lemma B.2.

If the $k$-wise Matrix Product problem has an algorithm running in time
$O(n^{k+1-\varepsilon})$ (for some $\varepsilon>0$), then the $k$-uniform
$(k+1)$-Hyperclique problem has an algorithm running in time
$O(n^{k+1-\varepsilon^{\prime}})$ (for some $\varepsilon^{\prime}>0$).

######  Proof B.3.

First, recall that in the proof of theorem 5.4 we defined how to index tensors
via configurations. We re-use this definition here.

Given a hyperclique instance $(G,f)$ where $G$ is a $k$-uniform hypergraph and
$f:V(G)\to V(C_{k+1})$ is a color homomorphism to the $k$-uniform
$(k+1)$-hyperclique $C_{k+1}$, we solve it via a single application of the
$k$-wise matrix product. To do this, we create $k$ tensors
$A^{1},\ldots,A^{k}$ of order $k$ with dimensions $n\times\ldots\times n$. We
initialize them with zeroes as entries. The tensor $A^{i}$ will be indexed by
configurations of $V(C_{k+1})\setminus\\{i\\}$ with ordering
$(1,\ldots,i-1,k+1,i+1,\ldots,k)$. For each $i$ and each configurations $R$ of
$V(C_{k+1})\setminus\\{i\\}$, we set $A^{i}[R]$ to one if and only if
$R(1)\ldots R(i-1)R(i+1)\ldots R(k+1)\in E(G)$. We use truth values and 0/1
interchangeably to declutter notation.

Now let $A(R):=\operatorname{MP}_{k}(A^{1},\ldots,A^{k})$. Then for a
configuration $R$ of $V(C_{k+1})\setminus\\{k+1\\}$, we have that

$\displaystyle A[R]$
$\displaystyle=\bigvee_{\ell\in[n]}A^{1}[\ell,R(2),\ldots,R(k)]\land\ldots\land
A^{k}[R(1),\ldots,R(k),\ell]$ $\displaystyle=\exists v^{\prime}\in
f^{-1}(k+1):\forall
i\in[k]:A^{i}[R(1),\ldots,R(i-1),v^{\prime},R(i+1),\ldots,R(k)]$
$\displaystyle=\exists v^{\prime}\in f^{-1}(k+1):\forall i\in[k]:R(1)\ldots
R(i-1)R(i+1)\ldots R(v)v^{\prime}\in E(G)$ (†)

But now note that there is a hyperclique in $G$ if and only if there exists a
configuration $R$ of $V(C_{k+1})\setminus\\{k+1\\}$ such that $({\dagger})$ is
true and $R(1)\ldots R(k)\in E(G)$. Hence we simply calculate $A[R]$ via the
fast $k$-wise matrix product algorithm, then check if such a configuration
exists by iterating through every possible configuration. This takes time
$O(n^{k+1-\varepsilon}+n^{k})=O(n^{k+1-\varepsilon})$.

###  B.2 From Boolean $k$-Wise Matrix Product to Hyperclique

######  Proposition B.4.

Let $T(n)=O(n^{c})$ for some $c\geq 1$. If there is a $T(n)$ time algorithm
for the $k$-uniform $(k+1)$-Hyperclique problem running in time $T(n)$, then
there is an $O(T(n))$ time algorithm solving the $k$-uniform
$(k+1)$-Hyperclique problem which also outputs the vertices of the
$(k+1)$-hyperclique (if one exists).

######  Proof B.5.

The proof is a straightforward binary-search-like algorithm. Let $C_{k+1}$ be
the $k$-uniform $(k+1)$-hyperclique and define
$V(C_{k+1})=\\{1,\ldots,k+1\\}$. For each $i\in[k+1]$, we split the preimage
$f^{-1}(i)$ into two equal parts of size $n/2$. Now for each of the $2^{k+1}$
possible $(k+1)$-tuples of halves from different preimages, we check if there
exists a $(k+1)$-hyperclique between these halves in time $T(n/2)$. If no
tuple has a hyperclique, we return no. If at least one tuple has a
hyperclique, we recurse on one of them, with the new preimages being the
halves selected in the tuple. The base case is reached if there is a single
vertex in each preimage, which we then return.

The running time of this recursive algorithm is
$S(n)=2^{k+1}T(n/2)+S(n/2)=2^{k+1}(T(n/2)+T(n/4)+T(n/8)+\ldots)$. Since
$T(n)=O(n^{c})$ for $c\geq 1$, we have $S(n)=O(T(n))$.

Hence if we can check if a hyperclique exists, we can also find it in
essentially the same time. We now use this to prove the second direction,
which we already stated in lemma 6.4. Recall that the statement of lemma 6.4
is the following:

_If the $k$-uniform $(k+1)$-Hyperclique problem has an algorithm running in
time
$O(n^{k+1-\varepsilon})$ (for some $\varepsilon>0$), then the $k$-wise Matrix
Product problem
has an algorithm running in time $O(n^{k+1-\varepsilon^{\prime}})$ (for some
$\varepsilon^{\prime}>0$)._

######  Proof B.6.

In this proof, we again use the definition of indexing tensors via
configurations from the proof of theorem 5.4 (also used above).

Let the input tensors $A^{1},\ldots,A^{k}$, each of order $k$ and dimensions
$n\times\ldots\times n$ be given. Now consider the $k$-uniform
$(k+1)$-hyperclique $C_{k+1}$ and define $V(C_{k+1})=\\{1,\ldots,k+1\\}$. We
let $G$ be the graph with $n$ vertices per preimage of $C_{k+1}$, with no
hyperedges (yet). In the following, we construct the edges of $G$ and the
color homomorphism $f:V(G)\to V(C_{k+1})$.

For each $i\in[k+1]$, we let the tensor $A^{i}$ be indexed by configurations
of $V(C_{k+1})\setminus\\{i\\}$ with ordering
$(1,\ldots,i-1,k+1,i+1,\ldots,k)$. Now for each configuration $R$ of
$V(C_{k+1})\setminus\\{i\\}$, we add the hyperedge $R(1)\ldots
R(i-1)R(i+1)\ldots R(k+1)$ to $G$ if and only if $A^{i}[R]=1$. Hence we are
encoding the $i$-th input tensor in the hyperedges between the preimages of
$V(C_{k+1})\setminus\\{i\\}$.

Finally, in $V(C_{k+1})\setminus\\{k+1\\}$, we encode the all-ones tensor.
That is, for each configuration $R$ of $V(C_{k+1})\setminus\\{k+1\\}$, we add
the hyperedge $R(1)\ldots R(k)$ to $G$.

We now show how to take advantage of the fast algorithm for $k$-uniform
$(k+1)$-Hyperclique to calculate the $k$-wise matrix product by using it
repeatedly on subinstances of this new hyperclique instance. Let
$A_{\text{res}}$ be the output tensor, initialized to all-zeroes. Now take
$g\in\mathbb{N}$ (chosen later). For each $i\in[k+1]$, we split the preimage
$f^{-1}(i)$ into $g$ parts (i.e. subsets of vertices)
$(f^{-1}(i))_{1},\ldots,(f^{-1}(i))_{g}$, each of size $n/g$ up to rounding.

For any $(k+1)$-tuple $(i(1),\ldots,i(k+1))\in[g]^{k+1}$, we do the following:
$(\star)$ While there is a hyperclique between the parts
$(f^{-1}(1))_{i(1)},\ldots,(f^{-1}(k+1))_{i(k+1)}$ (which can be checked via
the fast algorithm in time $O((n/g)^{k+1-\varepsilon})$), we find this
hyperclique in time $O((n/g)^{k+1-\varepsilon})$ via the algorithm from
Proposition B.4. Let the vertices of the found hyperclique be
$j(1),\ldots,j(k+1)$. Then we set $A_{\text{res}}[j(1),\ldots,j(k)]$ to one
and delete the edge $j(1)\ldots j(k)$ from $G$.

After having gone through all $(k+1)$-tuples, we output $A_{\text{res}}$.

We argue correctness. We use truth values and 0/1 interchangeably. Let the
correct output be $A_{\text{cor}}:=\operatorname{MP}_{k}(A^{1},\ldots,A^{k})$.
We want to prove $A_{\text{cor}}=A_{\text{res}}$. Let $A_{\text{cor}}$ and
$A_{\text{res}}$ be indexed by configurations of
$V(C_{k+1})\setminus\\{k+1\\}$ with ordering $(1,\ldots,k)$. Then for a
configuration $R$ of $V(C_{k+1})\setminus\\{k+1\\}$, we have that
$A_{\text{cor}}[R]$ also satisfies the equation $({\dagger})$ from the proof
of lemma B.2.

Now suppose $A_{\text{res}}[R]=1$. Then certainly $({\dagger})$ is true, so
$A_{\text{cor}}[R]=1$. Conversely, suppose that $A_{\text{cor}}[R]=1$ and
hence that $({\dagger})$ is true. Then when we will find a hyperclique for the
tuple $(i(1),\ldots,i(k))$ such that $\forall j:R(j)\in(f^{-1}(i))_{i(j)}$.
When we find it, the hyperedge $R(1)\ldots R(k)$ either still exists (in which
case we set $A_{\text{cor}}[R]$ to one) or it does not, in which case it must
have been deleted in a previous iteration where we must have then already set
$A_{\text{cor}}[R]$ to one.

Let us analyze the running time. For each successful check in the while loop
$(\star)$, we delete an edge in $E(G)$. Hence there are at most $O(n^{k})$
successful checks. In each successful check, we take time
$O((n/g)^{k+1-\varepsilon})$ for the check itself and another
$O((n/g)^{k+1-\varepsilon})$ for the execution of the while loop content. As
for unsuccessfull while loop checks, we have at most one per $(k+1)$ tuple of
parts, so $g^{k+1}$. Each of these also takes $O((n/g)^{k+1-\varepsilon})$.

Hence the overall running time is
$O(n^{k}(n/g)^{k+1-\varepsilon}+g^{k+1}(n/g)^{k+1-\varepsilon})$. Choosing
$g^{k+1}=n^{k}$ and hence $g=n^{k/(k+1)}$, we have a running time of
$O(n^{k}n^{(1-k/(k+1))(k+1-\varepsilon)})$, which works out to
$O(n^{k+1-\varepsilon/(k+1)})$.