# A Multi-Dimensional Matrix Product--A Natural Tool for Parameterized Graph Algorithms
## 2 Preliminaries  
For a positive integer \(r\), we shall denote the set of positive integers not greater than \(r\) by \([r]\).  
For a matrix \(D\), \(D^{T}\) denotes its transpose. Recall that for positive real numbers \(p,\ q,\ s\), \(\omega(p,q,s)\) denotes the smallest real number such that an \(n^{p}\times n^{q}\) matrix can be multiplied by \(n^{q}\times n^{s}\) matrix using \(O(n^{\omega(p,q,s)+\epsilon})\) operations over the field of reals for all \(\epsilon>0\). For convenience, \(\omega\) stands for \(\omega(1,1,1)\).  
Let \(\alpha\) stand for \(sup\{0\leq q\leq 1:\omega(1,q,1)=2+o(1)\}\). The following recent lower bound on \(\alpha\) is due to [PERSON] and [PERSON] [38].  
**Fact 1**: _The inequality \(\alpha>0.31389\) holds [38]._  
Recall also that a _witness_ for a non-zero entry \(C[i,j]\) of the Boolean matrix product \(C\) of a Boolean \(p\times q\) matrix \(A\) and a Boolean \(q\times s\) matrix \(B\) is any index \(\ell\in[q]\) such that \(A[i,\ell]\) and \(B[\ell,j]\) are equal to \(1\). The _witness problem_ is to report a witness for each non-zero entry of the Boolean matrix product of the two input Boolean matrices.  
[PERSON] and [PERSON] provided a solution to the witness problem for the Boolean matrix product of two square Boolean matrices [11] which is almost equally fast as that for square matrix multiplication [4]. It can be easily generalized to include the Boolean product of two rectangular Boolean matrices of sizes \(n^{p}\times n^{q}\) and \(n^{q}\times n^{s}\), respectively. The asymptotic matrix multiplication time \(n^{\omega+o(1)}\) is replaced by \(n^{\omega(p,q,s)+o(1)}\) in the generalization.  
**Fact 2**: _For positive \(p,q,s\), the witness problem for the Boolean matrix product of an \(n^{p}\times n^{q}\) Boolean matrix with an \(n^{q}\times n^{s}\) Boolean matrix can be solved (deterministically) in \(O(n^{\omega(p,q,s)+o(1)})\) time._  
A _directed acyclic graph_ (DAG) is a directed graph not containing directed cycles. A vertex \(v\) is an _ancestor_ (_proper ancestor_) of a vertex \(u\) in a DAG if there is a directed path (directed path of non-zero length, respectively) from \(u\) to \(v\). A vertex \(u\) is a _descendant_ (_proper descendant_) of a vertex \(v\) in a DAG if \(v\) is an ancestor (proper ancestor) of \(u\) in the DAG. Recall that a _lowest common ancestor_ (LCA) of a set of vertices in a DAG is a vertex that is an ancestor of all vertices in the set but none of its proper descendants is also an ancestor of all vertices in the set.  
We shall consider also simple undirected graphs.  
A _subgraph_ of the graph \(G=(V,E)\) is a graph \(H=(V_{H},E_{H})\) such that \(V_{H}\subseteq V\) and \(E_{H}\subseteq E\).  
An _induced subgraph_ of the graph \(G=(V,E)\) is a graph \(H=(V_{H},E_{H})\) such that \(V_{H}\subseteq V\) and \(E_{H}=E\cap(V_{H}\times V_{H})\). A subgraph of \(G\)_induced by \(S\subseteq V\)_ is a graph \(F=(V_{F},E_{F})\) such that \(V_{F}=S\) and \(E_{F}=E\cap(S\times S)\). It is denoted by \(G[S]\).  
For simplicity, we shall refer to a subgraph of a graph \(G\) that is isomorphic to \(K_{r}\) as a _copy_ of \(K_{r}\) in \(G\) or just a \(K_{r}\) copy in \(G\).  
The _adjacency matrix_\(A\) of a graph \(G=(V,E)\) is the \(0-1\)\(n\times n\) matrix such that \(n=|V|\) and for \(1\leq i,j\leq n\), \(A[i,j]=1\) if and only if \(\{i,j\}\in E\).