Faster Algorithms for Generalized Mean Densest Subgraph Problem
Chenglin Fan Ping Li Hanyu Peng
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~\citet{veldt2021generalized}. 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 $2^{1/p}$-approximation for the case $0<p < 1$.
(Veldt 2021) proposed a new generalized peeling algorithm (GENPEEL), which for
$p \geq 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 \in [1, +\infty)$ 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 \infty$.