Summary: 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, J. Fox et al. [SIAM J. Comput. 49, No. 2, 448–464 (2020; Zbl 1443.68128)] 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.
For the entire collection see [Zbl 1482.68012].