论文标题
计算图的K量最高子图
Computing the k Densest Subgraphs of a Graph
论文作者
论文摘要
计算粘性子图是图理论中的一个核心问题。虽然许多凝聚性子图的表述导致了NP-硬质问题，但在多项式时间内可以完成找到最密集的子图。因此，最密集的子图模型已成为最流行的凝聚力概念。最近，数据挖掘社区已经开始研究给定图中计算k密集子图的问题，而不是一个，对子图之间可能重叠的各种限制。但是，从理论的角度来看，这一重要和自然的概括似乎鲜为人知。在本文中，我们希望通过分析k个最巨型子图问题的三种自然变体来解决这种情况。每个变体都取决于子图之间允许的重叠量。在一个极端情况下，当不允许重叠时，我们证明问题是k> = 3的np-hard。在另一个极端情况下，当允许重叠而无需任何限制时重叠，而解决方案子图只需区别，我们表明，该问题是固定参数相对于k的固定参数拖拉，并且承认常数k的ptas。最后，当子图之间允许有限的重叠限制时，我们证明问题是k = 2的np-hard。
Computing cohesive subgraphs is a central problem in graph theory. While many formulations of cohesive subgraphs lead to NP-hard problems, finding a densest subgraph can be done in polynomial time. As such, the densest subgraph model has emerged as the most popular notion of cohesiveness. Recently, the data mining community has started looking into the problem of computing k densest subgraphs in a given graph, rather than one, with various restrictions on the possible overlap between the subgraphs. However, there seems to be very little known on this important and natural generalization from a theoretical perspective. In this paper we hope to remedy this situation by analyzing three natural variants of the k densest subgraphs problem. Each variant differs depending on the amount of overlap that is allowed between the subgraphs. In one extreme, when no overlap is allowed, we prove that the problem is NP-hard for k >= 3. On the other extreme, when overlap is allowed without any restrictions and the solution subgraphs only have to be distinct, we show that the problem is fixed-parameter tractable with respect to k, and admits a PTAS for constant k. Finally, when a limited of overlap is allowed between the subgraphs, we prove that the problem is NP-hard for k = 2.
