# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 2 The MMCE Algorithm
### Algorithm Synthesis  
From the foregoing, it naturally follows that any algorithm to enumerate maximal cliques in general graphs can be used to enumerate maximal \(k\)-partite cliques in \(k\)-partite graphs. This knowledge forms the genesis of our approach. MMCE (Algorithm 1) first adds intrapartite edges to its input and initializes BK-style vertex sets. It then invokes ENUMERATE, a recursive BK-style subroutine modified to check whether a maximal clique contains a vertex from each partite set. In what follows, we say that a set covers a partition if it contains at least one element from each cell of the partition, and we use \(N(v)\) to denote the neighborhood of vertex \(v\), that is, the set of vertices adjacent to \(v\).  
```
1 input: a \(k\)-partite graph \(G=(V,E)\), with partite sets \(V_{1}\), \(V_{2}\),..., \(V_{k}\);
2 output: all maximal \(k\)-partite cliques in \(G\);
3 add all possible intrapartite edges to \(G\);
4\(R\leftarrow\emptyset\); \(P\gets V\); \(X\leftarrow\emptyset\);
5 ENUMERATE (\(G\), \(R\), \(P\), \(X\));
6 end MMCE Subroutine ENUMERATE (\(G\), \(R\), \(P\), \(X\))
1 input: a graph \(G=(V,E)\), with vertex partition \(V_{1}\), \(V_{2}\),..., \(V_{k}\), a clique \(R\) that covers this partition, and two disjoint subsets \(P\) and \(X\) such that \(P\cup X=\{v\in V;R\subseteq N(v)\}\);
2 output: all maximal cliques covering this partition that extend \(R\) with vertices in \(P\);
3 if \(P=\emptyset\) and \(X=\emptyset\)
4 then if \(R\) covers the partition \(V_{1}\), \(V_{2}\),..., \(V_{k}\)
5 then report \(R\) as a maximal \(k\)-partite clique;
6 return;
7 choose a pivot vertex \(u\) in \(P\cup X\) that maximizes \(\mid P\cap N(u)\mid\);
8 for each vertex \(v\) in \(P\setminus N(u)\)
9 ENUMERATE (\(G\), \(R\cup v\), \(P\cap N(v)\), \(X\cap N(v)\));
10\(P\gets P\setminus v\);
11\(X\gets X\cup v\);
12 end ENUMERATE
```  
**Algorithm 1**MMCE  
**Lemma 1**.: _Determining whether a maximal clique contains at least one vertex from each partite set can be accomplished without increasing the overall time complexity of subroutine ENUMERATE._  
**Proof of Lemma 1.** A judicious application of data structures suffices. For example, let us use an array \(M\) of size \(n\) to store the partite set membership of each vertex, an array \(C\) of size \(k\) to count the number of vertices from each partite set in \(R\), and a scalar \(t\) to record the total number of partite sets currently covered by \(R\). \(C(M(v))\) is incremented upon insertion of \(v\) into \(R\) (when ENUMERATE is invoked). Similarly, \(C(M(v))\) is decremented upon deletion of \(v\) from \(R\) (when ENUMERATE returns). The value of \(t\) is increased (decreased) iff \(C(M(v))\) goes from 0 to 1 (1 to 0). A single comparison of \(t\) versus \(k\) decides whether a maximal clique contains at least one vertex from each partite set. Data structure operations add only a constant number of extra steps to each iteration of ENUMERATE, and thus have no effect on its asymptotic time complexity. \(\square\)  
**Theorem 1**.: _The time complexity of MMCE is \(O(3^{n/3})\)._  
**Proof of Theorem 1.** It is known [9; 10] that BK runs in \(O(3^{n/3})\) time as long as the pivot is selected as specified on line 5 of subroutine ENUMERATE. No increase results from the addition of intrapartite edges, because this is but an \(O(n^{2})\) task. Nor, thanks to Lemma 1, is an increase incurred by checking whether a maximal clique contains at least one vertex from each partite set. Thus, the time complexity of MMCE is \(O(3^{n/3})\). \(\square\)