English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Finding large cliques or cliques missing a few edges is a fundamentalalgorithmic task in the study of real-world graphs, with applications incommunity detection, pattern recognition, and clustering. A number of effectivebacktracking-based heuristics for these problems have emerged from recentempirical work in social network analysis. Given the NP-hardness of variants ofclique counting, these results raise a challenge for beyond worst-case analysisof these problems. Inspired by the triadic closure of real-world graphs, Fox etal. (SICOMP 2020) introduced the notion of $c$-closed graphs and proved thatmaximal 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 subgraphremoved. In this work, we prove that many different kinds of maximalnear-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-treewidthgraphs. Interestingly, our algorithms follow relatively simple backtrackingprocedures, analogous to what is done in practice. Our results underscore thesignificance of the $c$-closed graph class for theoretical understanding ofsocial network analysis.

FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs