# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 4 Complexity-Theoretic Issues  
The size of a \(k\)-partite clique is typically measured by either its number of vertices or its number of edges. Consider, for example, \(K_{8,1,1}\) versus \(K_{3,3,3}\). The former has more vertices, while the latter has more edges. Thus, for any \(k\geq 2\), a vertex-maximum \(k\)-partite clique may or may not also be edge-maximum, and vice versa. The difference between these two superficially similar versions can be significant. In a bipartite graph, for example, one can find a vertex-maximum biclique in polynomial time [23], while finding an edge-maximum biclique is \(NP\)-hard [24]. Even merely approximating the size of an edge-maximum biclique to within a constant factor turns out to be \(NP\)-hard as well, assuming the small set expansion hypothesis [25]. This is not unlike the situation for the maximum clique problem on general graphs. There it is possible to approximate the optimum to within a factor of \(O(n(\log\!\log n)^{2}/(\log\!n)^{3})\)[26], while approximating it to within a constant factor is as hard as solving the problem exactly [27] (a polynomial-time approximation would lead to a proof that \(P=NP\)). We now demonstrate that this rather curious situation does not extend beyond the bipartite case, by showing that finding a vertex-maximum \(k\)-partite clique in a \(k\)-partite graph is \(NP\)-hard for all \(k\geq 3\). We prove this, naturally, by establishing the \(NP\)-completeness of the decision version of the problem. In some places our proof strengthens, streamlines and makes precise parts of a graph gadget first suggested in [28], where an \(L\)-reduction was proposed to provide an inapproximability result. Although the original reduction is rather vague but probably sound, reasoning about the quality  
Figure 2: An illustration of the construction used in the \(k=5\) case of Theorem 2. Lines denote bundles of edges that are absent from a balanced complete 5-partite graph of order \(n\). of its approximation is incorrect. See Appendix C. In contrast, our proof is disentangled from any inapproximability argument, and extends the reduction to all \(k\geq 3\). **Theorem 3**. : _Given a \(k\)-partite graph, \(G\), with \(k\geq 3\), and a positive integer, \(p\), it is NP-complete to decide whether \(G\) has a \(k\)-partite clique with \(p\) or more vertices._  
Proof of Theorem 3.: Membership in \(NP\) is manifest: a proffered solution can be deterministically checked in \(O(p^{2})\) time. To establish \(NP\)-hardness, we break the analysis into two cases. In the \(k=3\) case, we reduce an \(NP\)-complete variant of 3-SAT to 3-partite independent set, and therefore through complementation to 3-partite clique. Given a Boolean expression, \(E\), in 3 CNF, the one-in-three-SAT problem asks whether \(E\) has a satisfying truth assignment so that each clause has exactly one true literal. one-in-three-SAT is \(NP\)-complete even when restricted to expressions with no negated literals [29], which is the version we employ. So let \(E\) denote an instance of one-in-three-SAT with \(m\) clauses and no negated literals. Thus, we may write \(E=C_{1}\ \land\ldots\ \land\ C_{m}\), where \(C_{i}=l_{i,1}\lor l_{i,2}\lor l_{i,3}\) for \(1\leq i\leq m\), and where no \(l_{i,j}\) is negated. In polynomial time, we shall reduce \(E\) to an instance \(G\) of 3-partite independent set so that \(E\) is one-in-three satisfiable if the 3-partite complement of \(G\) has a 3-partite clique of size \(p=4m\). The reduction proceeds as follows. \(G\) contains nine vertices for each clause. Those associated with \(C_{i}\) are \(x_{i,1}\), \(x_{i,2}\), \(x_{i,3}\), \(y_{i,1}\), \(y_{i,2}\), \(y_{i,3}\), \(z_{i,1}\), \(z_{i,2}\), and \(z_{i,3}\).