On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs (Q2633284)

Summary: Let \( k\) denote an integer greater than 2, let \( G\) denote a \( k\)-partite graph, and let \( S\) denote the set of all maximal \( k\)-partite cliques in \( G\). Several open questions concerning the computation of \( S\) are resolved. A straightforward and highly-scalable modification to the classic recursive backtracking approach of \textit{C. Bron} and \textit{J. Kerbosch} [Commun. ACM 16, 575--577 (1973; Zbl 0261.68018)] is first described and shown to run in \( O(3^{n^/3})\) time. A series of novel graph constructions is then used to prove that this bound is best possible in the sense that it matches an asymptotically tight upper limit on \( |S|\). The task of identifying a vertex-maximum element of \( S\) is also considered and, in contrast with the \( k=2\) case, shown to be NP-hard for every \( k\geq 3\). A special class of \( k\)-partite graphs that arises in the context of functional genomics and other problem domains is studied as well and shown to be more readily solvable via a polynomial-time transformation to bipartite graphs. Applications, limitations, potentials for faster methods, heuristic approaches, and alternate formulations are also addressed.