给定图G、V*与k，如何移除不符合指定团覆盖要求的顶点？

核心目标 #

保留以下两类顶点：

1. 属于顶点集V*的顶点
2. 属于大小为k且至少含一个V*顶点的团的非V*顶点
   快速剔除不符合上述条件的顶点，避免全图枚举团的高耗时问题。

分步优化方案 #

1. 先锁定必留顶点

• 直接标记所有V*顶点为「保留」，这些是核心锚点，无需后续验证。

2. 快速排除不可能的顶点

对每个非V*顶点v，先做两轮快速筛除：

• 第一轮：如果v的总邻居数 < k-1 → 直接标记「移除」。因为团要求顶点两两相连，v至少需要k-1个邻居才能凑出k个顶点的团。
• 第二轮：如果v的邻居中没有任何V顶点 → 直接标记「移除」。这类顶点所在的团不可能包含V成员，完全不符合要求。

3. 轻量化验证候选顶点

对经过两轮筛选后剩下的非V顶点v（满足：邻居含至少一个V，且总邻居数≥k-1），不用枚举所有团，只做针对性验证：

• 遍历v的V*邻居u，计算v和u的共同邻居集合S（即同时与v、u相连的顶点）。
• 若 |S| + 2 ≥ k（2是指v和u本身），说明存在一个包含u、v，再从S中选k-2个顶点的合法团，直接标记v为「保留」，停止对该v的后续验证。

4. 批量移除冗余顶点

最后把所有未标记为「保留」的顶点统一移除，剩下的就是符合要求的顶点集合。

额外优化技巧 #

• 用邻接表/邻接矩阵存储图结构，方便快速查询邻居和计算共同邻居。如果顶点用整数编号，还可以用位运算加速交集计算（比如用二进制位表示邻居集合，按位与后统计1的个数就是共同邻居数）。
• 可以从V*顶点出发，先把它们的所有邻居纳入候选池，再筛选，避免遍历全图所有顶点，进一步节省时间。

内容的提问来源于stack exchange，提问作者thunderbird30