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

3004 软件学报 2024 年第 35 卷第 6 期

1. while ∃u ∈V , degree(u) ≥ 1 do
2. if 对超点 u 可应用精确剪枝 then
3. 对超点 u 应用精确剪枝
4. else
5. 对超点 u 应用近似剪枝
6. return 所有剩余超点组成最大独立集
在算法 2 超图独立集剪枝框架中, 首先需要输入原始超图和若干精确剪枝和近似剪枝策略. 然后不断枚举超
图 G 中的超点, 可采用精确剪枝时, 优先使用精确剪枝; 精确剪枝不能使用时, 采用近似剪枝. 近似剪枝后, 可能又
会出现可应用近似剪枝的条件. 这样近似剪枝与精确剪枝相结合, 直到最后精确剪枝和近似剪枝都不能在应用, 此
时所有剩余的超点的度都不大于 1. 则所有剩余的超点可以组成一个近似的最大超图独立集.
下面本文结合超图的特性和本文中超图最大独立集的定义, 提出以下几种剪枝策略.
● 剪枝 1. one-degree 点精确剪枝. 对于原始超图 G 中的所有的度为 1 的超点 u, 删除超点 u 及其所在的整条
边 e 后, 原图 G 中的最大独立集的大小减少 1. 即∀u∈V, 若 degree(u)=1, 而且 u∈e, |α(G\e)|=|α(G)−1|. 换个角度说,
即可将超点 u 加入最大独立集中, 然后删掉超点 u 所在的超边 e, 此时, 假设 G\e 中的最大独立集为 S′, 则原图 G
一定存在一个最大独立集为 S′∪{u}.
one-degree 点剪枝的具体情况由图 4 所示, 图中绿色超点为 one-degree 超点. 若在该图上应用剪枝 1, 则可将
绿色超点直接加入最大独立集中, 同时删除绿色超点所在超边及边上所有点.

图 4 one-degree 点剪枝
中, 如果一个高度超点
证明: (1) 证明选择 one-degree 超点 u 加入最大独立集不会改变最大独立集大小.
假设 G′=G\e, α(G\e) 为图 G′上的最大独立集大小. 由于 one-degree 点只存在于超边 e 中, 则∀v∈α(Ge), 超点 u
和超点 v 不能共同存在于同一超边, 则由性质 1, 一条超边最多能有一个超点加入最大独立集, 可得 α(Ge)∪{u}为
原图 G 的一个最大独立集.
(2) 证明选择 one-degree 超点 u 加入最大独立集不差于选择超边 e 中的其他点.
对于 v∈e, u≠v, 有两种情况, 即 degree(v)=1 或 degree(v)≥1.
① 若 degree(v)=1, 则超点 v 和超点 u 一样都是 one-degree 超点, 本质上将超点 v 和超点 u 中的任意一个超点
加入最大独立集都是可以的, 因此选择超点 u 加入最大独立集和选择超点 v 加入最大独立集一样好.
② 若 degree(v)>1, 超点 v 与其他超边还有邻接关系, 则由性质 2, 选择超点 u 加入最大独立集一定不比选择超
点 v 加入最大独立集差.
● 剪枝 2. high-degree 近似点剪枝. 在图 G u (degree(u)>1) 的 degree(u) 条邻接边都不是
只包含 u, 则可删掉超点 u. 高度超点的删除次序应为所有超点 degree 值降序.
high-degree 近似点剪枝的具体过程如图 5 所示, 图中绿色超点为 high-degree 超点. 若在该图上应用剪枝 2, 则
可将绿色超点直接删除, 同时遍历绿色超点的所有邻接边, 所有超边的 size 大小减 1.
证明: high-degree 近似点剪枝这种不精确的剪枝规则是基于高度的超点不太可能在一个最大独立集中的直觉
设计的; 例如, 如果一个高度的超点被加入独立集合中, 那么它所有的邻接点就会失去加入超图最大独立集机会.
此外, 对于一个不能应用其他精确剪枝的图, 通常在删除一个或几个高度的超点后, 可以重新应用其他精确剪枝规则.
对于两个 high-degree 超点, 在使用 high-degree 近似点剪枝时应优先删掉其中度数更高的超点, 因为高度超点