{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T21:27:49Z","timestamp":1780349269912,"version":"3.54.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Australian Research Council","doi-asserted-by":"publisher","award":["FT180100256 and DP220103731"],"award-info":[{"award-number":["FT180100256 and DP220103731"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>The k-plex model relaxes the clique model by allowing each vertex to miss up to k neighbors, including the vertex itself. A 1-plex is a clique. Many exact algorithms have been recently designed for finding the k-plex with the largest number of vertices, known as the maximum k-plex computation problem. However, all the existing algorithms, except BS, has the trivial worst-case time complexity of O*(2n) when ignoring polynomial factors. On the other hand, although BS improves the time complexity to O*(\u03b2kn) where \u03b2k &lt; 2 is a constant depending only on k, its practical performance is not satisfactory. In this paper, we study the maximum k-plex computation problem from both theory and practice. We first propose two new reduction rules and a new branching rule and prove that the base of the exponential time complexity is reduced to \u03b3k when the new reduction and branching rules are incorporated into a standard backtracking algorithm; here \u03b3k &lt; \u03b2k. We then design a two-stage approach kPlexT to improve the exponent of the time complexity by separating the search of large k-plexes from the search of small ones. We prove that kPlexT runs in O*((\u03b1 \u0394)k+1 \u03b3_k\u03b1) time when the maximum k-plex size \u03a9k(G) is at least 2k-1, and in O*((\u03b1 \u0394)k+1 \u03b3_k\u03b1 + min(\u03b3kn, n2k-2)) time otherwise; here, \u03b1 is the degeneracy and \u0394 is the maximum degree of the input graph. We also prove that with slight modification, kPlexT runs in O*((\u03b1\u0394)k+1 (k+1)\u03b1+k-\u03a9k(G)) time when \u00f8mega_k(G) \u2265 2k-1. Finally, we propose another reduction rule and a better initialization method to improve the practical performance of kPlexT. Extensive empirical studies demonstrate that kPlexT achieves state-of-the-art practical performance. We also show that our improved time complexity carries over to other related problems such as enumerating all maximal k-plexes, quasi-cliques, and k-biplexes.<\/jats:p>","DOI":"10.1145\/3639318","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":14,"title":["Maximum k-Plex Computation: Theory and Practice"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6830-3900","authenticated-orcid":false,"given":"Lijun","family":"Chang","sequence":"first","affiliation":[{"name":"The University of Sydney, Sydney, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2570-2741","authenticated-orcid":false,"given":"Kai","family":"Yao","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.01.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_4_1","volume-title":"cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. CoRR, Vol. cs.DS\/0310049 (2003)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1178"},{"key":"e_1_2_1_6_1","volume-title":"Proc. of ITCS'22 (LIPIcs","volume":"24","author":"Behera Balaram","unstructured":"Balaram Behera, Edin Husic, Shweta Jain, Tim Roughgarden, and C. Seshadhri. 2022. FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. In Proc. of ITCS'22 (LIPIcs, Vol. 215). 17:1--17:24."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565817"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557444"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589283"},{"key":"e_1_2_1_15_1","volume-title":"Maarten L\u00f6 ffler, and Darren Strash","author":"Eppstein David","year":"2013","unstructured":"David Eppstein, Maarten L\u00f6 ffler, and Darren Strash. 2013. Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics, Vol. 18 (2013)."},{"key":"e_1_2_1_16_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/201"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436916"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/233"},{"key":"e_1_2_1_20_1","volume-title":"Proc. of ISAAC'20 (LIPIcs","volume":"17","author":"Koana Tomohiro","year":"2020","unstructured":"Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. 2020. Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. In Proc. of ISAAC'20 (LIPIcs, Vol. 181). 20:1--20:17."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.02.017"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137660"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9338-2"},{"key":"e_1_2_1_25_1","volume-title":"Foundations of Machine Learning","author":"Mohri Mehryar","unstructured":"Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2012. Foundations of Machine Learning. MIT Press."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9391-5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Apichat Suratanee Martin H Schaefer Matthew J Betts Zita Soons Heiko Mannsperger Nathalie Harder Marcus Oswald Markus Gipp Ellen Ramminger Guillermo Marcus et al. 2014. Characterizing protein interactions employing a genome-wide siRNA cellular phenotyping screen. PLoS computational biology Vol. 10 9 (2014) e1003814.","DOI":"10.1371\/journal.pcbi.1003814"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.03.003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/627"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512198"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77018-3_47"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10655"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588729"},{"key":"e_1_2_1_40_1","volume-title":"Proc. ACM Manag. Data","volume":"2","author":"Yu Kaiqiang","year":"2024","unstructured":"Kaiqiang Yu and Cheng Long. 2024. Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach. Proc. ACM Manag. Data, Vol. 2 (2024)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i14.17477"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i03.5625"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639318","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:15:39Z","timestamp":1755789339000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639318"],"URL":"https:\/\/doi.org\/10.1145\/3639318","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}