# A Multi-Dimensional Matrix Product--A Natural Tool for Parameterized Graph Algorithms
## 1 Introduction
### Clique Detection  
Our first application of the multi-dimensional matrix product provides a simple alternative method for clique detection. The problems of detecting, finding, counting or listing subgraphs or induced subgraphs of a host graph that are isomorphic to a pattern graph are central in graph algorithms. They are generally termed as _subgraph isomorphism_ and _induced subgraph isomorphism_, respectively. Several well-known NP-hard problems such as the independent set, clique, Hamiltonian cycle or Hamiltonian path can be regarded as their special cases. Recent examples of applications of different variants of subgraph isomorphism include among other things [12; 13]: a comparison of bio-molecular networks by their so-called motifs [14], an analysis of social networks by counting the number of copies of a small pattern graph [15], graph-matching constraints in the automatic design of processor systems [16], and the detection of communication patterns between intruders in network security [17]. In the aforementioned applications, the pattern graphs are typically of fixed size which allows for polynomial-time solutions. At the beginning of the 1980s, [PERSON] and [PERSON] [18] presented the following straightforward reduction of not only triangle detection but also triangle counting to fast matrix multiplication. Let \(A\) be the \(0-1\) adjacency matrix of the host graph \(G\) on \(n\) vertices (see Preliminaries). Consider the matrix product \(C=A\times A\). Note that \(C[i,j]=\sum_{l=1}^{n}A[i,l]A[l,j]\) is equal to the number of two-edge paths connecting the vertices \(i\) and \(j\). Hence, if \(\{i,j\}\) is an edge of \(G\), then \(C[i,j]\) is the number of triangles in \(G\) including the edge \(\{i,j\}\). Consequently, the number of triangles in an \(n\)-vertex graph can be reported in \(O(n^{\omega+\omega(1)})\) time. A few years later, [PERSON] and [PERSON] [19] showed an efficient reduction of detecting and counting copies of any pattern graph both in the standard and induced case to the aforementioned method for triangle detection and counting. The idea is to divide the pattern graph into three almost equal parts and to build an auxiliary graph on copies of subgraphs isomorphic to one of three parts. Then, the triangle detection/counting method is run on the auxiliary graph. Two decades later, [PERSON] and [PERSON] [20] (cf. [21]) refined this general triangle method by using fast algorithms for rectangular matrix multiplication instead of those for square matrix multiplication. For a pattern graph on \(r\geq 3\) vertices and a host graph on \(n\) vertices, the (refined) general triangle method runs in time \(O(n^{\omega(\lfloor r/3\rfloor,\lceil(r-1)/3\rfloor,\lceil r/3\rceil)+o(1)})\)[19; 20; 21]. Up to now, the general triangle method remains the fastest known universal method for the detection and counting standard and induced copies of fixed pattern graphs. In the recent two decades, there has been a real progress in the design of efficient algorithms for the detection and even counting of fixed pattern graphs both in the standard [12; 22] and induced case [12; 23; 24; 25]. Among other things, the progress has been based on the use of equations between the numbers of copies of different fixed patterns in the host graph [13; 21; 22; 24] and randomization [12; 13; 24]. Unfortunately, this progress has not included complete pattern graphs, i.e., \(K_{r}\) graphs (and their complements, i.e., edge-free pattern graphs in the induced setting). For the aforementioned pattern graphs, the generalized triangle method remains the fastest known one. In this paper, we consider another universal and simple method that in fact can be viewed as another type of generalization of the classic algorithm for triangle detection and counting due to [PERSON] and [PERSON]. We can rephrase the description of their algorithm as follows.