{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:15:47Z","timestamp":1776122147588,"version":"3.50.1"},"reference-count":68,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2016,3,16]],"date-time":"2016-03-16T00:00:00Z","timestamp":1458086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Community detection is an important task in the analysis of biological, social or technical networks. We survey different models of cohesive graphs, commonly referred to as clique relaxations, that are used in the detection of network communities. For each clique relaxation, we give an overview of basic model properties and of the complexity of the problem of finding large cohesive subgraphs under this model. Since this problem is usually NP-hard, we focus on combinatorial fixed-parameter algorithms exploiting typical structural properties of input networks.<\/jats:p>","DOI":"10.3390\/a9010021","type":"journal-article","created":{"date-parts":[[2016,3,16]],"date-time":"2016-03-16T11:26:45Z","timestamp":1458127605000},"page":"21","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":42,"title":["Multivariate Algorithmics for Finding Cohesive Subnetworks"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Ernst-Abbe-Platz 2, D-07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,3,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/msb4100129","article-title":"Network-based prediction of protein function","volume":"3","author":"Sharan","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications, Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","article-title":"Graph structure in the web","volume":"33","author":"Broder","year":"2000","journal-title":"Comput. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1086\/soutjanth.10.1.3629074","article-title":"Cultures of the central highlands, New Guinea","volume":"10","author":"Read","year":"1954","journal-title":"Southwest. J. Anthropol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.ejor.2012.10.021","article-title":"On clique relaxation models in network analysis","volume":"226","author":"Pattillo","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"543","DOI":"10.7155\/jgaa.00273","article-title":"The h-Index of a graph and its application to dynamic subgraph statistics","volume":"16","author":"Eppstein","year":"2012","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-540-31955-9_6","article-title":"Local Density","volume":"Volume 3418","author":"Kosub","year":"2004","journal-title":"Network Analysis: Methodological Foundations"},{"key":"ref_9","unstructured":"Balasundaram, B., and Pajouh, F.M. (2013). Handbook of Combinatorial Optimization, Springer."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","article-title":"Network structure and minimum degree","volume":"5","author":"Seidman","year":"1983","journal-title":"Soc. Netw."},{"key":"ref_11","unstructured":"Cohen, J. (2008). Trusses: Cohesive Subgraphs for Social Network Analysis, National Security Agency. National Security Agency Technical Report."},{"key":"ref_12","unstructured":"Goldberg, A.V. (1984). Finding a Maximum Density Subgraph, University of California Berkeley. Technical Report."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","article-title":"The node-deletion problem for hereditary properties is NP-complete","volume":"20","author":"Lewis","year":"1980","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.dam.2015.04.029","article-title":"An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems","volume":"193","author":"Komusiewicz","year":"2015","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","article-title":"Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity","volume":"34","author":"Fellows","year":"2013","journal-title":"Eur. J. Comb."},{"key":"ref_18","first-page":"19","article-title":"New races in parameterized algorithmics","volume":"Volume 7464","author":"Komusiewicz","year":"2012","journal-title":"Lecture Notes in Computer Science, Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS \u201912)"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","article-title":"Parameterized complexity of finding subgraphs with hereditary properties","volume":"289","author":"Khot","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which problems have strongly exponential complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","article-title":"Tight lower bounds for certain parameterized NP-hard problems","volume":"201","author":"Chen","year":"2005","journal-title":"Inf. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","article-title":"Improved upper bounds for vertex cover","volume":"411","author":"Chen","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","article-title":"Scalable parallel algorithms for FPT problems","volume":"45","author":"Langston","year":"2006","journal-title":"Algorithmica"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5384","DOI":"10.1016\/j.tcs.2009.05.008","article-title":"Isolation concepts for clique enumeration: Comparison and computational experiments","volume":"410","author":"Komusiewicz","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., and Strash, D. (2013). Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithm., 18.","DOI":"10.1145\/2543629"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","article-title":"A graph-theoretic generalization of the clique concept","volume":"6","author":"Seidman","year":"1978","journal-title":"J. Math. Sociol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3640","DOI":"10.1016\/j.tcs.2009.04.021","article-title":"Isolation concepts for efficiently enumerating dense subgraphs","volume":"410","author":"Komusiewicz","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1016\/j.jcss.2010.12.001","article-title":"A generalization of Nemhauser and Trotter\u2019s local optimization theorem","volume":"77","author":"Fellows","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10878-011-9391-5","article-title":"Exact combinatorial algorithms and experiments for finding maximum k-plexes","volume":"24","author":"Moser","year":"2012","journal-title":"J. Comb. Optim."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1287\/opre.1100.0851","article-title":"Clique relaxations in social network analysis: The maximum k-plex problem","volume":"59","author":"Balasundaram","year":"2011","journal-title":"Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10878-010-9338-2","article-title":"Combinatorial algorithms for the maximum k-plex problem","volume":"23","author":"McClosky","year":"2012","journal-title":"J. Comb. Optim."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s10589-013-9548-5","article-title":"Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations","volume":"56","author":"Trukhanov","year":"2013","journal-title":"Comput. Optim. Appl."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0304-3975(98)00091-7","article-title":"Classifying molecular sequences using a linkage graph with their pairwise similarities","volume":"210","author":"Matsuda","year":"1999","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Pei, J., Jiang, D., and Zhang, A. (2005, January 21\u201324). On mining cross-graph quasi-cliques. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201905), Chicago, IL, USA.","DOI":"10.1145\/1081870.1081898"},{"key":"ref_35","first-page":"33","article-title":"Effective pruning techniques for mining quasi-cliques","volume":"Volume 5212","author":"Liu","year":"2008","journal-title":"Lecture Notes in Computer Science, Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML\/PKDD \u201908)"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1080\/0022250X.1973.9989826","article-title":"A graph-theoretic definition of a sociometric clique","volume":"3","author":"Alba","year":"1973","journal-title":"J. Math. Sociol."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF00139635","article-title":"Cliques, clubs and clans","volume":"13","author":"Mokken","year":"1979","journal-title":"Qual. Quant."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0377-2217(01)00133-3","article-title":"An exact algorithm for the maximum k-club problem in an undirected graph","volume":"138","author":"Bourjolly","year":"2002","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10878-005-1857-x","article-title":"Novel approaches for analyzing biological networks","volume":"10","author":"Balasundaram","year":"2005","journal-title":"J. Comb. Optim."},{"key":"ref_40","unstructured":"Sch\u00e4fer, A. (2009). Exact Algorithms for s-Club Finding and Related Problems. [Diplomarbeit (diploma thesis), Friedrich-Schiller-Universit\u00e4t Jena]."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","article-title":"Parameterized computational complexity of finding small-diameter subgraphs","volume":"6","author":"Komusiewicz","year":"2012","journal-title":"Optim. Lett."},{"key":"ref_42","unstructured":"Chang, M., Hung, L., Lin, C., and Su, P. (2011, January 27\u201328). Finding large k-clubs in undirected graphs. Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"155","DOI":"10.7155\/jgaa.00352","article-title":"Parameterized algorithmics and computational experiments for finding 2-clubs","volume":"19","author":"Hartung","year":"2015","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.dam.2014.11.026","article-title":"On structural parameterizations for the 2-club problem","volume":"185","author":"Hartung","year":"2015","journal-title":"Discret. Appl. Math."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02289199","article-title":"Connectivity and generalized cliques in sociometric group structure","volume":"15","author":"Luce","year":"1950","journal-title":"Psychometrika"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1016\/S0305-0548(99)00047-7","article-title":"Heuristics for finding k-clubs in an undirected graph","volume":"27","author":"Bourjolly","year":"2000","journal-title":"Comput. OR"},{"key":"ref_47","first-page":"598","article-title":"Massive quasi-clique detection","volume":"Volume 2286","author":"Abello","year":"2002","journal-title":"Lecture Notes in Computer Science, Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN \u201902)"},{"key":"ref_48","first-page":"41","article-title":"On effectively finding maximal quasi-cliques in graphs","volume":"Volume 5313","author":"Brunato","year":"2008","journal-title":"Lecture Notes in Computer Science, Proceedings of the Selected Papers of the Second International Conference on Learning and Intelligent Optimization (LION \u201907)"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/j.dam.2012.07.019","article-title":"On the maximum quasi-clique problem","volume":"161","author":"Pattillo","year":"2013","journal-title":"Discret. Appl. Math."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","article-title":"The dense k-subgraph problem","volume":"29","author":"Feige","year":"2001","journal-title":"Algorithmica"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10479-012-1242-y","article-title":"A branch-and-bound approach for maximum quasi-cliques","volume":"216","author":"Pajouh","year":"2014","journal-title":"Ann. Oper. Res."},{"key":"ref_52","unstructured":"Komusiewicz, C., Sorge, M., and Stahl, K. (July, January 29). Finding connected subgraphs of fixed minimum density: Implementation and experiments. Proceedings of the 14th International Symposium on Experimental Algorithms (SEA \u201915), Paris, France."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1007\/s00453-011-9487-4","article-title":"Editing graphs into disjoint unions of dense clusters","volume":"61","author":"Guo","year":"2011","journal-title":"Algorithmica"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Veremyev, A., Prokopyev, O.A., Butenko, S., and Pasiliao, E.L. (2016). Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs. Comput. Optim. Appl, to appear.","DOI":"10.1007\/s10589-015-9804-y"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.ejor.2014.05.041","article-title":"Finding maximum subgraphs with relatively large vertex connectivity","volume":"239","author":"Veremyev","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1137\/0114065","article-title":"A graph-theoretic approach to a communications problem","volume":"14","author":"Chartrand","year":"1966","journal-title":"SIAM J. Appl. Math."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0020-0190(00)00142-3","article-title":"A clustering algorithm based on graph connectivity","volume":"76","author":"Hartuv","year":"2000","journal-title":"Inf. Process. Lett."},{"key":"ref_58","first-page":"254","article-title":"Finding highly connected subgraphs","volume":"Volume 8939","author":"Komusiewicz","year":"2015","journal-title":"Lecture Notes in Computer Science, Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM \u201915)"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1007\/s00453-011-9492-7","article-title":"Approximation and tidying\u2013A problem kernel for s-plex cluster vertex deletion","volume":"62","author":"Moser","year":"2012","journal-title":"Algorithmica"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"1662","DOI":"10.1137\/090767285","article-title":"A more relaxed model for graph-based data clustering: s-Plex cluster editing","volume":"24","author":"Guo","year":"2010","journal-title":"SIAM J. Discret. Math."},{"key":"ref_61","unstructured":"Gschwind, T., Irnich, S., Furini, F., and Calvo, R.W. (2015). Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz. Technical Report LM-2015-07."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/TCBB.2013.177","article-title":"Partitioning biological networks into highly connected clusters with maximum edge coverage","volume":"11","author":"Komusiewicz","year":"2014","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_63","first-page":"235","article-title":"On editing graphs into 2-club clusters","volume":"Volume 7285","author":"Liu","year":"2012","journal-title":"Lecture Notes in Computer Science, Proceedings of the Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM \u201912)"},{"key":"ref_64","first-page":"157","article-title":"Alliances in graphs","volume":"48","author":"Kristiansen","year":"2004","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"70","DOI":"10.5614\/ejgta.2014.2.1.7","article-title":"A survey on alliances and related parameters in graphs","volume":"2","author":"Fernau","year":"2014","journal-title":"Electr. J. Graph Theory Appl."},{"key":"ref_66","unstructured":"Enciso, R.I. (2009). Alliances in Graphs: Parameterized Algorithms and on Partitioning Series-Parallel Graphs. [Ph.D. Thesis, University of Central Florida]."},{"key":"ref_67","unstructured":"Fernau, H., and Raible, D. (2007, January 20\u201326). Alliances in graphs: A complexity-theoretic study. Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM \u201907), Harrachov, Czech Republic."},{"key":"ref_68","doi-asserted-by":"crossref","unstructured":"Ito, H., and Iwama, K. (2009). Enumeration of isolated cliques and pseudo-cliques. ACM Trans. Algorithms, 5.","DOI":"10.1145\/1597036.1597044"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/1\/21\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:20:47Z","timestamp":1760210447000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/1\/21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,16]]},"references-count":68,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,3]]}},"alternative-id":["a9010021"],"URL":"https:\/\/doi.org\/10.3390\/a9010021","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,16]]}}}