论文标题
用凸边缘重量功能提取最密集的亚hypergraph
Extracting Densest Sub-hypergraph with Convex Edge-weight Functions
论文作者
论文摘要
旨在查找诱导子图的最密集的子图问题（DSG），以使该子图的平均边缘重量最大化，这是一个充分研究的问题。但是，当输入图是超图时，现有的DSG概念未能捕获一个事实，即部分属于诱导的亚hypergraph的高度也是亚hypergraph的一部分。要解决问题，我们建议一个函数$ f_e：\ mathbb {z} _ {\ ge0} \ rightarrow \ rightArrow \ mathbb {r} _ {\ ge 0} $表示输入$ \ \ mathcal $ \ nathcal $ \ natercal $ \ mathcal {e $ and的hypereedge $ e $的部分边缘 - 广义密集的子hypergraph问题（gdsh）作为$ \ max_ {s \ subseteq v} \ frac {\ sum_ {e \ in \ mathcal {e}}} {f_e（| e \ cap s |）}}} {| s |} $。我们证明，当所有边缘权重功能都不应对凸面时，可以通过基于线性程序的算法，基于网络的基于网络的基于网络的算法和贪婪$ \ frac {1} {1} {r} $ - 近似算法 - $ r $等级的gdsh在多项式时间内求解GDSH。最后，我们研究了某些边缘重量函数是非convex的GDSH的计算障碍性。
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_{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.
