FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs
summary
Proves fixed-parameter algorithms that enumerate specific near-cliques in c-closed graphs, with concrete bounds: FPT enumeration of maximal (d+1)-plexes in roughly n^{2d}·2^c time, and co-degenerate/co-treewidth cases in about n^{t+4}·4^c or n^{2d+4}·4^c, plus a tight Moon–Moser–style bound for 2-plexes. Techniques are simple backtracking (analysis of recursive call trees) and the Fox et al. three-step reduction; also shows some near-clique variants are not FPT.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:29Real-world graphs
- 5:34Near-Clique counting
- 11:32Clique Enumeration
- 13:54CLIQUE COUNTING Depth of tree
- 15:52C-CLOSED GRAPHS Simple proof for clique counting
- 18:05OTHER NEAR CLIQUES (d+1) plex
- 22:50Bounded co-degeneracy
- 23:51Bounded co-treewidth
- 24:21COUNTING NEAR-CLIQUES Conclusion
- 24:42Conceptual Message