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

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

被删除后, 会影响其相邻的超边, 进而影响其相关的超点. 在这一过程中, 还可能较低度超点的邻接边的关系发生
变化, 无需再使用 high-degree 近似点剪枝.

图 5 high-degree 点剪枝

● 剪枝 3. one-size 边精确剪枝 a. 在图 G 中, 如果一个高度的超点 u(degree(u)>1) 的 degree(u) 条邻接边中, 一
部分只包含超点 u, 一部分不是只包含超点 u, 则删掉超点 u 的只包含超点 u 的邻接超边, 图 G 的最大独立集大小
不变.
one-size 边精确剪枝 a 的具体过程由图 6 所示, 图中绿色超点为 high-degree 超点, 该点的 degree 为 3. 该点的
图 7 one-size 边剪枝
3 条邻接超边中有两条超边不是只包含绿色超点, 有一条超边只包含绿色超点, 这条边的 size 为 1. 若在该图上应
用剪枝 3, 则可直接删除这条 size 为 1 的超边.

图 6 one-size 边剪枝 a

证明: one-size 的超边只包含一个超点 u, 他并没有提供与超点 u 相关的邻接信息. 删掉超点 u 的只包含 u 的
部分邻接边并没有影响点 u 和图 G 中其他超点的邻接关系, 所以对原图的最大独立集大小没有影响.
● 剪枝 4. one-size 边精确剪枝 b. 在图 G 中, 如果一个高度的超点 u(degree(u)>1) 的 degree(u) 条邻接边都是
只包含超点 u, 则删掉超点 u 的任意 degree(u)–1 条邻接边, 图 G 的最大独立集大小不变.
one-size 边精确剪枝 b 的具体过程由图 7 所示, 图中绿色超点为 high-degree 超点. 该点的 3 条邻接超边都只
包含绿色超点一个点, 他们的 size 均为 1. 若在该图上应用剪枝 4, 则可删除其中的两条超边.

b

证明: 删掉点 u 的只包含 u 的邻接边并没有影响点 u 和图 G 中其他点的邻接关系, 所以对原图的最大独立集
大小没有影响. 然而需要注意的一点是, 不能删除所有 size 为 1 的超边. 因为, 若删掉所有 size 为 1 的超边, 超点 u
也会被删除.
综合 4 种剪枝策略, 下面提出一种改进的超图独立集算法, 即算法 3. 算法第 3–6 行遍历所有度为 1 的超点,
通过遍历 1 度点的邻接边, 删除邻接边上的所有超点, 将遍历到的度为 1 的超点加入超图独立集 H. 之后按超点度
数从高到低访问所有超点, 对于遍历到的一个超点 v, 如算法 3 的第 9–11 行所示, 若他的所有邻接边的 size 都为
1, 则所有邻接超边都只包含超点 v 这一个超点, 则可应用 one-size 边精确剪枝 b, 删除 N v 中的所有超边, 但注意要