On Finding and Enumerating Maximal and Maximum k-Partite Cliques in k-Partite Graphs
Open Access
- 15 January 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 12 (1) , 23
Abstract
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 Bron and Kerbosch is first described and shown to run in O(3n/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 ≥ 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.Keywords
Funding Information
- National Institutes of Health (R01AA018776)
This publication has 27 references indexed in Scilit:
- On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data typesBMC Bioinformatics, 2014
- k-Partite cliques of protein interactions: A novel subgraph topology for functional coherence analysis on PPI networksJournal of Theoretical Biology, 2014
- Listing All Maximal Cliques in Large Sparse Real-World GraphsACM Journal of Experimental Algorithmics, 2013
- On finding k-cliques in k-partite graphsOptimization Letters, 2012
- GeneWeaver: a web-based system for integrative functional genomicsNucleic Acids Research, 2011
- Clicks: An effective algorithm for mining subspace clusters in categorical datasetsData & Knowledge Engineering, 2007
- The worst-case time complexity for generating all maximal cliques and computational experimentsTheoretical Computer Science, 2006
- Finding all k-cliques in k-partite graphs, an application in textile engineeringComputers & Operations Research, 2002
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973
- On cliques in graphsIsrael Journal of Mathematics, 1965