密集子图

在图论和计算机科学中，密集子图是一个具有高度内部连接性的子图。其形式如下：让G=(V,E)是一个无向图，让S=(VS,ES)是G的一个子图，那么S的密度定义为最密集子图问题是指寻找一个密度最 大的子图。

1984年，AndrewV.Goldberg开发了一种多项式时间算法，使用最 大流技术寻找最 大密度子图。Gallo,Grigoriadis和Tarjan在1989年对这一算法进行了改进，以O(nmlog(n2/m))时间运行。Charikar在2000年给出了一个寻找最优解的简单LP。

关于最密集子图问题有许多变种。其中一个是最密集k子图问题，其目标是在正好k个顶点上找到最 大密度子图。

这个问题概括了Clique问题，因此在一般图中是NP-hard。存在一种多项式算法，可以在以下比率内接近最密集k子图该问题在双位图和弦状图中仍然是NP-hard，但在树和分裂图中是多项式的。

该问题在（适当的）区间图和平面图中是NP-hard还是多项式还没有定论；然而，该问题的一个变体，即要求子图是连接的，在平面图中是NP-hard。

最密集的k子图的目标是k{displaystylek}的目标是找到密度最 大的子图。问题的目标是在最 多k个子图上找到最 大密度的子图。

k{displaystylek}顶点上的最 大密度子图。顶点上的最 大密度子图。安德森和切拉皮拉表明，如果存在一个α{displaystyle{alpha}的近似，那么这个问题就会有一个α{displaystyle{alpha}的近似。-的近似值，那么这将导致一个Θ(α2){displaystyle{Theta(alpha{2})}对这个问题的近似值将导致一个Θ(α2)-的近似值为最密集的k{displaystylek}子图的问题。

最密集的k个子图最密集的k{fnTahomafs10bord0shad01cH00FFFF}{displaystylek}.问题的定义类似于最密集的k{displaystylek}子图的定义相似。

子图问题。这个问题是NP-完全的，但是可以在多项式时间内进行2次近似。此外，有证据表明这种近似算法基本上是xxx的：假设小集扩展假设（一种与唯 一游戏猜想密切相关的计算复杂性假设），那么将该问题近似到以下范围是NP难点(2-ϵ){displaystyle(2-epsilon)}对于每一个常数，都是NP-hard的。的系数，对于每个常数ϵ>0{displaystyleepsilon>0}。

K-clique最密集子图CharalamposTsourakakis提出了k{displaystylek}。-的最密集子图问题。这个最密集子图问题的变体旨在使诱导的平均数最大化。这种泛化提供了一种经验上成功的多时间方法，用于从大规模的真实世界网络中提取大的近似片段。

Qin等人提出了发现图中最密集子图的问题，每个子图在图中的局部区域达到最高密度：它既不包含在任何具有相同或更大密度的超级图中，也不包含密度与本地最密集子图的其余部分松散连接的子图。

请注意，最密集子图问题是作为以下情况的一个特例得到的k=1{displaystylek=1}。图中局部最密集子图的集合可以在多项式时间内计算出来。