2026-07-22T14:08:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15613 2024-03-06T10:55:45Z ddc:004 open_access

FPT Algorithms for Finding Near-Cliques in c-Closed Graphs Behera, Balaram Husić, Edin Jain, Shweta Roughgarden, Tim Seshadhri, C. c-closed graph dense subgraphs FPT algorithm enumeration algorithm k-plex Moon-Moser theorem Finding large cliques or cliques missing a few edges is a fundamental algorithmic task in the study of real-world graphs, with applications in community detection, pattern recognition, and clustering. A number of effective backtracking-based heuristics for these problems have emerged from recent empirical work in social network analysis. Given the NP-hardness of variants of clique counting, these results raise a challenge for beyond worst-case analysis of these problems. Inspired by the triadic closure of real-world graphs, Fox et al. (SICOMP 2020) introduced the notion of c-closed graphs and proved that maximal clique enumeration is fixed-parameter tractable with respect to c. In practice, due to noise in data, one wishes to actually discover "near-cliques", which can be characterized as cliques with a sparse subgraph removed. In this work, we prove that many different kinds of maximal near-cliques can be enumerated in polynomial time (and FPT in c) for c-closed graphs. We study various established notions of such substructures, including k-plexes, complements of bounded-degeneracy and bounded-treewidth graphs. Interestingly, our algorithms follow relatively simple backtracking procedures, analogous to what is done in practice. Our results underscore the significance of the c-closed graph class for theoretical understanding of social network analysis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Balaram Behera and Edin Husić and Shweta Jain and Tim Roughgarden and C. Seshadhri 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.17 urn:nbn:de:0030-drops-156130 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.17 eng https://creativecommons.org/licenses/by/4.0/legalcode