王利民 華景煜

摘要頂點(diǎn)覆蓋問題是經(jīng)典的NP完全問題，在排序、計(jì)算機(jī)網(wǎng)絡(luò)等現(xiàn)實(shí)生活中有許多的應(yīng)用.近幾年來，許多研究者開始探究它的推廣形式——頂點(diǎn)P_k覆蓋（VCPP_k）問題，即尋找一個(gè)頂點(diǎn)子集，從拓?fù)浣Y(jié)構(gòu)圖中刪除后使得剩下的頂點(diǎn)導(dǎo)出的子圖不包含P_k路，其中P_k是指包含k個(gè)頂點(diǎn)的路.本文簡(jiǎn)單介紹了VCPP_k問題的應(yīng)用背景，歸納了它在近似算法、精確算法、參數(shù)化算法3個(gè)方面的主要研究進(jìn)展，并分析了一些主要的方法和技巧.在此基礎(chǔ)上，對(duì)VCPP_k問題及其相關(guān)問題的研究前景進(jìn)行了展望.關(guān)鍵詞頂點(diǎn)P_k覆蓋；近似算法；精確算法；參數(shù)化算法

中圖分類號(hào)TP391.7

文獻(xiàn)標(biāo)志碼A

0 引言

頂點(diǎn)覆蓋問題是一個(gè)經(jīng)典的NP完全問題，它與團(tuán)問題、獨(dú)立集問題等可以互相轉(zhuǎn)換，在排序、計(jì)算機(jī)網(wǎng)絡(luò)等現(xiàn)實(shí)生活中有許多的應(yīng)用.近幾年來，許多研究者開始探究它的推廣形式——頂點(diǎn)P_k覆蓋（VCPk，k≥3）問題.這個(gè)問題是頂點(diǎn)刪除問題的一個(gè)特殊類型.頂點(diǎn)刪除問題就是尋找一個(gè)頂點(diǎn)子集，從拓?fù)鋱D中刪除這些頂點(diǎn)后，使得剩下的頂點(diǎn)導(dǎo)出的子圖滿足一個(gè)給定的特征.例如頂點(diǎn)P_k覆蓋問題，即尋找一個(gè)頂點(diǎn)子集，從拓?fù)浣Y(jié)構(gòu)圖中刪除這個(gè)子集后使得拓?fù)鋱D中剩下的頂點(diǎn)導(dǎo)出的子圖不包含Pk路，其中Pk是指包含k個(gè)頂點(diǎn)的路.

無(wú)線傳感器網(wǎng)絡(luò)是當(dāng)前信息領(lǐng)域中研究的熱點(diǎn)之一，可用于特殊環(huán)境的信號(hào)采集、處理和發(fā)送.無(wú)線傳感器網(wǎng)絡(luò)是一種全新的信息獲取和處理技術(shù)，作為一種無(wú)處不在的感知技術(shù)，無(wú)線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于軍事、環(huán)境、醫(yī)療、家庭和其他商用及工業(yè)領(lǐng)域.在空間探索和反恐、救災(zāi)等特殊的領(lǐng)域，傳感器技術(shù)和節(jié)點(diǎn)間的無(wú)線通信能力為無(wú)線傳感器網(wǎng)絡(luò)賦予了廣闊的應(yīng)用前景.

在無(wú)線傳感器網(wǎng)絡(luò)越來越廣泛的現(xiàn)實(shí)生活應(yīng)用中，人們主要關(guān)注的安全特性包括機(jī)密性、可靠性和數(shù)據(jù)的完整性等.由于傳感器自身的計(jì)算能力、電源儲(chǔ)備和處理信息的能力都有限，而且，它們通常部署在易受影響的區(qū)域，很容易被攻擊者攻擊或信息被竊取.傳統(tǒng)的安全協(xié)議不能直接應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)中，因此，就安全研究領(lǐng)域來說，如何設(shè)計(jì)無(wú)線傳感器網(wǎng)絡(luò)的安全協(xié)議成為一個(gè)很大的挑戰(zhàn).

許多學(xué)者在這方面進(jìn)行了大量探究，例如，在傳感器網(wǎng)絡(luò)中，為了確保數(shù)據(jù)的完整性或數(shù)據(jù)來源認(rèn)證，文獻(xiàn)[1]就設(shè)計(jì)了一個(gè)安全協(xié)議.為了確保數(shù)據(jù)的完整性，推廣的Canvas協(xié)議[2]提出在傳感器形成的通信圖中，對(duì)于每條長(zhǎng)度為k-1的路徑中至少要有一個(gè)頂點(diǎn)沒有被捕獲.因此，在傳感器網(wǎng)絡(luò)的部署和初始化期間，應(yīng)確保至少有一個(gè)受保護(hù)的頂點(diǎn)存在于每個(gè)長(zhǎng)度為k-1的路徑中.又由于傳感器之間需要傳遞信息，以及對(duì)傳感器加以保護(hù)是需要費(fèi)用的，為此在現(xiàn)實(shí)應(yīng)用時(shí)還需要考慮傳感器節(jié)點(diǎn)之間的連通性，以及合理設(shè)計(jì)安全協(xié)議盡量減少費(fèi)用.更多的實(shí)際應(yīng)用可以參考文獻(xiàn)[3].

一般圖上的權(quán)值最小VCPP_k問題和所含頂點(diǎn)數(shù)最少的VCPP_k問題都是NP完全問題.本文重點(diǎn)介紹VCPP_k問題的研究成果包括：無(wú)向圖、有向圖和特殊圖的VCPP_k問題和參數(shù)化VCPP_k問題的相關(guān)算法，同時(shí)根據(jù)已有成果介紹一些可以值得研究的方向.下面給出VCPP_k問題的一些相關(guān)定義.

圖G=（V，E）是一個(gè)含有n個(gè)頂點(diǎn)的圖，V是G的頂點(diǎn)集，E是邊集.

定義1（含頂點(diǎn)數(shù)最少的VCPP_k，簡(jiǎn)記MVCPk） 給定一個(gè)含有n個(gè)頂點(diǎn)的圖G，求一個(gè)含頂點(diǎn)數(shù)最少的VCPP_k.

定義2（權(quán)值最小的VCPP_k，簡(jiǎn)記MWVCPP_k） 給定一個(gè)頂點(diǎn)帶權(quán)的圖G，求一個(gè)權(quán)值最小的VCPP_k.

一般圖上的MVCPP_k和MWVCPP_k問題的前期研究主要集中在一些性質(zhì)、近似算法和精確算法，其中也包括頂點(diǎn)連通性，即使得求得的VCPP_k集導(dǎo)出的子圖是連通的.近幾年，許多學(xué)者開始關(guān)注VCPP_k問題的參數(shù)化，參數(shù)化VCPP_k問題的定義如下：

定義3（參數(shù)化不帶權(quán)的VCPP_k，簡(jiǎn)記PVCPk） 給定含有n個(gè)頂點(diǎn)的圖G和一個(gè)非負(fù)整數(shù)k，能否在圖中找到一個(gè)含頂點(diǎn)個(gè)數(shù)不超過k的VCPP_k.

如果一個(gè)參數(shù)化NP難問題在時(shí)間f（k）nO（1）內(nèi)可解，其中f（k）是僅關(guān)于k的一個(gè)函數(shù)，那么稱此問題是固定參數(shù)可解的（FixedParameter Tractable，簡(jiǎn)記FPT）[4].

本文第1節(jié)介紹無(wú)向圖中VCPP_k問題的研究現(xiàn)狀；第2節(jié)主要描述無(wú)向圖中PVCPP_k問題的研究現(xiàn)狀；第3節(jié)給出一些特殊圖中VCPP_k問題的研究現(xiàn)狀；第4節(jié)介紹有向圖中VCPP_k問題的研究現(xiàn)狀；最后通過分析和總結(jié)，給出VCPP_k問題研究中可以考慮的幾個(gè)方面.

1 無(wú)向圖中的VCPP_k問題

本節(jié)主要介紹無(wú)向圖中VCPP_k問題的研究現(xiàn)狀，主要包括近似算法、精確算法和MVCPP_k的上下界.

1.1 近似算法

由于VCPP_k問題是NP完全問題，除非P=NP，否則VCPP_k問題不可能有多項(xiàng)式時(shí)間算法，因此前期學(xué)者對(duì)最小VCPP_k問題的研究主要集中在多項(xiàng)式時(shí)間可解的近似算法.近似算法主要是在最壞的情況下找到問題的近似解與最優(yōu)解的比值；即算法的近似度.近似算法主要的衡量指標(biāo)之一就是近似度.下面主要分析MVCPP_k和MWVCPP_k問題的近似算法.對(duì)于MWVCPP_k問題，算法的近似度為近似解與最優(yōu)解的權(quán)值的比值，對(duì)于MVCPP_k問題，近似度為近似解與最優(yōu)解所含頂點(diǎn)數(shù)目的比值.

文獻(xiàn)[5]利用以某概率選擇頂點(diǎn)的方法得到MVCP3問題的一個(gè)近似比期望為2311的隨機(jī)算法.Tu等[67]利用原始對(duì)偶算法或分層技巧分別給出權(quán)值最小的VCP3問題的一個(gè)2因子近似解.文獻(xiàn)[6]通過在原圖上添加懸掛邊的方法，將權(quán)值最小的頂點(diǎn)覆蓋問題歸約到權(quán)值最小的VCP3問題，證明VCP3問題是NP難解的.

文獻(xiàn)[8]首先利用逐步刪除P_k的貪婪算法和添加頂點(diǎn)的方法給出了最小的連通VCPk問題的一個(gè)k2近似解，進(jìn)而結(jié)合平面的劃分和轉(zhuǎn)移策略給出這個(gè)問題在單位圓盤圖上的一個(gè)多項(xiàng)式時(shí)間近似格式的算法.這個(gè)算法的整體設(shè)計(jì)思路如下：首先，定義一個(gè)正方形區(qū)域使得這個(gè)區(qū)域包含圖中的所有單位圓盤，再將這個(gè)區(qū)域劃分成一些小的正方形.對(duì)每一個(gè)小正方形，定義它的中心區(qū)域和邊界區(qū)域.其次，對(duì)于單位圓盤圖，采用一個(gè)常因子的近似算法求得圖的一個(gè)連通的VCPk集，使得這個(gè)近似解中每個(gè)頂點(diǎn)的權(quán)值至多是c，這里c是一個(gè)正的常數(shù).然后，對(duì)于每個(gè)正方形的中心區(qū)域，枚舉所有的VCPP_k集，僅僅考慮滿足鄰域條件的解，進(jìn)而選擇頂點(diǎn)權(quán)和最小的一個(gè)解，將此解記作局部最優(yōu)解.通過對(duì)邊界區(qū)域的選擇，可以確保算法的輸出結(jié)果是一個(gè)連通的VCPP_k集.最后將常因子近似解落在某個(gè)劃分的邊界區(qū)域的頂點(diǎn)集合與局部最優(yōu)解合并.一般地，將正方形區(qū)域的左下角沿著45°角移位，每次移動(dòng)2個(gè)單位就得到一個(gè)新的劃分.其中采用轉(zhuǎn)移策略是為了選取一個(gè)劃分使得常因子近似解落在這個(gè)劃分的邊界區(qū)域的頂點(diǎn)集合的權(quán)和或頂點(diǎn)個(gè)數(shù)盡可能小，從而使得輸出結(jié)果與最優(yōu)解的比更小.而劃分策略或分治法主要是將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，各個(gè)擊破，分而治之，然后再利用這些子問題的解求出原問題的解.簡(jiǎn)言之，縮小問題規(guī)模，使子問題易求解.在假設(shè)圖的圍長(zhǎng)至少是k的條件下，Li等[9]利用深度優(yōu)先搜索法及逐步加點(diǎn)判斷的方法提高了最小的連通VCPk問題在一般圖上的近似比，即給出一個(gè)k近似解，其算法時(shí)間復(fù)雜度為O（n2）.

文獻(xiàn)[10]提出最小連通有界VCPP_k的概念，并在假設(shè)圖的度有界的條件下，利用增長(zhǎng)劃分的方法得到連通的VCPP_k問題在growthbounded圖上的一個(gè)多項(xiàng)式時(shí)間近似格式的算法，但是此時(shí)不需要利用常因子近似解.文獻(xiàn)[10]的主要思想是將圖劃分成一些聚類，然后對(duì)每一個(gè)聚類求局部解，進(jìn)而合并這些解得到最后結(jié)果.

在假設(shè)圖的最小度為2的情況下，Wang等[11]首先利用原始對(duì)偶算法和有關(guān)頂點(diǎn)加權(quán)的斯坦納樹的一個(gè)近似算法得到權(quán)值最小的連通VCP3問題的一個(gè)常因子近似解；其次利用文獻(xiàn)[12]給出的最小連通頂點(diǎn)覆蓋問題在單位圓盤圖上的多項(xiàng)式時(shí)間近似格式算法的思想，結(jié)合一個(gè)類似c局部問題[13]的概念（c是一個(gè)正的常數(shù)），再利用平面上的劃分和轉(zhuǎn)移策略，給出權(quán)值最小的連通VCP3問題在單位圓盤圖上的一個(gè)多項(xiàng)式時(shí)間近似格式的算法.

在現(xiàn)實(shí)世界中，為了觀察某些復(fù)雜的環(huán)境，例如高山上或水里[14]，一些傳感器就被放在不同的深度，這就形成了三維空間的網(wǎng)絡(luò)，它可以模擬的數(shù)學(xué)模型是單位球圖.根據(jù)平面上研究的一些結(jié)論和受到的啟發(fā)，Wang等[15]提出一個(gè)弱c局部問題的概念（c是一個(gè)正的常數(shù)），并在頂點(diǎn)權(quán)值的光滑性條件下，利用高維空間的劃分和轉(zhuǎn)移技巧，給出權(quán)和最小的連通VCP3問題在單位球圖上的一個(gè)多項(xiàng)式時(shí)間近似格式的算法.當(dāng)球的半徑不同時(shí)，上面的方法將不起作用.然而文獻(xiàn)[16]在球的最大半徑與最小半徑的比值有界的條件下，利用局部搜索的方法給出最小的VCPP_k問題在球圖上的一個(gè)多項(xiàng)式時(shí)間近似格式的算法.

注意到在處理連通的VCPP_k問題時(shí)，主要包含常因子的近似解、多項(xiàng)式時(shí)間近似格式的算法和特殊拓?fù)浣Y(jié)構(gòu)圖上的時(shí)間復(fù)雜度等3個(gè)方面.

對(duì)于求解常因子的近似解，一般地，先通過一些算法或技巧找到一個(gè)不連通的近似解，再結(jié)合求解斯坦納樹的算法或逐步添加頂點(diǎn)并判斷的方法，進(jìn)而得到連通的常因子近似解.或者，先利用深度優(yōu)先搜索法或其他搜索法得到拓?fù)浣Y(jié)構(gòu)的支撐樹，再對(duì)樹的每一分支判斷是否需要繼續(xù)添加頂點(diǎn)，從而得到所求的結(jié)果.因此，以后在求解連通的常因子近似解時(shí)就可以參考這2種方法.而設(shè)計(jì)多項(xiàng)式時(shí)間近似格式的算法，主要采取劃分策略和轉(zhuǎn)移策略，以及增長(zhǎng)劃分策略2種方式，當(dāng)圖中頂點(diǎn)的位置信息已知時(shí)大部分采取劃分和轉(zhuǎn)移策略，這是處理這類問題常用的技巧和方法.然而在更一般的圖上，如growthbounded圖上，不需要利用常因子近似解，只知道圖的部分信息，此時(shí)多采取增長(zhǎng)劃分.不管是那種劃分策略，為了達(dá)到連通都需要使劃分的小區(qū)域有重疊的部分，算法最關(guān)鍵的地方就是處理重疊部分.

1.2 精確算法

近似算法只能得到問題的近似解而無(wú)法得到精確解，甚至許多問題很難求得近似解.于是許多學(xué)者開展了對(duì)VCPP_k精確算法的研究.顯然，通過枚舉圖中n個(gè)頂點(diǎn)的2n個(gè)子集就可以找到最小的VCPP_k.

對(duì)于VCP3問題，文獻(xiàn)[5]利用分支定界法逐步減少圖的頂點(diǎn)個(gè)數(shù)，從而求得MVCP3，其算法時(shí)間復(fù)雜度為O（1.517 1n），其中n是圖G的頂點(diǎn)個(gè)數(shù).Chang等[17]利用加權(quán)分治技術(shù)提出一個(gè)分支化簡(jiǎn)的算法，算法提高了上面的時(shí)間復(fù)雜度，其復(fù)雜度為O（1.465 8n）.文獻(xiàn)[18]根據(jù)給出的一些有關(guān)分散集和VCP3結(jié)構(gòu)特征，利用更多的化簡(jiǎn)規(guī)則和分支規(guī)則，提出了時(shí)間復(fù)雜度為O（1.465 6n）的精確算法，此時(shí)需要多項(xiàng)式空間；進(jìn)一步利用動(dòng)態(tài)規(guī)劃技術(shù)改進(jìn)算法，其時(shí)間復(fù)雜度為O（1.365 9n），但是需要指數(shù)空間.

1.3 MVCPP_k的上下界

2 無(wú)向圖中的PVCPP_k問題

在實(shí)際應(yīng)用中，圖的結(jié)構(gòu)是比較復(fù)雜的且圖的頂點(diǎn)數(shù)n往往比較大，VCPP_k問題的所有精確算法都無(wú)法應(yīng)用于實(shí)際.但是在很多實(shí)際應(yīng)用中，VCPk的大小k比n小很多，而且有些應(yīng)用不一定要找最小的VCPP_k，而只要求小于某個(gè)值的VCPP_k，于是許多研究者考慮研究VCPP_k問題的參數(shù)化.下面開始介紹無(wú)向圖參數(shù)化VCPP_k問題的研究現(xiàn)狀.

文獻(xiàn)[4]采用迭代壓縮技術(shù)證明一般圖上的PVCP3問題是固定參數(shù)可解的，即對(duì)于固定的參數(shù)k，這個(gè)問題可以在時(shí)間O（2kk3.376+n4m）內(nèi)得到它的解，其中n是圖的頂點(diǎn)個(gè)數(shù)，m是圖的邊數(shù)，VCP3問題解的頂點(diǎn)個(gè)數(shù)至多是k.文獻(xiàn)[24]利用化簡(jiǎn)規(guī)則和分支搜索技術(shù)給出PVCP3問題的一個(gè)FPT算法，其時(shí)間復(fù)雜度為O（1.817 2knO（1））.Chang等[25]也利用化簡(jiǎn)規(guī)則和分支搜索技術(shù)在多項(xiàng)式空間和指數(shù)空間中分別說明PVCP3問題是固定參數(shù)可解的，算法所執(zhí)行完成的時(shí)間至多分別為O*（1.796 4k），O*（1.748 5k），這里O*的含義為：對(duì)于2個(gè)函數(shù)f和g，如果f（k，n）=O（g（k）·poly（n）），那么f（k，n）=O*（g（k）），其中poly（n）是n的多項(xiàng)式函數(shù).對(duì)于VCP4問題，Tu等[26]也利用迭代壓縮技術(shù)證明一般圖上的PVCP4問題是固定參數(shù)可解的，時(shí)間復(fù)雜度為O（3kn4）.

VCPP_k問題核心化是參數(shù)化VCPP_k問題的重要研究?jī)?nèi)容.如果在求解VCPP_k問題之前，利用核心化算法對(duì)問題規(guī)模進(jìn)行簡(jiǎn)化，將大大提高求解PVCPP_k的效率.對(duì)于VCP3問題，文獻(xiàn)[27]得到一個(gè)大小為15k的核，文獻(xiàn)[28]利用2次簡(jiǎn)化規(guī)則提高這個(gè)核到6k-6，Brause等[29]利用皇冠分解給出一個(gè)計(jì)算核的多項(xiàng)式時(shí)間的算法，通過算法得到圖的2個(gè)不交的集合T1，T2，滿足|T2|≤6·ψ3（G[T2]），其中T2為圖G的核，可以看出此處核的上界為6k.最近，通過改進(jìn)化簡(jiǎn)規(guī)則，文獻(xiàn)[30]將該問題的核大小提高到5k.

3 特殊圖中的VCPP_k問題

對(duì)于特殊圖上的VCPP_k問題，許多學(xué)者也進(jìn)行了大量的研究.某些特殊的應(yīng)用對(duì)應(yīng)一些在具有特殊性質(zhì)的圖上的VCPP_k問題，而特殊圖上的VCPP_k問題比一般圖上的VCPP_k問題更容易，使得在特定條件下解決VCPP_k問題顯得更有意義.本節(jié)簡(jiǎn)要闡述各類特殊圖中VCPP_k問題的研究現(xiàn)狀.

1） 三正則圖上的VCPP_k問題

三正則圖是指圖中所有頂點(diǎn)的度均為3的圖，也稱為立方圖.在三正則圖中，文獻(xiàn)[31]給出了一些有關(guān)VCP3問題的結(jié)論：首先，利用歸約證明在圍長(zhǎng)為3的三正則平面圖中，最小VCP3問題的判定問題是NP完全的；其次，令ψ3（G）表示圖G的最小VCP3集的頂點(diǎn)數(shù)，得出2n5≤ψ3（G）≤n2；最后，利用逐步刪除頂點(diǎn)度為3的頂點(diǎn)的貪婪算法，給出最小VCP3問題的一個(gè)近似度為1.57的近似算法.在三正則圖中，文獻(xiàn)[32]給出了一些有關(guān)VCP4問題的結(jié)論：首先，利用歸約證明最小VCP4問題的判定問題是NP完全的；其次，令ψ4（G）表示圖G的最小VCP4集的頂點(diǎn)數(shù)，得出n4≤ψ4（G）≤n2；最后，利用Lovasz分解，給出最小VCP4問題的一個(gè)近似度為2的近似算法.

2） 完全圖、路、圈、樹上的VCPP_k問題

文獻(xiàn)[33]從時(shí)間復(fù)雜度的角度考慮，在完全圖、路和圈上分別可以在O（n·k）、O（n·k）和O（n·k2）時(shí)間內(nèi)求出權(quán)值最小的VCPk問題的最優(yōu)解，而在樹上的時(shí)間和空間復(fù)雜度均為O（n·k）.文獻(xiàn)[9]采取逐步判斷樹的分支是否含有Pk的方法，得到在樹上可以在O（n2）時(shí)間內(nèi)求出最小連通的VCPk問題的最優(yōu)解.文獻(xiàn)[34]通過尋找最長(zhǎng)路以及逐步加點(diǎn)判斷的方法可以在O（n）時(shí)間內(nèi)找到權(quán)和最小的連通VCPk問題的最優(yōu)解；進(jìn)一步得到在包含唯一圈（圈的長(zhǎng)度為r）的圖上可以在O（nr）時(shí)間內(nèi)找到這個(gè)問題的最優(yōu)解.

3） 樹寬有界的圖的VCPP_k問題

在樹寬有界的圖中，文獻(xiàn)[35]設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法可以求得MVCP3，其時(shí)間復(fù)雜度為4p·nO（1），其中樹寬至多是p.文獻(xiàn)[36]不僅提高了求MVCP3問題的時(shí)間復(fù)雜度3p·nO（1），而且針對(duì)連通的VCP3問題給出一個(gè)時(shí)間復(fù)雜度為4p·nO（1）的隨機(jī)算法.

4 有向圖中的VCPP_k問題

眾多研究者探究VCPP_k的相關(guān)問題主要集中在無(wú)向的拓?fù)浣Y(jié)構(gòu)圖上，對(duì)有向圖的VCPP_k問題的研究進(jìn)展較為緩慢，主要是考慮方向后難度會(huì)更大.然而，近年來，文獻(xiàn)[3，37]分別從現(xiàn)實(shí)的生活環(huán)境和需求出發(fā)介紹了VCPP_k問題在有向圖環(huán)境中的一些應(yīng)用實(shí)例（圖1）.例如：人們?cè)谶h(yuǎn)足旅行時(shí)會(huì)通過一些網(wǎng)站查詢一下路線圖，網(wǎng)站會(huì)發(fā)送幾條建議遠(yuǎn)足路線，路線中的每個(gè)節(jié)點(diǎn)都標(biāo)記的話會(huì)浪費(fèi)很多帶寬，因此，可以考慮只發(fā)送幾個(gè)關(guān)鍵的節(jié)點(diǎn)信息，刪除重疊的部分，使得路線圖顯得更清晰，便于出行者選擇合適的路線.如圖1，有2條出行路線紅色s′→t和綠色s→t可供選擇，只需選用灰圓圈標(biāo)記的節(jié)點(diǎn)即可覆蓋整個(gè)圖（k=6時(shí)的情形）.在超大規(guī)模的圖中，文獻(xiàn)[3，37]均利用剪枝方法可以得到求極小的VCPP_k集的算法，并通過實(shí)驗(yàn)驗(yàn)證了其算法的有效性.

5 總結(jié)與展望

頂點(diǎn)覆蓋問題是一類重要的NP完全問題，在排序、計(jì)算機(jī)網(wǎng)絡(luò)等現(xiàn)實(shí)生活中有許多的應(yīng)用.近幾年來，人們開始關(guān)注它的推廣形式——VCPk （k≥3）問題.本文著重闡述無(wú)向圖中VCPP_k問題的研究現(xiàn)狀.從中可以看出，前期較多的研究關(guān)注點(diǎn)是VCPP_k問題的性質(zhì)和近似算法，而隨著參數(shù)計(jì)算理論的產(chǎn)生，推動(dòng)了VCPP_k問題的發(fā)展，使之成為目前階段的研究熱點(diǎn).

通過對(duì)VCPP_k問題研究現(xiàn)狀的總結(jié)和分析，可以使學(xué)者對(duì)VCPP_k問題有更全面的理解.當(dāng)然對(duì)于VCPP_k問題，依然還有許多方面有待于我們進(jìn)一步探究，主要可以從以下幾個(gè)角度進(jìn)行研究.

1）VCPP_k問題的算法研究

在一般圖上對(duì)于權(quán)和最小的連通VCPP_k問題尚未有常因子近似解，是否可以根據(jù)已有結(jié)果及問題的自身特征尋求新穎的算法去求解，進(jìn)而給出相應(yīng)問題的一個(gè)多項(xiàng)式時(shí)間近似格式算法呢？ 處理這個(gè)問題的難點(diǎn)是如何使其連通.

對(duì)于權(quán)和最小的連通VCP3問題，所求的近似解是在最小度為2的情況下得到的，那么是否可以通過尋求新算法將圖的最小度降為1？求解這個(gè)問題的多項(xiàng)式時(shí)間近似格式的算法時(shí)，有假設(shè)條件c局部或弱c局部以及頂點(diǎn)權(quán)值是光滑性的等，考慮到現(xiàn)實(shí)環(huán)境，不太實(shí)用，能否采用其他的方法將c局部等條件去掉？

2）VCPP_k問題的核心化

許多學(xué)者對(duì)無(wú)向圖上VCPP_k問題的核心化研究已取得了一些結(jié)果，通過一系列局部簡(jiǎn)化規(guī)則和對(duì)圖結(jié)構(gòu)的分析，對(duì)核大小不斷進(jìn)行改進(jìn).希望能夠通過深入分析已有結(jié)論和VCPP_k問題的結(jié)構(gòu)，構(gòu)造出更多的簡(jiǎn)化規(guī)則，從而提出更好的核心化算法.

3）VCPP_k問題的變形

近年來，一部分研究者探究VCPP_k問題的一個(gè)變體——k連通子圖覆蓋問題，即尋找一個(gè)頂點(diǎn)子集，從圖中刪除后使得圖中剩下的頂點(diǎn)導(dǎo)出的子圖不包含k個(gè)頂點(diǎn)導(dǎo)出的連通子圖.可以看出這個(gè)問題比VCPP_k問題更具有一般性.在這方面的主要結(jié)論有：在假設(shè)圖是連通的條件下，文獻(xiàn)[9]利用深度優(yōu)先搜索法、生成樹及逐步加點(diǎn)判斷的方法給出頂點(diǎn)連通的k連通子圖覆蓋問題的一個(gè)k近似算法.利用線性規(guī)劃舍入方法很容易得到權(quán)和最小的k連通子圖覆蓋問題的一個(gè)k近似解.然而在假設(shè)圖的圍長(zhǎng)至少是k的情況下，文獻(xiàn)[38]提高了這個(gè)問題的近似比，首先利用圖的拓?fù)浣Y(jié)構(gòu)，并結(jié)合頂點(diǎn)的度權(quán)函數(shù)給出一個(gè)近似比，其次，利用類似分層的方法又得到一個(gè)近似比，兩者均為k-1.除了這2種情況有以上結(jié)果外，頂點(diǎn)不連通、不加權(quán)和頂點(diǎn)連通以及加權(quán)等情況尚未有人探討，而且就現(xiàn)階段的研究現(xiàn)狀來看，對(duì)于有關(guān)k連通子圖覆蓋問題的多項(xiàng)式時(shí)間近似格式算法還沒有研究者去探索，這可能也是一個(gè)比較好的研究方向.

4）VCPP_k問題的隨機(jī)算法

隨機(jī)化是現(xiàn)代計(jì)算機(jī)科學(xué)最重要的方法之一，近幾十年來被廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域.在這些應(yīng)用的背后，是一些共通的隨機(jī)化原理.我們是否可以利用一些重要的隨機(jī)算法的設(shè)計(jì)思想和理論分析，借助一些概率論工具及其在算法分析中的應(yīng)用，從新的角度探索VCPP_k問題或k連通子圖覆蓋問題呢？

5） 特殊圖上的VCPP_k問題

根據(jù)一些特定的應(yīng)用，對(duì)于特殊圖上VCPP_k問題的研究也很有意義.本文列舉了一些特殊圖上的VCPP_k問題，可以對(duì)這些問題的算法做進(jìn)一步的研究，提出更有效的算法，或者對(duì)由實(shí)際應(yīng)用而轉(zhuǎn)化的特殊VCPP_k問題進(jìn)行研究.

參考文獻(xiàn)

References

[1] Menezes A J，Van Oorschot P C，Vanstone S A.Handbook of applied cryptography[M].Boca Raton：CRC Press，1996

[2] Novotny M.Design and analysis of a generalized canvas protocol[C]∥IFIP International Workshop on Information Security Theory and Practices，2010：106121

[3] Funke S，Nusser A，Storandt S.On kpath covers and their applications[J].The VLDB Journal，2014，25（1）：103123

[4] Tu J H.A fixedparameter algorithm for the vertex cover P3 problem[J].Information Processing Letters，2015，115（2）：9699

[5] Kardos F，Katrenic J，Schiermeyer I.On computing the minimum 3path vertex cover and dissociation number of graphs[J].Theoretical Computer Science，2011，412（50）：70097017

[6] Tu J H，Zhou W L.A primaldual approximation algorithm for the vertex cover P3 problem[J].Theoretical Computer Science，2011，412（50）：70447048

[7] Tu J H，Zhou W L.A factor 2 approximation algorithm for the vertex cover P3 problem[J].Information Processing Letters，2011，111（14）：683686

[8] Liu X L，Lu H L，Wang W，et al.PTAS for the minimum kpath connected vertex cover problem in unit disk graphs[J].Journal of Global Optimization，2013，56（2）：449458

[9] Li X S，Zhang Z，Huang X H.Approximation algorithm for the minimum connected kpath vertex cover problem[C]∥International Conference on Combinatorial Optimization and Applications，2014：764771

[10] Chu Y，F(xiàn)an J X，Liu W J，et al.PTAS for minimum kpath connected vertex cover in growthbounded graphs[C]∥International Conference on Algorithms and Architectures for Parallel Processing，2014：114126

[11] Wang L M，Zhang X Y，Zhang Z，et al.A PTAS for the minimum weight connected vertex cover P3problem on unit disk graphs[J].Theoretical Computer Science，2015，571：5866

[12] Zhang Z，Gao X F，Wu W L.PTAS for connected vertex cover in unit disk graphs[J].Theoretical Computer Science，2009，410（52）：53985402

[13] Jiang T，Wang L S.An approximation scheme for some steiner tree problems in the plane[J].Networks，1996，28（4）：187193

[14] Akyildiz I F，Pompili D，Melodia T.Underwater acoustic sensor networks：Research challenges[J].Ad Hoc Network，2005，3（3）：257279

[15] Wang L M，Du W X，Zhang Z，et al.A PTAS for minimum weighted connected vertex cover P3 problem in 3dimensional wireless sensor networks[J].Journal of Combinatorial Optimization，2017，33（1）：106122

[16] Zhang Z，Li X T，Shi Y S，et al.PTAS for minimum kpath vertex cover in ball graph[J].Information Processing Letters，2017，119：913

[17] Chang M S，Chen L H，Hung L J，et al.An O*（1.465 8n）time exact algorithm for the maximum boundeddegree1 set problem[C]∥Proceedings of the 31st Workshop on Combinatorial Mathematics and Computation Theory，2014：918

[18] Xiao M Y，Kou S W.Exact algorithms for the maximum dissociation set and minimum 3path vertex cover problems[J].Theoretical Computer Science，2017，657（A）：8697

[19] Bresar B，Kardos F，Katrenic J，et al.Minimum kpath vertex cover[J].Discrete Applied Mathematics，2011，159（12）：11891195

[20] Jakovac M.The kpath vertex cover of rooted product graphs[J].Discrete Applied Mathematics，2015，187（C）：111119

[21] Zuo L C，Zhang B T，Zhang S Q.The kpath vertex cover in product graphs of stars and complete graphs[J].International Journal of Applied Mathematics，2016，46：97103

[22] Brause C，KrivosBellus R.On a relation between kpath partition and kpath vertex cover[J].Discrete Applied Mathematics，2017，223：2838

[23] Bhavani P D，Kumar K V，Satyanarayana S.An investigation on some theorems on kPath vertex cover[J].Global Journal of Pure and Applied Mathematics，2016，12（2）：14031412

[24] Katrenic J.A faster FPT algorithm for 3path vertex cover[J].Information Processing Letters，2016，116（4）：273278

[25] Chang M S，Chen L H，Hung L J，et al.Fixedparameter algorithms for vertex cover P3[J].Discrete Optimization，2016，19：1222

[26] Tu J H，Jin Z M.An FPT algorithm for the vertex cover P4 problem[J].Discrete Applied Mathematics，2016，200（C）：186190

[27] Fellows M R，Guo J，Moser H，et al.A generalization of Nemhauser and Trotters local optimization theorem[J].Journal of Computer and System Sciences，2011，77（6）：11411158

[28] Chen J E，F(xiàn)ernau H，Shaw P，et al.Kernels for packing and covering problems[C]∥Frontiers in Algorithmics and Algorithmic Aspects in Information and Management，2012：199211

[29] Brause C，Schiermeyer I.Kernelization of the 3path vertex cover problem[J].Discrete Mathematics，2016，339：19351939

[30] Xiao M Y，Kou S W.Kernelization and parameterized algorithms for 3path vertex cover[C]∥International Conference on Theory and Applications of Models of Computation，2017：654668

[31] Tu J H，Yang F M.The vertex cover P3 problem in cubic graphs[J].Information Processing Letters，2013，113（13）：481485

[32] Li Y C，Tu J H.A 2approximation algorithm for the vertex cover P4 problem in cubic graphs[J].International Journal of Computer Mathematics，2014，91（10）：21032108

[33] Bresar B，KrivosBellus R，Semanisin G，et al.On the weighted kpath vertex cover problem[J].Discrete Applied Mathematics，2014，177：1418

[34] Li X S，Zhang Z，Huang X H.Approximation algorithms for minimum （weight） connected kpath vertex cover[J].Discrete Applied Mathematics，2016，205：101108

[35] Tu J H，Wu L D，Yuan J，et al.On the vertex cover P3 problem parameterized by treewidth[J].Journal of Combinatorial Optimization，2016，31（1）：112

[36] Bai Z W，Tu J H，Shi Y T.An improved algorithm for the vertex cover P3 problem on graphs of bounded treewidth[J].arXiv eprint，2016，arXiv：1603.09448

[37] Bhavan P D，Krishna G V，Thota N.Minimum kpath vertex using pruning algorithm[J].International Journal of Scientific Engineering and Technology Research，2014，3（46）：94199422

[38] Zhang Y P，Shi Y S，Zhang Z.Approximation algorithm for the minimum weight connected ksubgraph cover problem[J].Theoretical Computer Science，2014，535：5458