# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 1 Introduction  
All graphs we consider are finite, simple and undirected. A graph is \(k\)-partite if it can be partitioned into \(k\) nonempty, vertex-disjoint, edgeless subgraphs. The collection of vertices in each such subgraph is called a 'partite set'. Every edge in a \(k\)-partite graph is thus 'interpartite', that is, it has endpoints in two different partite sets. A \(k\)-partite graph is complete if it contains all possible interpartite edges. Such a graph is specified by \(K_{x_{1},\ldots,x_{k}}\), where \(x_{i}\) denotes the cardinality of partite set \(i\), \(1\leq i\leq k\).  
A \(k\)-partite clique is a set of vertices that induces a complete \(k\)-partite subgraph. A \(k\)-partite clique is maximum if no larger \(k\)-partite clique exists; it is maximal if no vertex can be added to it to form a larger \(k\)-partite clique. The quest for maximum and maximal \(k\)-partite cliques arises in numerous applications, as examples, in textile engineering [1], in categorical data clustering for data mining [2], in the analysis of heterogeneous functional genomics data [3], and in the identification of coherence in protein-protein interaction networks [4].  
A \(k\)-partite graph is balanced if the number of vertices in the various partite sets differ by at most one. Balanced complete \(k\)-partite graphs are known as Turan graphs, named after [PERSON], who studied them in the context of extremal graph theory. [PERSON]'s Theorem [5, 6] states that such graphs have the maximum number of edges possible for a graph with no \((k+1)\)-clique. Although2-partite (a.k.a., bipartite) graphs can be recognized in polynomial time, determining whether a graph is \(k\)-partite for \(k\geq 3\) is \(NP\)-complete [7]. The complexity is inherited from graph coloring: a graph is \(k\)-partite if it is \(k\)-colorable.  
Here we derive a number of new results that are highly relevant to this general problem. In the next section, we describe an uncomplicated and efficient technique to enumerate all maximal \(k\)-partite cliques in a \(k\)-partite graph. We dub this algorithm MMCE, for maximal multipartite clique enumeration. We base it on the classic backtracking method [8] for finding all maximal cliques in non-partite graphs, and show that it runs in \(O(3^{n/3})\) time. In Section 3, we employ a series of innovative combinatorial constructions to prove an asymptotically tight bound on the maximum number of maximal \(k\)-partite cliques in a \(k\)-partite graph, thereby establishing MMCE's asymptotic optimality. In Section 4, we resolve a significant complexity-theoretic issue by proving that finding a \(k\)-partite clique with the maximum number of vertices is \(NP\)-hard for any \(k\geq 3\). Then, in Section 5, we formally characterize a special class of \(k\)-partite graphs that arises in the context of functional genomics and numerous other application domains. We show such graphs to be more readily solvable via a polynomial-time reduction to bipartite graphs, and devise an \(O(kn^{3})\) time recognition algorithm for them. In a final section, we draw conclusions and offer several directions for future research.