FPT Algorithms for Finding Dense Subgraphs in c-Closed Graphs
share
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.
READ FULL TEXT