Page 427 - 《软件学报》2024年第6期

徐兰天 等: 面向超图数据的最大独立集算法 3003

6. for u ∈ N v do //标记 ∼ IS 超点
7. if State[v] = INITIAL then
8. State[v] =∼ IS
9. return 所有状态为 IS 的超点
首先遍历图 G 的所有超点 v, 为所有的超点赋予一个状态值 State[v]. 初始时, 所有的超点的状态都为
INITIAL. 然后遍历超图 G 中的所有超点, 若当前访问的超点 u 的状态为 INITIAL, 则将当前被访问超点 u 的状态
置为 IS, 同时遍历超点 u 的所有的邻接超边中包含的所有超点, 如果这些点状态为 INITIAL, 则将其置为~IS. 重复
本操作, 直到超图 G 中的所有超点的状态都不为 INITIAL, 此时输出所有状态为 IS 的超点, 即为算法搜索到的一
个近似的超图最大独立集.
算法完成后的所有的点的状态都为 IS 或~IS. 对于所有状态为 IS 的点, 每一轮循环中被置为 IS 的点都不会与
在他之前就已被置为 IS 的点有共同的超边. 因为如果存在这样的超点, 则该超点被枚举为 IS 时, 他的邻接超点已
被置为 IS, 失去了再被置为 IS 的机会. 因此算法结束后所有的 IS 状态的点一定是一个超团独立集. 对于所有状态
的遍历顺序不同导致的, 一种好的遍历次序可以让算法
为~IS 的点, 每一个~IS 状态的点, 至少存在一个与他相邻的点已被置为 IS, 否则这个点就不会被置为~IS. 则此
时~IS 状态的点都不能再加入当前所有 IS 状态的点组成的超图独立集.
然而, 这种贪心的搜索策略可能在一些情况下将非最优的超点加入独立集. 如图 3 所示, 原图中共有 4 个点,
且 4 个点的度都为 3. 按照算法 1 枚举图中所有超点, 假如从超点 1 开始枚举, 则超点 1 的状态先被置为 IS, 此时
搜索超点 1 的所有邻居超点, 即 2, 3, 4 这 3 个超点. 将 3 个超点的状态都置为~IS, 此时图中所有点的状态已经都
不为 INITIAL, 则可输出本次超图最大独立集搜索结果, 即{1}.

1 2

3 4

图 3 基础算法的异常示例

可是, 如若改换算法 1 第 3 行的超点遍历顺序, 首先遍历超点 2. 则超点 2 的状态先被置为 IS, 此时搜索超点
2 的所有邻居超点, 即 1, 4 两个超点, 则将这两个超点的状态都置为~IS. 此时超点 3 的状态仍为 INITIAL, 则第 2
次循环遍历超点 3, 搜索超点 3 的所有邻居超点, 即 1, 4 两个超点. 但超点 1, 4 的状态在上一轮循环中都已被
置~IS, 则本轮不再有 INITIAL 状态的超点, 则循环直接结束. 此时可输出本次超图最大独立集搜索结果, 即{2, 3}.
显然第 2 次执行算法搜索到的独立集的大小大于第 1 次搜索到的独立集的大小. 这主要是因为算法 1 中超点
1 找到更接近于真实结果的超图最大独立集.
6 超图最大独立集的改进算法

本节中, 本文改进了 2-uniform 图上的剪枝方式 [37] , 提出了超图近似最大独立集的搜索框架, 3 种精确剪枝和
一种近似剪枝策略. 如算法 2 所示, 给出了超图近似最大独立集的搜索框架.

算法 2. 超图独立集剪枝框架.
输入: 超图 G 以及若干精确和近似剪枝;
输出: 超图 G 的最大独立集.