Extracting Densest Sub-hypergraph with Convex Edge-weight Functions

Abstract

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}}_{\ge 0}\to {\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 }_{S\subseteq V}\frac{{\sum }_{e\in \mathcal{E}}{f}_e(|e\cap 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.