{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T20:17:43Z","timestamp":1760300263733,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,8,2]],"date-time":"2019-08-02T00:00:00Z","timestamp":1564704000000},"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>In this survey paper, we review various concepts of graph density, as well as associated theorems and algorithms. Our goal is motivated by the fact that, in many applications, it is a key algorithmic task to extract a densest subgraph from an input graph, according to some appropriate definition of graph density. While this problem has been the subject of active research for over half of a century, with many proposed variants and solutions, new results still continuously emerge in the literature. This shows both the importance and the richness of the subject. We also identify some interesting open problems in the field.<\/jats:p>","DOI":"10.3390\/a12080157","type":"journal-article","created":{"date-parts":[[2019,8,2]],"date-time":"2019-08-02T11:58:16Z","timestamp":1564747096000},"page":"157","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["In Search of the Densest Subgraph"],"prefix":"10.3390","volume":"12","author":[{"given":"Andr\u00e1s","family":"Farag\u00f3","sequence":"first","affiliation":[{"name":"Department of Computer Science, Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas, P.O.B. 830688, MS-EC31, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2170-8318","authenticated-orcid":false,"given":"Zohre","family":"R. Mojaveri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas, P.O.B. 830688, MS-EC31, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02289146","article-title":"A method of matrix analysis of group structure","volume":"14","author":"Luce","year":"1949","journal-title":"Psychometrika"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gionis, A., and Tsourakakis, C.E. (2015, January 10\u201313). Dense Subgraph Discovery. KDD Tutorial. Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201915), Sydney, Australia.","DOI":"10.1145\/2783258.2789987"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/net.3230120206","article-title":"A Network Flow Solution to Some Nonlinear 0\u20131 Programming Problems with Application to Graph Theory","volume":"12","author":"Picard","year":"1982","journal-title":"Networks"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","article-title":"A Fast Parametric Maximum Flow Algorithm and Applications","volume":"18","author":"Gallo","year":"1989","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Charikar, M. (2000). Greedy Approximation Algorithms for Finding Dense Components in a Graph. Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000, Springer.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"ref_6","first-page":"23","article-title":"Determination of the Densest Subgraph","volume":"17","author":"Dong","year":"2004","journal-title":"J. Syst. Sci. Complex."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1007\/s11786-007-0026-2","article-title":"A General Tractable Density Concept for Graphs","volume":"1","year":"2008","journal-title":"Math. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","article-title":"k-Degenerate Graphs","volume":"22","author":"Lick","year":"1970","journal-title":"Can. J. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/2402.322385","article-title":"Smallest-Last Ordering and Clustering and Graph Coloring Algorithms","volume":"30","author":"Matula","year":"1983","journal-title":"J. ACM"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Tatti, N., and Gionis, A. (2015, January 18\u201322). Density-Friendly Graph Decomposition. Proceedings of the 24th International World Wide Web Conference (WWW\u201915), Florence, Italy.","DOI":"10.1145\/2736277.2741119"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E. (2015, January 18\u201322). The K-clique Densest Subgraph Problem. Proceedings of the 24th International World Wide Web Conference (WWW\u201915), Florence, Italy.","DOI":"10.1145\/2736277.2741098"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3461","DOI":"10.1007\/s00453-017-0400-7","article-title":"The Densest Subgraph Problem with a Convex\/Concave Size Function","volume":"80","author":"Kawase","year":"2018","journal-title":"Algorithmica"},{"key":"ref_13","first-page":"456","article-title":"Dense Subgraphs With Restrictions and Applications to Gene Annotation Graphs","volume":"Volume 6044","author":"Berger","year":"2010","journal-title":"RECOMB 2010"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1007\/978-3-319-26626-8_41","article-title":"Algorithms for the Densest Subgraph With at Least k Vertices and with a Specified Subset","volume":"Volume 9486","author":"Lu","year":"2015","journal-title":"Combinatorial Optimization and Applications"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Miyauchi, A., and Kakimura, N. (2018, January 22\u201326). Finding a Dense Subgraph with Sparse Cut. Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM\u201918), Torino, Italy.","DOI":"10.1145\/3269206.3271720"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Nagamochi, H., and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity, Cambridge University Press.","DOI":"10.1017\/CBO9780511721649"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chartrand, G., and Kapoor, S.F. (1969). The Cohesive Strength of Graphs. The Many Facets of Graph Theory, Springer. Lecture Notes in Mathematics.","DOI":"10.1007\/BFb0060099"},{"key":"ref_18","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Brandes, U., and Erlebach, T. (2005). Local Density. Network Analysis\u2014Methodological Foundations, Springer.","DOI":"10.1007\/b106453"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","article-title":"Algorithms for maximum independent sets","volume":"7","author":"Robson","year":"1986","journal-title":"J. Algorithms"},{"key":"ref_21","unstructured":"Robson, J.M. (2019, June 10). Finding a Maximum Independent Set in Time O(2n\/4). Available online: http:\/\/www.labri.fr\/perso\/robson\/mis\/techrep.html."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","article-title":"Approximating maximum independent sets by excluding subgraphs","volume":"32","author":"Boppana","year":"1992","journal-title":"BIT Numer. Math."},{"key":"ref_23","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_24","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","article-title":"Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number","volume":"3","author":"Zuckerman","year":"2007","journal-title":"Theory Comput."},{"key":"ref_25","unstructured":"(2019, May 05). ISGCI: Information System on Graph Classes and their Inclusions. Available online: http:\/\/www.graphclasses.org."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","article-title":"A New Algorithm for Generating all the Maximal Independent Sets","volume":"6","author":"Tsukiyama","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","article-title":"On generating all maximal independent sets","volume":"27","author":"Johnson","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","article-title":"Complexity of Finding Dense Subgraphs","volume":"121","author":"Asahiro","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., and Vijayaraghavan, A. (2010, January 6\u20138). Detecting High Log-densities\u2014An O(n1\/4) Approximation for Densest k-Subgraph. Proceedings of the Annual ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806719"},{"key":"ref_30","first-page":"84","article-title":"Densest k-Subgraph Approximation on Intersection Graphs","volume":"Volume 6534","author":"Jansen","year":"2010","journal-title":"Approximation and Online Algorithms (WAOA 2010)"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1006\/jcss.1998.1605","article-title":"Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems","volume":"58","author":"Arora","year":"1999","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Manurangsi, P. (2017, January 19\u201323). Almost-polynomial Ratio ETH-hardness of Approximating Densest k-Subgraph. Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017), Montreal, PQ, Canada.","DOI":"10.1145\/3055399.3055412"},{"key":"ref_33","unstructured":"Khot, S. (2004, January 17\u201319). Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201904), Rome, Italy."},{"key":"ref_34","unstructured":"Charikar, M., Naamad, Y., and Wu, J. (2018). On Finding Dense Common Subgraphs. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Semertzidis, K., Pitoura, E., Terzi, E., and Tsaparas, P. (2018). Finding lasting dense subgraphs. Data Mining and Knowledge Discovery, Springer.","DOI":"10.1007\/s10618-018-0602-x"},{"key":"ref_36","first-page":"436","article-title":"On an Extremal Problem in Graph Theory","volume":"48","year":"1941","journal-title":"Matematikai \u00e9s Fizikai Lapok (Math. Phys. Lett.)"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/BF01895726","article-title":"Extensions of Tur\u00e1ns Theorem on Graphs","volume":"14","author":"Dirac","year":"1963","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1090\/S0002-9904-1946-08715-7","article-title":"On the Structure of Linear Graphs","volume":"52","author":"Stone","year":"1946","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Bachem, A., Korte, B., and Grotschel, M. (1983). Min-Max Results in Combinatorial Optimization. Mathematical Programming\u2014The State of the Art, Springer.","DOI":"10.1007\/978-3-642-68874-4"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF01758774","article-title":"Forests, Frames, and Games: Algorithms for Matroid Sums and Applications","volume":"7","author":"Gabow","year":"1992","journal-title":"Algorithmica"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF02020444","article-title":"On Chromatic Number of Graphs and Set-Systems","volume":"17","author":"Hajnal","year":"1966","journal-title":"Acta Math. Hung."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge University Press.","DOI":"10.1017\/CBO9780511814068"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","article-title":"On Colouring Random Graphs","volume":"77","author":"Grimmett","year":"1975","journal-title":"Math. Proc. Cam. Philos. Soc."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/157\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:12:43Z","timestamp":1760188363000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,2]]},"references-count":43,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080157"],"URL":"https:\/\/doi.org\/10.3390\/a12080157","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,8,2]]}}}