# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 5 A Special Class of Multipartite Graphs
```
1 input: a \(k\)-partite set intersection graph \(G=(V,E)\), with partite sets \(V_{1}\), \(V_{2}\),..., \(V_{k}\);
2 output: all maximal \(k\)-partite cliques in \(G\);
3 compute the bipartite graph \(G_{b}\);
4 invoke MBEA on \(G_{b}\);
5 for each maximal biclique \(B\) returned by MBEA
6 if every partite set of \(G\) contains at least one \(u_{i}\) for which \(v_{i}\in B\)
7 then report \(\{u_{i}\mid v_{i}\in B\}\) as a maximal \(k\)-partite clique;
8 end MMCE-SI
```  
**Algorithm 2**MMCE-SI  
**Theorem 4**. : _Let \(S\), \(G\), and \(G_{b}\) be defined as above, and let \(I\) denote an arbitrary subset of {1, 2,..., \(n\)}. If each partite set of \(G\) contains at least one member of \(U=\{u_{i}\mid i\in I\}\), then \(U\) is a \(k\)-partite clique of \(G\) if \(V=\{v_{i}\mid i\in I\}\) is a biclique of \(G_{b}\)._  
**Proof of Theorem 4. ** Suppose \(S\), \(G\), \(G_{b}\), \(I\), \(U\), and \(V\) satisfy the statement of the theorem, and specifically that the vertices of \(U\) cover all partite sets of \(G\). We first prove the forward (only if) implication, and suppose that \(U\) is a \(k\)-partite clique of \(G\). Because singleton vertex neighborhoods are unchanged by compression, \(V\) must be a biclique of \(G_{b}\). We now prove the reverse (if) implication, and suppose \(V\) is a biclique of \(G_{b}\). We again use the fact that singleton vertex neighborhoods are unchanged by compression, and observe from this that we only need to examine the configuration in which \(v_{i}\) and \(v_{j}\) (\(i\),\(j\in I\)) are subset vertices of \(G_{b}\), and \(u_{i}\) and \(u_{j}\) reside in different partite sets of \(G\). Because \(v_{i}\) and \(v_{j}\) are in \(V\), they have at least one singleton neighbor in common, and so the sets they represent cannot be disjoint. Therefore, \(u_{i}\) and \(u_{j}\) share an edge in \(G\). It follows that \(U\) is a \(k\)-partite clique of \(G\). It follows that maximality is preserved as well. **Corollary 1**. : _Let \(U\) and \(V\) be defined as in Theorem 4. Then \(U\) is a maximal \(k\)-partite clique of \(G\) if \(V\) is a maximal biclique of \(G_{b}\)._  
Therefore, whenever \(k\) exceeds 2, enumerating maximal \(k\)-partite cliques in a \(k\)-partite set intersection graph can be accomplished by enumerating maximal bicliques in the manner just defined. We leave it as an exercise for the reader to construct counterexamples showing that \(k\)-partite graphs with edges based on intersections is insufficient by itself. One partite set must contain only singleton vertices for Theorem 4 to hold. Corollary 1 actually ensures that every maximal \(k\)-partite clique is matched by a (unique) maximal biclique. But the converse does not hold without partite set coverage. Consider, for example, the three vertices in Figures 6 and 8 that represent \(b\), \(c\) and {b,c}. These form a maximal biclique in Figure 8, but not a maximal 3-partite clique in Figure 6.  
**Corollary 2**. : _The number of maximal \(k\)-partite cliques in a \(k\)-partite set intersection graph is bounded above by the number of maximal bicliques in its compressed bipartite graph._  
In addition to providing relative simplicity by dealing only with bipartite graphs, MMCE-SI offers tangible speedup over MMCE as well. To see this, note that the overall time needed by MMCE-SI is dominated by its call to MBEA. We know from [15] that MBEA takes at most \(O(\,|\,E\,|\,)\) time for each maximal biclique it reports, and from [20,22] that a bipartite graph can have at most \(O(2^{n/2})\) such bicliques. Because checking for partite set coverage can be accomplished in \(O(\,|\,E\,|\,)\) time, and because a bipartite graph can have no more than \(n^{2}/4\) edges, it follows that the total time required by MMCE-SI is \(O(n^{2}2^{n/2})\), which is an asymptotic improvement over the \(O(3^{n/3})\) time complexity of MMCE. As previously mentioned, it is \(NP\)-complete to decide whether a graph is \(k\)-partite. We have therefore assumed throughout that an input graph comes along with its \(k\)-partite structure.