2022/07/18 by Yi Zhou, Zhou, Yi, Shan Hu +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2207.08340
openalex publication_date 2022/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 fe:ℤ≥0→ ℝ≥ 0 to represent the partial edge-weight of a hyperedge e in the input hypergraph H=(V,E,f) and formulate a generalized densest sub-hypergraph problem (GDSH) as maxS⊆ V\frac∑e∈ Efe(|e∩ 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 (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.