On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms

Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical problems here are to find a maxcore (subgraph of maximum min degree) and to find a densest subgraph (subgraph of maximum average degree). Both of these problems can be solved in polynomial time. Veldt, Benson, and Kleinberg [VBK21] introduced the generalized p-mean densest subgraph problem which captures the maxcore problem when p=-∞ and the densest subgraph problem when p=1. They observed that the objective leads to a supermodular function when p ≥ 1 and hence can be solved in polynomial time; for this case, they also developed a simple greedy peeling algorithm with a bounded approximation ratio. In this paper, we make several contributions. First, we prove that for any p ∈ (-frac18, 0) cup (0, frac14) the problem is NP-Hard and for any p ∈ (-3,0) cup (0,1) the weighted version of the problem is NP-Hard, partly resolving a question left open in [VBK21]. Second, we describe two simple 1/2-approximation algorithms for all p < 1, and show that our analysis of these algorithms is tight. For p > 1 we develop a fast near-linear time implementation of the greedy peeling algorithm from [VBK21]. This allows us to plug it into the iterative peeling algorithm that was shown to converge to an optimum solution [CQT22]. We demonstrate the efficacy of our algorithms by running extensive experiments on large graphs. Together, our results provide a comprehensive understanding of the complexity of the p-mean densest subgraph problem and lead to fast and provably good algorithms for the full range of p.