On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms

06/03/2023
by   Chandra Chekuri, et al.
0

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 ∈ (-1/8, 0) ∪ (0, 1/4) the problem is NP-Hard and for any p ∈ (-3,0) ∪ (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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset