On Finding and Enumerating Maximal and Maximum -Partite Cliques in -Partite Graphs.

Let denote an integer greater than 2, let denote a -partite graph, and let denote the set of all maximal -partite cliques in . Several open questions concerning the computation of are resolved. A straightforward and highly-scalable modification to the classic recursive backtracking approach of Bron and Kerbosch is first described and shown to run in (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 ||. The task of identifying a vertex-maximum element of is also considered and, in contrast with the = 2 case, shown to be -hard for every ≥ 3. A special class of -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.