如何从图中删除派系无法覆盖的顶点？

Question

给定一个图 G = (V, E)、V 中的一组顶点 V* 和一个整数 k，我们如何从 G 中删除顶点，使得剩余的顶点要么在 V* 中，要么在大小为 clique 中k 在 V* 中至少有一个顶点？

这是一个玩具示例和解决方案：

图形 G = (V, E) 如下所示。带有白色“x”的顶点位于 V* 中。 k = 3。浅橙色的顶点是应该从 G 中删除的顶点。

我尝试为 V* 中的每个顶点找到一个派系，跟踪这些派系覆盖的顶点，然后删除图中未被派系覆盖的顶点。

但是，当图很大时，为每个顶点找到一个派系需要很长时间，我想知道是否有一种更简单的方法来修剪不属于任何派系的顶点。

Answer 1

为每个顶点找到一个派系需要很长时间

因此，仅在满足所有其他条件时才调用派系发现：

- LOOP W over vertices
   - IF W in V*
        - CONTINUE LOOP W
   - BFS from W, visiting X
        - IF X in V*
            - FIND clique containing W
            - If clique size != k
                - MARK W to_be_deleted
- END LOOP W
- DELETE vertices marked to_be_deleted
           

Answer 2

我将使用 I(S1, S2) 来表示两个集合的交集。

令 W = V \ V*（集合减法）。

For every vertex w in W
  For every vertex v in I(N(W), V*)
    There is no solution for v & w if |I(N(w), N(v))| < k-2
    Otherwise, search for a clique of size k-2 in that intersection. Two good heuristics for this (if you can use a heuristic) are 'Tabu search' and 'Iterated Greedy' 
    If you find a clique of size k-2, you're done with w as well as with any other vertices of your clique not in V*. Remove those from your queue of vertices to process.
   

如果你走这条路，我有 Rust 代码，它实现了迭代贪婪方法来寻找我很乐意分享的派系。高级描述是，对于具有 n 个节点的图 G，我们以随机顺序从其自己的团中的每个节点开始。

• 贪婪：然后我们将每个节点与它可以合并的最左边的节点贪婪地合并并保留团属性。如果没有，它是独立的，未来的节点可以与它合并。
• 迭代：我们打乱我们的派系，将它们转换回顶点（但因此同一派系的所有顶点都是相邻的；在派系内，顺序并不重要），然后重复该过程。

请注意，派系总数永远不会增加。在实践中（无论如何在我的用例中）它经常会减少。

为了探索特定的顶点或一对顶点（不是我的用例），您可能会通过强制它们或它们的包含派系始终位于最左边而受益，因此贪婪步骤总是首先尝试合并到其中。

如果你没有找到你想要的规模的小团体，你需要决定何时停止。这可能是许多步骤，但包含您正在寻找的顶点的团的大小没有任何改善。

这种方法可以受益于模拟退火。顶点的初始排序可能会导致您尝试围绕其建立派系的一对顶点没有解决方案。当您在没有解决方案的情况下停止时，您可以尝试随机化数组中其他顶点的顺序并重试任意次数。