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

Area of Science:

• Graph Theory
• Computational Complexity
• Algorithms

Background:

• Maximal k-partite cliques are fundamental in graph theory.
• Efficient computation of these cliques is a significant algorithmic challenge.
• Existing methods may not scale for larger or complex k-partite graphs.

Purpose of the Study:

• To resolve open questions regarding the computation of maximal k-partite cliques.
• To develop a scalable algorithm for finding maximal k-partite cliques.
• To analyze the complexity of finding vertex-maximum cliques in k-partite graphs.

Main Methods:

• A modified recursive backtracking algorithm based on Bron and Kerbosch.
• Novel graph constructions to establish tight upper bounds on clique set size.
• Complexity analysis, including NP-hardness proofs.
• Polynomial-time transformations for specific graph classes.

Main Results:

• A highly-scalable algorithm with O(3^n) time complexity for maximal k-partite clique computation.
• Proof that the O(3^n) bound is asymptotically tight.
• Identification of the vertex-maximum k-partite clique problem as NP-hard for k >= 3.
• Efficient polynomial-time solution for a special class of k-partite graphs relevant to functional genomics.

Conclusions:

• The developed algorithm offers an efficient and scalable approach to finding maximal k-partite cliques.
• The NP-hardness result highlights the inherent difficulty of optimizing clique selection in general k-partite graphs.
• Specialized graph structures can be solved more efficiently, suggesting domain-specific algorithmic advantages.