# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 6 Summary and Directions for Future Research  
With this work we have derived a number of new results concerning the enumeration of maximum and maximal \(k\)-partite cliques in \(k\)-partite graphs. In so doing, we have resolved fundamental questions concerning both asymptotic optimality and algorithmic complexity. We have modified the well-known Bron and Kerbosch approach so that it could be applied to multipartite graphs, and shown that the resultant algorithm runs in \(O(3^{n/3})\) time. We have proved that this matches the minimum asymptotic worst-case bound. We have also considered the problem of identifying a vertex-maximum \(k\)-partite clique and, unlike the bipartite case, shown it to be _NP_-hard for all \(k\geq 3\). We have introduced and studied \(k\)-partite set intersection graphs, proved them to be more efficiently solvable via a reduction to bipartite graphs, and developed an \(O(kn^{3})\) algorithm for their recognition. Problems amenable to this general approach abound. A \(k\)-partite graph model may be reasonable whenever associations between heterogeneous data types can be scored with a similarity metric. In that regard, maximal \(k\)-partite cliques are a 'gold standard' for multidimensional density-based clustering. With minor algorithmic alterations, the range of MMCE's applications can readily be widened. In a data mining setting, for example, a maximal \(k\)-partite clique corresponds to a maximal full space cluster. Checking that only \(k^{\prime}<k\) partite sets are covered (line 2 of ENUMERATE) produces an algorithm to enumerate all maximal subspace clusters of at least \(k^{\prime}\) dimensions. Similarly, MMCE can easily be modified to produce only vertex (edge) maximum \(k\)-partite cliques, or \(k\)-partite cliques with some pre-specified number vertices (edges). I/O limitations are frequently overlooked or ignored, but in this particular case they merit some mention. Input is of course only an \(O(n^{2})\) operation. The standard output premise [9; 10], however, and the one we have adopted here, is that \(k\)-partite cliques are merely reported, not written, as they are discovered. Because a clique may contain \(O(n)\) vertices, listing clique contents would add a linear factor to MMCE's \(O(3^{n/3})\) run time. But we know from Theorem 2 that, for every fixed \(k\geq 3\), there are infinitely many \(k\)-partite graphs with \(\sim\)\(3^{n/3}\) maximal \(k\)-partite cliques. Moreover, these cliques each contain \(n/3\) vertices because of the way partite sets are tripartitioned. Any listing algorithm must therefore require \(\Omega(n3^{n/3})\) time in the worst case, and so an adaptation of MMCE that outputs, not just reports, maximal cliques is also asymptotically optimal. Numerous research questions beckon. For example, can heuristic strategies provide improvement? What if one were to start by removing any vertex not part of a 3-clique or without neighbors in every partite set? And what of pivot strategies? Are any selection techniques particularly well-suited for \(k\)-partite graphs? One might also entertain the idea of checking partite set coverage in more sophisticated ways, although an amortized form of analysis may be required. Finally, we consider the decision version of the edge-maximum biclique problem and observe that its proof of _NP_-completeness [24] resolves, perhaps unknowingly, a quadratic programming conjecture [34], which posited that minimizing a product of linear functions is _NP_-hard. The complexity-theoretic resolution of edge-maximum biclique actually settles a somewhat stronger version of the quadratic programming conjecture, one that restricts numeric variables to binary values. In contrast, the complexity of deciding edge-maximum \(k\)-partite clique for \(k\geq 3\) remains open. We are, quite naturally, confident that it too is _NP_-complete. Rather oddly, however, the proof for the bipartite case does not appear to generalize because of the sum-of-products formula used to determine the number of edges in a \(k\)-partite clique.