# A Multi-Dimensional Matrix Product--A Natural Tool for Parameterized Graph Algorithms
## 6 All \(k\)-Tuples LCA  
In this section, we consider the lowest common ancestors of \(k\geq 2\) vertices [30]. For an example, see Figure 1.  
Recall that an LCA of vertices \(v_{1},\dots,v_{k}\) is an ancestor \(v\) of each vertex \(v_{i}\), \(i\in[k]\) such that \(v\) has no proper descendant that is also an ancestor of each vertex \(v_{i}\), \(i\in[k]\). We can generalize the method of solving the all pairs LCA problem in DAGs based on maximum witnesses of Boolean matrix products from [9] to include the all \(k\)-tuples LCA  
Figure 1: Both F and H are LCA for the 3-tuple A, B, C while G does not have this property. problem, i.e., reporting for each \(k\)-tuple of vertices in the input DAG an LCA, as follows (in Algorithm 4). _Input_: A DAG \(G\) on \(n\) vertices and a natural number \(k\geq 2\). _Output_: A solution to the all \(k\)-tuples LCA problem in the input DAG. 1. Topologically sort vertices of the input DAG \(G\) and number them in the sorted order starting from the source vertices. 2. Compute the \(n\times n\) transitive closure matrix \(A\) of \(G\) such that \(A[i,j]=1\) if and only if the vertex \(j\) is an ancestor of the vertex \(i\). 3. Compute maximum witnesses for non-zero entries of the \(k\)-dimensional Boolean matrix product \(D\) of \(k\) copies of the Boolean version of the matrix \(A\). 4. For each \(k\)-tuple \(i_{1},i_{2},\ldots,i_{k}\) of vertices, output the maximum witness of \(D[i_{1},i_{2},\ldots,i_{k}]\) (if any) as the LCA of the \(k\)-tuple. **Algorithm 4** Reporting for each \(k\)-tuple of vertices in the input DAG an LCA. The correctness of this generalized method follows from the fact that by the definition of the matrix \(A\) and the \(k\)-dimensional Boolean matrix product \(D\), the set of witnesses of \(D[i_{1},i_{2},\ldots,i_{k}]\) coincides with the set of common ancestors of \(i_{1},i_{2},\ldots,i_{k}\), and that the maximum witness of of \(D[i_{1},i_{2},\ldots,i_{k}]\) cannot have any descendant in the aforementioned set by the vertex numbering. The topological sort requires \(O(n^{2})\) time while computing the transitive closure takes \(O(n^{\omega+o(1)})\) time. Hence, by Theorem 3, we obtain upper bounds basically matching those derived by [PERSON] in [36] and [PERSON] et al. in [37]. **Theorem 6**. : _Let \(\lambda\) satisfy \(\omega_{k}(1,\lambda)=k-1+2\lambda\) and let \(\lambda^{\prime}\) satisfy \(\omega(\lceil k/2\rceil,\lambda^{\prime},\lfloor k/2\rfloor)=k-1+2\lambda^{\prime}\), respectively. Suppose \(k=O(1)\). The all \(k\)-tuples LCA problem can be solved by Algorithm 4 in \(O(n^{k+\lambda+o(1)})=O(n^{k+\lambda^{\prime}+o(1)})\) time._  
**Corollary 4**. : _Let \(\lambda,\lambda^{\prime}\) and \(\lambda^{\prime\prime}\) satisfy \(\omega_{3}(1,\lambda)=2+2\lambda\), \(\omega(2,\lambda^{\prime},1)=2+2\lambda^{\prime}\), and \(\omega(1,\lambda^{\prime\prime},1)=1+2\lambda^{\prime\prime}\), respectively. The all \(3\)-tuples LCA problem can be solved in \(O(n^{3+\lambda+o(1)})=O(n^{3+\lambda^{\prime}+o(1)})\)\(=(n^{3+\lambda^{\prime\prime}+o(1)})=O(n^{3.529})\) time._  
**Proof. ** By dividing an \(n^{2}\times n^{\prime}\) matrix into \(n\times n^{\prime}\) matrices, we obtain the inequality \(1+\omega(1,r,1)\geq\omega(2,r,1)\). The inequality \(\lambda^{\prime\prime}\geq\lambda^{\prime}\) follows from \(1+\omega(1,r,1)\geq\omega(2,r,1)\) similarly as \(\lambda^{\prime}\geq\lambda\) follows from \(\omega_{3}(1,r)\leq\omega(2,r,1)\) in the proof of Theorem 3. By the recent results on fast rectangular multiplication, \(\lambda^{\prime\prime}<0.529\) holds. **7. Final Remarks**  
We have applied our results on the multi-dimensional matrix product to provide a simple alternative method for clique detection and to rephrase known algorithms for \(k\)-dominating set problem and the all \(k\)-tuples LCA problem in DAGs. Our direct reduction of the \(k\)-dominating set problem to the \(k\)-dimensional matrix product yields the \(W[2]\) hardness of the latter problem.