{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T16:45:51Z","timestamp":1778690751165,"version":"3.51.4"},"reference-count":35,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,1,15]],"date-time":"2019-01-15T00:00:00Z","timestamp":1547510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01AA018776"],"award-info":[{"award-number":["R01AA018776"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 \u2265 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.<\/jats:p>","DOI":"10.3390\/a12010023","type":"journal-article","created":{"date-parts":[[2019,1,16]],"date-time":"2019-01-16T03:09:13Z","timestamp":1547608153000},"page":"23","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["On Finding and Enumerating Maximal and Maximum k-Partite Cliques in k-Partite Graphs"],"prefix":"10.3390","volume":"12","author":[{"given":"Charles A.","family":"Phillips","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Georgia Southern University, Statesboro, GA 30460, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-5704","authenticated-orcid":false,"given":"Erich J.","family":"Baker","sequence":"additional","affiliation":[{"name":"Computer Science Department, Baylor University, Waco, TX 76798, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5013-1234","authenticated-orcid":false,"given":"Jason A.","family":"Bubier","sequence":"additional","affiliation":[{"name":"The Jackson Laboratory, Bar Harbor, ME 04609, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5642-5062","authenticated-orcid":false,"given":"Elissa J.","family":"Chesler","sequence":"additional","affiliation":[{"name":"The Jackson Laboratory, Bar Harbor, ME 04609, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-5796","authenticated-orcid":false,"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,1,15]]},"reference":[{"key":"ref_1","first-page":"13","article-title":"Finding all k-cliques in k-partite graphs, an application in textile engineering","volume":"29","author":"Irnich","year":"2001","journal-title":"Comput. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.datak.2006.01.005","article-title":"Clicks: An effective algorithm for mining subspace clusters in categorical datasets","volume":"60","author":"Zaki","year":"2007","journal-title":"Data Knowl. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Phillips, C.A., Wang, K., Bubier, J., Baker, E.J., Chesler, E.J., and Langston, M.A. (2015, January 9\u201312). Scalable Multipartite Subgraph Enumeration for Integrative Analysis of Heterogeneous Experimental Functional Genomics Data. Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics, Atlanta, Georgia.","DOI":"10.1145\/2808719.2812595"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/j.jtbi.2013.09.013","article-title":"k-Partite Cliques of Protein Interactions: A Novel Subgraph Topology for Functional Coherence Analysis on PPI Networks","volume":"340","author":"Liu","year":"2014","journal-title":"J. Theor. Biol."},{"key":"ref_5","first-page":"436","article-title":"On an Extremal Problem in Graph Theory","volume":"48","year":"1941","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"ref_6","first-page":"808","article-title":"Tur\u00e1n\u2019s Graph Theorem","volume":"102","author":"Aigner","year":"1995","journal-title":"Am. Math. Mon."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Miller, R., and Thatcher, J. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Algorithm 457: Finding All Cliques of an Undirected Graph","volume":"16","author":"Bron","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","article-title":"The Worst-Case Time Complexity for Generating all Maximal Cliques and Computational Experiments","volume":"363","author":"Tomita","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3.1","DOI":"10.1145\/2543629","article-title":"Listing All Maximal Cliques in Large Sparse Real-World Graphs","volume":"18","author":"Eppstein","year":"2013","journal-title":"J. Exp. Algorithm."},{"key":"ref_11","unstructured":"Zhang, Y., Abu-Khzam, F.N., Baldwin, N.E., Chesler, E.J., Langston, M.A., and Samatova, N.F. (2005, January 12\u201318). Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology. Proceedings of the Supercomputing, Seattle, WA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1198","DOI":"10.1093\/bioinformatics\/17.12.1198","article-title":"Visualizing plant metabolomic correlation networks using clique\u2013metabolite matrices","volume":"17","author":"Kose","year":"2001","journal-title":"Bioinformatics"},{"key":"ref_13","unstructured":"Abu-Khzam, F.N., Baldwin, N.E., Langston, M.A., and Samatova, N.F. (2005, January 7\u20139). On the Relative Efficiency of Maximal Clique Enumeration Algorithms, with Application to High-Throughput Computational Biology. Proceedings of the Proceedings, International Conference on Research Trends in Science and Technology, Beirut, Lebanon."},{"key":"ref_14","first-page":"146","article-title":"A Correspondence Between Maximal Complete Bipartite Subgraphs and Closed Patterns","volume":"Volume 3721","author":"Jorge","year":"2005","journal-title":"Knowledge Discovery in Databases: PKDD 2005"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Phillips, C.A., Rogers, G.L., Baker, E.J., Chesler, E.J., and Langston, M.A. (2014). On Finding Bicliques in Bipartite Graphs: A Novel Algorithm and Its Application to the Integration of Diverse Biological Data Types. BMC Bioinform., 15.","DOI":"10.1186\/1471-2105-15-110"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"D1067","DOI":"10.1093\/nar\/gkr968","article-title":"GeneWeaver: A Web-based System for Integrative Functional Genomics","volume":"40","author":"Baker","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1007\/s11590-012-0536-y","article-title":"On Finding k-cliques in k-partite Graphs","volume":"7","author":"Mirghorbani","year":"2013","journal-title":"Optim. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Makino, K., and Uno, T. (2004). New Algorithms for Enumerating All Maximal Cliques. Algorithm Theory\u2014SWAT 2004, Proceedings of the Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, 8\u201310 July 2004, Springer.","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"ref_19","unstructured":"Miller, R.E., and Muller, D.E. (1960). A Problem of Maximum Consistent Subsets, Watson Research Center. IBM Research Report RC-240."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","article-title":"On Cliques in Graphs","volume":"3","author":"Moon","year":"1965","journal-title":"Isr. J. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00453-010-9474-1","article-title":"On Independent Sets and Bicliques in Graphs","volume":"62","author":"Gaspers","year":"2012","journal-title":"Algorithmica"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s004930070035","article-title":"Bicliques in Graphs, I. Bounds on Their Number","volume":"20","author":"Prisner","year":"2000","journal-title":"Combinatorica"},{"key":"ref_23","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","article-title":"The maximum edge biclique is NP-complete","volume":"131","author":"Peeters","year":"2003","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Manurangsi, P. (2018). Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis. Algorithms, 11.","DOI":"10.3390\/a11010010"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1137\/S089548010240415X","article-title":"Approximating Maximum Clique by Removing Subgraphs","volume":"18","author":"Feige","year":"2004","journal-title":"SIAM J. Discret. Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","article-title":"Clique is Hard to Approximate Within n^(1-\u0454)","volume":"182","year":"1999","journal-title":"Acta Math."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/3-540-48686-0_28","article-title":"On the Complexity of Approximating Colored-Graph Problems","volume":"Volume 1627","author":"Asano","year":"1999","journal-title":"Computing and Combinatorics"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J. (1978, January 1\u20133). The Complexity of Satisfiability Problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/800133.804350"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Aggarwal, C.C. (2011). An Overview of Social Tagging and Applications. Social Network Data Analytics, Springer.","DOI":"10.1007\/978-1-4419-8462-3"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"D555","DOI":"10.1093\/nar\/gkv1329","article-title":"GeneWeaver: Data Driven Alignment of Cross-Species Genomics in Biology and Disease","volume":"44","author":"Baker","year":"2016","journal-title":"Nucleic Acids Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: Tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"ref_33","first-page":"390","article-title":"The Mammalian Phenotype Ontology: Enabling Robust Annotation and Comparative Analysis","volume":"1","author":"Smith","year":"2009","journal-title":"Wiley Interdiscip. Rev."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","article-title":"Quadratic Programming with One Negative Eigenvalue is NP-hard","volume":"1","author":"Pardalos","year":"1991","journal-title":"J. Glob. Optim."},{"key":"ref_35","unstructured":"Zwick, U. (1998, January 25\u201327). Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/1\/23\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:26:02Z","timestamp":1760185562000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/1\/23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,15]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,1]]}},"alternative-id":["a12010023"],"URL":"https:\/\/doi.org\/10.3390\/a12010023","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,15]]}}}