FPT Algorithms for Finding Dense Subgraphs in c-Closed Graphs
Dense subgraph detection is a fundamental problem in network analysis for which few worst-case guarantees are known, motivating its study through the lens of fixed-parameter tractability. But for what parameter? Recent work has proposed parameterizing graphs by their degree of triadic closure, with a $c$-closed graph defined as one in which every vertex pair with at least $c$ common neighbors are themselves connected by an edge. The special case of enumerating all maximal cliques (and hence computing a maximum clique) of a $c$-closed graph is known to be fixed-parameter tractable with respect to $c$ (Fox et al., SICOMP 2020). In network analysis, sufficiently dense subgraphs are typically as notable and meaningful as cliques. We investigate the fixed-parameter tractability (with respect to $c$) of optimization and enumeration in $c$-closed graphs, for several notions of dense subgraphs. We focus on graph families that are the complements of the most well-studied notions of sparse graphs, including graphs with bounded degree, bounded treewidth, or bounded degeneracy, and provide fixed-parameter tractable enumeration and optimization algorithms for these families. To go beyond the special case of maximal cliques, we use a new combinatorial bound (generalizing the Moon-Moser theorem); new techniques for exploiting the $c$-closed condition; and more sophisticated enumeration algorithms.