奖励-收集顶点覆盖问题的精确算法

曾宾 宁爱兵 付振星 徐江盼 张惠珍

摘  要： 奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题，同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明，利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中，从而降低该问题的规模；基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法，通过降阶子算法可以降低该问题的规模，从而缩短回溯子算法的搜索时间，进而降低求解该问题最优解的时间。通过应用和算法对比表明，所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。

关键词： 奖励-收集顶点覆盖； 上下界子算法； 降阶子算法； 回溯子算法

中图分类号：O223          文献标识码：A     文章编号：1006-8228（2023）05-51-06

Exact algorithm for the prize-collecting vertex covering problem

Zeng Bin， Ning Aibing， Fu Zhenxing， Xu Jiangpan， Zhang Huizhen

（Business School， University of Shanghai for Science and Technology， Shanghai 200093， China）

Abstract： The prize-collecting vertex covering problem is not only a derivative of the vertex covering problem， but also a problem for NP-hard combinatorial optimization. In this paper， we firstly propose the mathematical properties of the problem and give the proof， which can determine that some vertices must or must not be in the optimal prize collection vertex covering set， so as to reduce the scale of the problem. Secondly， based on the mathematical properties of the problem， we design the upper and lower bound sub-algorithm， reduced-order sub-algorithm and backtracking sub-algorithm. Through the reduced-order sub-algorithm， the scale of the problem can be reduced， so as to shorten the search time of the backtracking sub-algorithm， and then reduce the time to solve the optimal solution of the problem. A comparison of applications and algorithms shows that the designed algorithm has lower time complexity than the general accurate algorithms without considering the mathematical properties of the problem.

Key words： prize-collecting vertex cover; upper and lower bound sub-algorithm; reduced-order sub-algorithm; backtracking sub-algorithm

0 引言

奖励-收集，是Balas[1]在研究旅行商问题时首次提出，寻找低成本、低惩罚的服务方式就是奖励-收集所关注的问题。奖励-收集顶点覆盖问题（thePrize-Collecting Vertex Cover Problem， PCVC）是顶点覆盖问题（the Vertex Cover Problem， VC）的衍生问题。在实际商业活动中，为了避免超出预算必须追求成本费用与惩罚费用之和最小化。因此，PCVC问题相比于其他顶点覆盖问题更加切合实际的应用。

目前，求解PCVC问题的算法主要有三类。第一类是使用分支限界的传统精确算法求解PCVC问题，此类方法类似于求解VC问题[3]。此类算法可求得该问题的最优解，但求解速度缓慢。第二类主要是近似算法，如林俊峰[4]等将PCVC问题转化为对偶问题，利用迭代松弛方法设计出该问题的一个2-近似算法；郭金双[5]受Konemann[6]等人求解奖励-收集顶点集合覆盖问题的f-LMP算法的启发设计出2-LMP算法来求解该问题；Levn[7]等给出求解这类部分顶点覆盖问题的贪心算法。此类算法虽然在求解速度快于传统精确算法，但无法求到该问题的最优解。第三类是启发式算法，采用启发式算法来求解PCVC的文献极少，用启发式算法来求解最小权顶点覆盖问题文獻较多，如王辰尹[8]利用遗传算法求解模糊环境下的最小权顶点覆盖问题。从理论上来看，启发式算法同样可以用来求解PCVC问题。

1 奖励收集顶点覆盖问题的数学定义与性质

1.1 奖励-收集顶点覆盖问题定义

奖励收集顶点覆盖问题是指在给定简单无向赋权图G=（V，E），其中V为顶点集合，E为边集合，顶点vi的非负权值为c（vi），即顶点成本费用，边eij的非负权值为p（vi，vj）其中vi≠vj，即边惩罚费用，要求顶点子集S*[?]V，使得S*中所有顶点的成本费用之和加上未被S*中顶点覆盖的所有边上的惩罚费用之和最小。

1.2 数学符号

G：G=（V，E）为简单无向赋权图，V为顶点集，vi为V中的某顶点，vi∈V，E为边集，eij为E中的某边，eij∈E，c（vi）为顶点vi∈V的非负成本费用，p（vi，vj）为边eij=（vi，vj）∈E的非负惩罚费用；

n、m：图G的顶点数量；图G的边数量；

eij、c（vi）：顶点vi，vj的之间的边，eij=（vi，vj）∈E且vi≠vj；顶点vi成本费用，vi∈V；

p（vi，vj）：顶点vi，vj之间边eij的惩罚费用，eij =（vi，vj）∈E且vi≠vj；

G[F]：G=（VF，EF）由顶点子集F的导出子图G[F]，其中VF[?]V，EF[?]E；

N（G，vi）、N（G[F]，vi）：vi在图G、G[F]中的邻接顶点集，N（G，vi）={vi|（vi，vj）∈E}，N（G[F]，vi） ={vi|（vi，vj）∈EF}；

N[G，vi]、N[G[F]，vi]：N[G，vi]=N（G，vi）∪vi，N[G[F]，vi]=N（G[F]，vi）∪vi；

N（G，Vi）、N（G[F]，Vi）：顶点集Vi在图G、G[F]中的邻接顶点集的合集；

E（G，vi）、E（G[F]，vi）：vi在图G、G[F]中的邻边集，E（G，vi）={（vi，vj）|（vi，vj）∈E}、E（G[F]，vi）={（vi，vj）|（vi，vj）∈EF}；

P（G，vi）、P（G[F]，vi）：边集合在E（G，vi）、E（G[F]，vi）中所有边惩罚费用之和；

C（N（G，vi））、C（N（G[F]，vi））：顶点vi的在图G、G[F]中的所有邻接顶点的成本费用之和；

P0（Vj，vi）：vi的邻接边集中未被集合Vj中的顶点所覆盖的边惩罚费用之和；

E（G，Vi）、E（G[F]，Vi）：顶点集Vi在图G、G[F]中邻边集的合集；

d（G，vi）、d（G[F]，vi）：vi在图G、G[F]中度，即与vi邻接边的数量，d（G，vi）=|N（G，vi）|、d（G[F]，vi）=N（G[F]，vi）；

u、b：该问题的上界值，全局变量；子算法中的下界值，局部变量；

S、S*：当前最优奖励收集顶点覆盖集合，S[?]V；最优奖励收集顶点覆盖集合，即最优解，S*[?]V；

z：当前状态下的目标函数值，S中的顶点成本费用与未被S所覆盖边的惩罚费用之和；

z*：最优目标函数值，S*中的顶点成本费用与未被S*所覆盖边的惩罚费用之和；

V0，V1，V5;E0，E1，E5：分别为图G中通过数学性质判定一定不在、一定在、不确定是否在S*中的顶点集合，V5=V＼V1＼V0始终成立，初始化V0={}，V1={}，都为全局变量；分别为图G中通过数学性质判定一定被、一定不被、不确定是否被S*中的顶点所覆盖的边集合，都为全局变量；

VV0，VV1，VV5;EVV0， EVV1，EVV5：分别为G在执行子算法时假设不在、假设在、不确定是否在S*中的顶点集合，分别初始化为VV0={}，VV1={}，VV5=V＼V1＼V0＼VV1＼VV0始终成立，都为局部变量；分别为G在执行子算法时假设不被、假设被、不确定是否被S*中的顶点所覆盖的边集合，都为局部变量。

对某顶点vi而言：

⑴ 若通过数学性质判断得出vi∈V1，则更新V1=V1∪{vi}，V5=V5＼{vi}，此时E（G，vi）中所有的边都被覆盖，即E（G，vi）中所有的边都不被惩罚；

⑵ 若假设vi∈VV1，则更新VV1=VV1∪{vi}，VV5=VV5＼{vi}；

⑶ 若通过数学性质判断得出vi∈V0，则更新V0=V0∪{vi}，V5=V5＼{vi}；

⑷ 若假设vi∈VV0，则更新VV0=VV0∪{vi}，VV5=VV5＼{vi}。

1.3 数学性质及证明

性质1 对于d（G[VV5]，vi）=0的vi，分两种情况，情况⑴：VV1=VV0=?，此时若c（vi）>0，则vi∈V0；此时若c（vi）=0，则vi在V0或V1中都是最优解，本文都将其放在V0中；情况⑵：VV1、VV0不全为?，此时若c（vi）>0，则vi∈VV0；此时若c（vi）=0，则vi在VV0或VV1中都是最优解，本文都将其放在VV0中。

证明 情况⑴，当c（vi）>0时，vi在V0中会降低目标函数值，又因为VV1=VV0=?，则vi只能在V0中；当c（vi）=0时，无论vi在V0还是V1中，都不会影响目标函数值，又因为VV1=?和VV0=?，则此时vi∈V0中或vi∈V1中；情况⑵，同理可证。

性质2 对于d（G[VV5]，vi）=1的vi，其邻接顶点为vj，分两种情况，情况⑴：VV1=VV0=?，此时若c（vi）>0且vj∈V1，则vi∈V0；此时若c（vi）=0且vj∈V1，则vi在V0或V1中都是最優解，本文算法都将其放在V0中；情况⑵：VV1、VV0不全为?，此时若c（vi）>0且vj∈V1，则vi∈VV0；此时若c（vi）=0且vj∈V1，则vi在VV0或VV1中都是最优解，本文算法都将其放在VV0中。

证明 情况⑴，当c（vi）>0且vj∈V1时，vi在V0中会降低目标函数值，又因为VV1=VV0=?，则此时vi只能在V0中；当c（vi）=0且vj∈V1时，vi在V0或V1中都不会影响目标函数值，又因为VV1=VV0=?，则vi只能在V0中或V1中；情况⑵，同理可证。

性质3 对于d（G[VV5]，vi）=1的vi，其邻接顶点为vj，分两种情况，情况⑴：VV1=VV0=?，此时若p（vi，vj）c（vi），则vi∈V1；此时若vi∈V0且p（vi，vj）>c（vj），则vj∈V1；情况⑵：VV1、VV0不全为?，此时若p（vi，vj）c（vi），则vi∈VV1；此时若vi∈V0且p（vi，vj）>c（vj），则vj∈VV1。

证明 情况⑴，当p（vi，vj）c（vj）时，vi在V1中能降低目标函数值，又因为VV1=VV0=?，则vi只能在V1中；当vi∈V0且p（vi，vj）>c（vj）时，vj在V1中能降低目标函数值，又因为VV1=VV0=?，则vj只能在V1中；情况⑵，同理可证。

性质4 对于d（G[VV5]，vi）=2的vi，其邻接顶点为vk、vj，分两种情况，情况⑴：VV1=VV0=?，此时若c（vk）+c（vj）

证明 替代法证明，若vi在V1中，那么此时用vk或vj在V1中而vi在V0中，目标函数会更小，又因为VV1=VV0=?，则vj只能在V1中；那么当VV1、VV0不全为?时，则vj只能在VV1中。

性质5 对于图G[VV5]中的惩罚费用为+∞的eij，分两种情况，情况⑴：VV1=VV0=?，此时若vj∈V0且c（vi）≠+∞，则vi∈V1；情况⑵：VV1、VV0不全为?，此时若vj∈V0且c（vi）≠+∞，则vi∈VV1。

证明 因为eij的惩罚费用为+∞，则eij必须要覆盖，又因为VV1=VV0=?，则vi只能在V1中；那么当VV1、VV0不全为?时，则vj只能在VV1中。

性质6 在VV5中存在vi，设其邻接顶点集为N（G[VV5]，vi），分两种情况，情况⑴：VV1=VV0=?，若C（N（G[VV5]，vi））

证明 此时vi在V0中可以降低顶点的成本费用，从而使得目标函数值降低，又因为VV1=VV0=?，则vi只能在V0中；那么当VV1、VV0不全为?时，则vi只能在VV0中。

性质7 当vi满足P（G[VV5]，vi）

证明 当P（G[VV5]，vi）

性质8 对于d（G[VV5]，vi）=2的vi，设与其相连的vj，vk之间没有边，分两种情况，情况⑴：VV1=VV0=?，若c（vi）

证明 此时vi在V0中降低了顶点成本费用，从而使得目标函数值降低，又因为VV1=VV0=?，則vi只能在V0中；那么当VV1、VV0不全为?时，则vj只能在VV0中。

性质9 对于d（G[VV5]，vi）=2的vi，设与vi相连的顶点vj，vk之间有边ejk=（vj，vk），分两种情况，情况⑴：VV1=VV0=?，此时若p（vi，vj）+p（vi，vk）>c（vj）+c（vk）且c（vj）+c（vk）c（vj）+c（vk）且c（vj）+c（vk）

证明 此时vi在V0中降低了顶点成本费用，从而使得目标函数值降低，又因为VV1=VV0=?，则vi只能在V0中；那么当VV1、VV0不全为?时，则vj只能在VV0中。

性质10 若图G中所有vi满足c（vi）>P（G，vi），则该问题可在多项式时间内求解。

证明 此时最优奖励收集顶点集为空集，目标函数值为图中所有边惩罚费用之和。

性质11 若图G中所有eij满足p（vi，vj）>min{c（vi），c（vj）}，则该问题为最小权顶点覆盖问题。

证明 此时图中任意一边不覆盖所要花费的惩罚费用都比覆盖它所要花费的成本费用高，则图中所有边都要用顶点覆盖，又要追求成本费用最小，此时即为最小权顶点覆盖问题。

性质12 假设vi不在最优集合S*中时，若在这种情况下的下界大于上界，此时若|VV0|=|VV1|=0，则vi一定在最优集合S*中，vi此时也一定在V1中，此时若|VV0|≠0或|VV1|≠0，则vi一定在VV1中。

证明 假设vi不在S*中，此时下界大于上界且集合VV0与VV1为空，表明若顶点vi不在S*中是不可能求得最优解，则vi只能在S*中，自然也就在V1中；假设vi不在S*中，此时下界大于上界且集合VV0与VV1不为空，表明此时若vi不在VV1中是不可能求得比当前状态下更好的解，又因为vi是假设不在S*中，则vi只能在VV1中。

性质13 假设vi在最优集合S*中时，若在这种情况下的下界大于上界，此时若|VV0|=|VV1|=0，则vi一定不在最优集合S*中，vi此时也一定在V0中，此时若|VV0|≠0或|VV1|≠0，则vi一定在VV0中。

证明 证明同理性质12的证明，不再赘述。

2 算法设计与案例分析

2.1上界子算法

结合上文的数学性质设计一个上界子算法来寻找该问题的上界。设上界子算法所求出的顶点集合为Su，其所有顶点成本费用为Cu，即Cu=[vi∈sucvi]，设未被顶点集合Su中顶点所覆盖的边集合为Eu，其所有边惩罚费用为Pu，即Pu=[（vi， vj）∈Eup（vi，vj）]，则上界为u=Cu+Pu，上界子算法的具体步骤描述如下：

Step 1 初始化集合Su={}，Eu={}，u=0；

Step 2 依据上文的数学性质将一定在、不在S*中的顶点分别添加到V1、V0，执行Su=Su∪V1；

Step 3 将V5中每个顶点vi的邻接边中未被集合V1∪Su中顶点所覆盖的边的惩罚费用之和减去顶点vi的成本费用c（vi）的值计算出来，并设该值为αi，即αi=P0（V1∪Su， vi）-c（vi）；

Step 4 将V5＼Su中αi值大于0所对应的顶点vi添加到集合Su，再重新计算集合N（G，vi）＼（V1∪Su）中各顶点对应的αi值，直到集合V5＼Su为空集或集合V5＼Su中顶点vi 的最大αi值小于等于0为止，跳到Step 5；

Step 5 将未被集合V1∪Su中的顶点所覆盖的边都添加到Eu，并計算Eu所有边的惩罚费用之和Pu；

Step 6 计算上界u=Cu+Pu，输出集合Su与上界u，退出该子算法。

2.2 下界子算法

结合上文的数学性质设计一个下界子算法求该问题的初始下界，在回溯子算法中调用下界子算法求出当前状态下的下界，若在该状态下出现下界大于上界，则结束该状态下的搜索，形成剪枝，提高搜索效率。

Step 1 初始化b=0，集合Temp_0={}，Temp_1={}，Temp_2={}，Temp_V={}；

Step 2 根据上文中的数学性质将一定在、不在S*中的顶点分别添加到V1、V0，假设在S*中的顶点加到VV1，假设不在S*中的顶点加到VV0，执行VV5=V＼V1＼V0＼VV1＼VV0；

Step 3 由于V1∪VV1中的顶点一定在解中，则把V1∪VV1中顶点的成本费用累加得到累加和sum1，执行b=b+sum1；

Step 4 把图G中有两个顶点都在集合V0∪VV0中的边都放到集合Temp_0中，由于Temp_0中的边不可能被覆盖，因此把Temp_0中的每一条边的惩罚费用p（vi，vj）累加得到累加和sum 2，执行b=b+ sum 2；

Step 5 把图G中有0个顶点在集合V1∪VV1中且有0个顶点在V0∪VV0中的边都放到集合Temp_1中，把图G中有0个顶点在集合V1∪VV1中且有1个顶点在V0∪VV0中的边都放到集合Temp_2中；

Step 6 k=1；

Step 7 对于Temp_2中第k条边eij，设eij的顶点vi在V0∪VV0中，若vj?Temp_V，此时边eij可能被覆盖也可能不被覆盖，如果eij不被覆盖，则其惩罚费用为p（vi，vj），如果eij被覆盖，则至少需要付出的顶点成本为c（vj）；而这两种情况必然有一种情况发生，因此执行b=b+min{p（vi，vj），c（vj）}，Temp_V=Temp_V∪vj；若vj?Temp_V则不操作，因为此时的边eij可能被Temp_V中的顶点覆盖；

Step 8 k=k+1；若k≤|Temp_2|则跳到Step 7；

Step 9 k=1；

Step 10 对于Temp_1中第k条边eij，若vi?Temp_V且vj?Temp_V，此时eij可能被覆盖也可能不被覆盖，如果eij不被覆盖，则其惩罚费用为p（vi，vj），如果eij被覆盖，则至少需要付出的顶点成本为min{c（vi）， c（vj）}；而这两种情况必然有一种情况发生，因此执行b=b+min{p（vi，vj），c（vi），c（vj）}，Temp_V=Temp_V∪vi∪vj；若vi?Temp_V或vj?Temp_V则不操作，因为此时的eij可能被Temp_V中的顶点覆盖；

Step11 k=k+1；若k≤|Temp_1|则跳到Step 10；

算法结束后，b即为在V1，VV1，V0，VV0确定情况下的下界值。

2.3 降阶回溯算法

降阶子算法是利用数学性质来确定图中某些顶点在或不在S*中，从而降低问题规模。回溯子算法是从根节点出发，以深度优先的方式对VV5进行搜索。搜索到任意vi先计算当前下界b1，再判断下界b1是否小于等于上界，若不满足则进行剪枝；若满足则分两种情况：情况①假设顶点vi在S*中，对应搜索左子树；情况②假设顶点vi不在S*中，对应搜索右子树。

⑴ 降阶子算法具体步骤

Step 1 输入图G=（V， E），初始化V1={}，V0={}，V5=V，VV1={}，VV0={}，VV5={}，E1={}，E0={}，EVV0={}，EVV1={}，E5=E＼E＼E0，EVV5={}，S={}，S*={}，z=0，z*=+∞；

Step 2 若圖G满足性质10，则该问题多项式时间内可求得最优解，输出最优解S*={}，最优解对应的目标函数值为图中所有边惩罚费用之和，退出求解程序；否则跳到Step 2；

Step 3 根据性质1、2、3、4、6、7、5、8、9进行降阶；

Step 4 调用上、下界子算法，若u=b，则z*=u，结束算法；

Step 5 调用回溯子算法Backtrack（1）。

调用回溯子算法Backtrack（1）之前，令cur_i为当前搜索层数，对集合初始化：VV5=V5，VV1={}，VV0={}，EVV0={}，EVV1={}，EVV5=E＼E1＼E0，S={}，S*={}，z=0，z*=u；再将集合VV5中vi的邻接边集E（G，vi）中未被集合VV1∪V1中的顶点所覆盖边惩罚费用之和减去vi成本费用c（vi）的值βi计算出来，即βi=P0（VV1∪V1，vi）[-]c（vi），并按照βi的大小进行降序排列。

⑵ 回溯子算法Backtrack（cur_i）具体步骤

Step 1 若cur_i>|VV5| 或VV5={}，则搜索到叶节点，此时解为S=VV1∪V1，若z

Step 2 在VV5中找βi最大的vi，假设顶点vi在S*中，VV1=VV1∪{vi}，VV5 =VV5＼{vi}，调用下界子算法计算出当前情况下的下界b，若b≤u，则该状态下可能存在比S更优的解，调用Backtrack（cur_i+1）进入左子树进行搜索；若b>u，则当前情况下不存在最优解并剪枝，跳到Step 3；

Step 3 返回上一层前执行VV1=VV1＼{vi}，VV5=VV5∪{vi}；

Step 4 在VV5中找βi最大的vi，假设顶点vi不在S*中，VV0=VV0∪{vi}；VV5=VV5＼{vi}，调用下界子算法计算出当前情况下的下界b，若b≤u，则该状态下可能存在比S更优的解，调用Backtrack（cur_i+1）进入右子树进行搜索；若b>u，则当前情况下不存在最优解并剪枝，跳到Step 5；

Step 5 返回上一层前执行VV0=VV0＼{vi}，VV5=VV5∪{vi}。

算法结束后，S*即为该问题的最优解。

2.4 应用案例分析

如图1为A公司在某区域拟建快递配送点示意图，该公司计划拟建快递配送点最多n=11个，各配送点建设成本费用为图中顶点的权值，因某些原因无法拟建配送点所造成的惩罚费用为图中边权值。设计出以尽可能少的配送点来服务更多的客户其数学模型就是奖励-收集顶点覆盖问题。

案例的具体求解过程：

⑴ 初始化集合：V1={}，V0={}，V5=V，VV1={}，VV0={}，VV5={}，E1={}，E0={}，EVV0={}，EVV1={}，E5=E＼E＼E0，EVV5={}，S={}，S*={}，z=0，z*=+∞；

⑵ 调用降阶子算法得出V1={v1，v3，v9}，V0={v2，v5，v6，v8，v11}，V5=V＼V1＼V0，E1={（v3，v9}，E0={}，E5=E＼E1＼E0；

⑶ 计算上界：调用上界子算法计算出当前上界u1=15，此时Su={v1，v3，v4，v9，v10}；

⑷ 回溯部分：令VV5=V5，调用回溯子算法求解，如图2解空间所示，得出S*={v1，v3，v9，v10}。

由此，A公司应在上述⑷中S*的位置上拟建快递配送点所要的花费最小。

2.5 算法时间复杂度分析与对比

本文以图的顶点数n作为问题的规模，除回溯子算法外，其他子算法的时间复杂度都是多项式时间算法，因此仅需分析回溯子算法的时间复杂度。利用本文的数学性质对问题的规模进行降阶，在进入回溯子算法前，进一步压缩搜索空间。此外，进入回溯子算法后，在导出子图G[VV5]中以VV5中最大βi值所对应的顶点在或不在最优奖励收集顶点覆盖集合S*中进行分支。所以，该问题规模由n经过降阶子算法之后降低到k=|V5|≤n，因此，该算法最坏时间复杂度为O（2k）。

目前，求解该问题主要算法有启发式算法、近似算法、精确算法；本文的算法克服了启发式算法与近似算法在一般情况下不能得到问题的最优解的缺点；而传统精确算法虽然可以保证求得问题的最优解，但因未考虑该问题的数学性质，求解速度慢，其最坏时间复杂度为O（2n），高于本文提出的降阶回溯算法的最坏时间复杂度O（2k），其中k=|V5|≤n。比如用一般精确算法求解本文案例，其最坏时间复杂度为O（211），本文算法由于利用数学性质进行降阶与求解，求解案例的时间复杂度为O（23），其求解速度比一般精确算法快。

3 结束语

本文首先研究问题的数学性质，然后设计出上下界子算法、降阶子算法、回溯子算法。一般情况下，本文的降阶子算法可以降低问题的规模，进而降低该问题的时间复杂度。相比于近似算法和启发式算法，本文算法的优点是可以得到该问题的最优解，相较于传统精确算法，其优点是利用该问题的数学性质降阶从而使得时间复杂度更低。最后，本文所提出的数学性质不仅可以用于本文算法，还可与启发式算法等其他算法结合起来求解该问题，能够加快其他算法的求解速度。

参考文献（References）：

[1] Balas E. The prize collecting traveling salesman problem[J].Networks，1989，19（1）：621-626

[2] Karp R.M. Reducibility among combinatorial problem[J].Complexity of Computer Computations，1972，43（1）：85-103

[3] 王露芝.求解最小顶点覆盖问题的精确算法研究[D].硕士，东北师范大学，2020

[4] 杜俊峰，涂建华.奖励-收集顶点覆盖问题的一个2-近似算法[J].北京化工大学学报（自然科学版），2014，41（2）：120-123

[5] 郭金双.部分奖励-收集顶点覆盖问题的近似算法[D].硕士，河北师范大学，2021

[6] Konemann J， et al. A Unified Approach to ApproximatingPartial Covering Problems[J]. Algorithmica，2011，59（4）：489-509

[7] Levin A， Segev D. Partial multicuts in trees[J]. TheoreticalComputer Science，2006，369（1）：384-392

[8] 王辰尹，倪耀东，柯华.模糊环境下的最小权顶点覆盖问题[J].计算机应用研究，2012，29（1）：38-42