Faster Algorithms for Generalized Mean Densest Subgraph Problem

The densest subgraph of a large graph usually refers to some subgraph with the highest average degree, which has been extended to the family of p-means dense subgraph objectives by~citetveldt2021generalized. The p-mean densest subgraph problem seeks a subgraph with the highest average p-th-power degree, whereas the standard densest subgraph problem seeks a subgraph with a simple highest average degree. It was shown that the standard peeling algorithm can perform arbitrarily poorly on generalized objective when p>1 but uncertain when 0<p<1. In this paper, we are the first to show that a standard peeling algorithm can still yield 21/p-approximation for the case 0<p < 1. (Veldt 2021) proposed a new generalized peeling algorithm (GENPEEL), which for p ≥ 1 has an approximation guarantee ratio (p+1)1/p, and time complexity O(mn), where m and n denote the number of edges and nodes in graph respectively. In terms of algorithmic contributions, we propose a new and faster generalized peeling algorithm (called GENPEEL++ in this paper), which for p ∈ [1, +∞) has an approximation guarantee ratio (2(p+1))1/p, and time complexity O(m(log n)), where m and n denote the number of edges and nodes in graph, respectively. This approximation ratio converges to 1 as p rightarrow ∞.