Kavli Affiliate: Yi Zhou
| First 5 Authors: Yi Zhou, Shan Hu, Zimo Sheng, ,
| Summary:
The densest subgraph problem (DSG) aiming at finding an induced subgraph such
that the average edge-weights of the subgraph is maximized, is a well-studied
problem. However, when the input graph is a hypergraph, the existing notion of
DSG fails to capture the fact that a hyperedge partially belonging to an
induced sub-hypergraph is also a part of the sub-hypergraph. To resolve the
issue, we suggest a function $f_e:mathbb{Z}_{ge0}rightarrow mathbb{R}_{ge
0}$ to represent the partial edge-weight of a hyperedge $e$ in the input
hypergraph $mathcal{H}=(V,mathcal{E},f)$ and formulate a generalized densest
sub-hypergraph problem (GDSH) as $max_{Ssubseteq V}frac{sum_{ein
mathcal{E}}{f_e(|ecap S|)}}{|S|}$. We demonstrate that, when all the
edge-weight functions are non-decreasing convex, GDSH can be solved in
polynomial-time by the linear program-based algorithm, the network flow-based
algorithm and the greedy $frac{1}{r}$-approximation algorithm where $r$ is the
rank of the input hypergraph. Finally, we investigate the computational
tractability of GDSH where some edge-weight functions are non-convex.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=10