{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T19:06:03Z","timestamp":1783191963650,"version":"3.54.6"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,11,13]]},"abstract":"<jats:p>k-defective cliques relax cliques by allowing up-to k missing edges from being a complete graph. This relaxation enables us to find larger near-cliques and has applications in link prediction, cluster detection, social network analysis and transportation science. The problem of finding the largest k-defective clique has been recently studied with several algorithms being proposed in the literature. However, the currently fastest algorithm KDBB does not improve its time complexity from being the trivial O(2n), and also, KDBB's practical performance is still not satisfactory. In this paper, we advance the state of the art for exact maximum k-defective clique computation, in terms of both time complexity and practical performance. Moreover, we separate the techniques required for achieving the time complexity from others purely used for practical performance consideration; this design choice may facilitate the research community to further improve the practical efficiency while not sacrificing the worst case time complexity. In specific, we first develop a general framework kDC that beats the trivial time complexity of O(2n) and achieves a better time complexity than all existing algorithms. The time complexity of kDC is solely achieved by our newly designed non-fully-adjacent-first branching rule, excess-removal reduction rule and high-degree reduction rule. Then, to make kDC practically efficient, we further propose a new upper bound, two new reduction rules, and an algorithm for efficiently computing a large initial solution. Extensive empirical studies on three benchmark graph collections with 290 graphs in total demonstrate that kDC outperforms the currently fastest algorithm KDBB by several orders of magnitude.<\/jats:p>","DOI":"10.1145\/3617313","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T22:28:39Z","timestamp":1699914519000},"page":"1-26","source":"Crossref","is-referenced-by-count":13,"title":["Efficient Maximum k-Defective Clique Computation with Improved Time Complexity"],"prefix":"10.1145","volume":"1","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"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2_51"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.01.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1178"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00133-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00602-z"},{"key":"e_1_2_1_10_1","series-title":"Springer Series in the Data Sciences","volume-title":"Cohesive Subgraph Computation over Large Sparse Graphs","author":"Chang Lijun","unstructured":"Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs. Springer Series in the Data Sciences."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_2_1_12_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms. McGraw-Hill Higher Education."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557444"},{"key":"e_1_2_1_14_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_15_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_16_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21257"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2020.0984"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.09.039"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of FOCS'96","author":"H\u00e5stad Johan","year":"1996","unstructured":"Johan H\u00e5stad. 1996. Clique is Hard to Approximate Within n(^1-epsilon ). In Proc. of FOCS'96. 627--636."},{"key":"e_1_2_1_20_1","volume-title":"Proc. WSDM'20","author":"Jain Shweta","unstructured":"Shweta Jain and C. Seshadhri. 2020a. The Power of Pivoting for Exact Clique Counting. In Proc. WSDM'20. ACM, 268--276."},{"key":"e_1_2_1_21_1","volume-title":"Proc. of WWW'20","author":"Jain Shweta","year":"1966","unstructured":"Shweta Jain and C. Seshadhri. 2020b. Provably and Efficiently Approximating Near-cliques using the Tur\u00e1 n Shadow: PEANUTS. In Proc. of WWW'20. ACM \/ IW3C2, 1966--1976."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676847"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_24_1","volume-title":"Aggarwal","author":"Lee Victor E.","year":"2010","unstructured":"Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu C. Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. In Managing and Mining Graph Data. Advances in Database Systems, Vol. 40. Springer, 303--336."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2013.143"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.02.017"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_29_1","volume-title":"Pardalos and Jue Xue","author":"Panos","year":"1994","unstructured":"Panos M. Pardalos and Jue Xue. 1994. The maximum clique problem. J. global Optimization, Vol. 4, 3 (1994), 301--328."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2014.986778"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_2_1_33_1","unstructured":"J. M. Robson. 2001. Finding a maximum independent set in time $O(2^n\/4)$. smallhttps:\/\/www.labri.fr\/perso\/robson\/mis\/techrep.html."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/14100018X"},{"key":"e_1_2_1_35_1","volume-title":"Regular Graphs with Given Girth and Restricted Circuits. Journal of the London Mathematical Society","author":"Sachs H.","year":"1963","unstructured":"H. Sachs. 1963. Regular Graphs with Given Girth and Restricted Circuits. Journal of the London Mathematical Society, Vol. s1--38, 1 (1963), 423--429."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.36.4.378.546"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01572-4"},{"key":"e_1_2_1_40_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_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_18"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9548-5"},{"key":"e_1_2_1_45_1","volume-title":"Proc. of AAAI'96","author":"Verfaillie G\u00e9","year":"1996","unstructured":"G\u00e9 rard Verfaillie, Michel Lema^i tre, and Thomas Schiex. 1996. Russian Doll Search for Solving Constraint Optimization Problems. In Proc. of AAAI'96. AAAI Press \/ The MIT Press, 181--187."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_47_1","volume-title":"Proc. of ICDE'13","author":"Xiang Jingen","year":"2013","unstructured":"Jingen Xiang, Cong Guo, and Ashraf Aboulnaga. 2013. Scalable maximum clique computation using mapreduce. In Proc. of ICDE'13. 74--85."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"},{"key":"e_1_2_1_50_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\/3617313","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:15Z","timestamp":1750178775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617313"],"URL":"https:\/\/doi.org\/10.1145\/3617313","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}