有界度图中K_{i,j}子图检测的高效优化方案问询

我正在处理最大度数受常数d约束的无向图G，目标是检测G中是否存在完全二部子图K_{i,j}（其中i、j均小于8）。目前采用的暴力检测代码如下：

nodes = [u for u in self.g if len(self.g[u]) >= j]
set_combinations = combinations(nodes, i)
for A in set_combinations:
  common_neighbors = set(self.g)
  for u in A:
    common_neighbors &= self.g[u]
    if len(common_neighbors) >= j:
      return False # K_ij found
  return True

该方法虽能正确检测，但随图规模增大运行速度变慢，主要瓶颈为：

• 枚举所有i节点子集，复杂度为O(n^i)；
• 迭代求邻居集合交集，在大图中成本较高。

鉴于图的最大度数有界且i、j取值较小，想了解是否存在更高效的检测方法。

结合图的最大度数d为常数、i和j均小于8的特点，可以从以下几个方向优化：

1. 调整枚举策略，减少子集数量 #

• 优先枚举较小的一侧：如果i > j，换成枚举j个节点的子集，再检查它们是否有至少i个共同邻居。因为子集数量C(n, k)随k增大快速增长，选更小的k能大幅减少枚举量。
• 基于邻居的局部枚举：不要全局枚举所有i节点子集，而是遍历每个节点u，从u的邻居中选取i-1个节点组成i元子集。这样子集的共同邻居必然是u的邻居的子集，范围更小，且枚举量变为O(n*d^{{i-1})——由于d是常数，i<8，这个复杂度远低于O(n}i)。

2. 优化共同邻居计算效率 #

• 位掩码替代集合：将每个节点的邻居集合编码为位掩码（比如Python的int或bitarray），集合交集操作直接转为位与运算，速度比普通集合操作快数倍。计算完位掩码后，统计其中1的个数即可判断是否≥j。
• 提前剪枝+初始集优化：计算多个节点的共同邻居时，先取邻居数量最少的节点的邻居集合作为初始交集，每一步交集后立即检查大小，若小于j则直接终止后续计算，避免无用操作。
• 双指针法求交集：若邻居列表是有序的，用双指针法求多个列表的交集，时间复杂度为O(d)（d为最大度数），常数远低于集合操作。

3. 利用度数约束直接剪枝 #

因为图的最大度数为d，可直接做以下剪枝：

• 如果d < j，直接判定不存在K_{i,j}——因为单个节点的邻居数最多是d，i个节点的共同邻居数不可能超过d，自然达不到j的要求。
• 筛选候选节点时，只保留邻居数≥min(i,j)的节点，不符合条件的直接排除，进一步缩小枚举范围。

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