頂點覆蓋k-路問題

《頂點覆蓋k-路問題》是依託北京化工大學，由塗建華擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：頂點覆蓋k-路問題
• 依託單位：北京化工大學
• 項目類別：青年科學基金項目
• 項目負責人：塗建華

項目摘要

頂點覆蓋問題是組合最佳化和計算機科學領域最經典NP難問題之一，Erd?s(國際數學大師，Wolf 獎得主)等人把它推廣成了頂點覆蓋某類子圖問題。這類推廣問題，與近似算法理論和計算複雜性理論有著緊密聯繫，是近二十年來圖論研究的熱點問題。頂點覆蓋k-路問題也屬於這類推廣的問題。同時，頂點覆蓋k-路問題的研究，與圖論的其他課題也有著重要聯繫，且在兩類實際問題中有著重要套用。. 本項目將從兩個方面來研究頂點覆蓋k-路問題。首先，我們從算法的角度研究頂點覆蓋k-路問題，確定某些問題的算法複雜性，給出這些問題的近似算法或多項式時間的精確算法。設計k為一般情況下的頂點覆蓋k-路問題的近似算法。另一方面，我們研究頂點覆蓋k-路數。將經典圖論中的方法與機率方法相結合，來研究圖的頂點覆蓋k-路數與圖的若干其他不變數（最大度、直徑、半徑、圍長等）的關係，給出圖的頂點覆蓋k-路數的上下界，或者精確值。

結題摘要

本項目研究的主要問題是頂點覆蓋k-路問題：在給定圖G中找一個最小的頂點子集F，使得圖中任何一條k個頂點的路都至少有一個頂點在這個頂點子集F中。它是經典的頂點覆蓋問題的推廣，同時也屬於Erdos（Wolf獎得主）等人推廣的頂點覆蓋子圖問題，故此問題的研究在計算機算法與複雜性方面有著重要的理論意義。同時頂點覆蓋k-路問題的研究在實際中也有著廣泛的套用，特別是在無線感測器網路加密問題與交通燈設定問題上有著重要套用。由此，頂點覆蓋k-路問題吸引了越來越多的國內外學者的關注，已經成為圖論與計算機算法領域的一個研究熱點。 項目主要從算法的角度重點研究了頂點覆蓋k-路問題，研究了一般圖上的頂點覆蓋k-路問題近似算法以及特殊圖上問題的計算複雜性與求解算法。目前，項目組得到的主要結果有： （1）證明了對於任意的k＞=2，頂點覆蓋k-路問題都是NP-完全的，並利用原始對偶方法與局部比值法給出了一般圖上頂點賦權情況下頂點覆蓋3-路問題的兩個2-近似算法，這也是頂點覆蓋3-路問題近似算法方面最好的結果； （2）研究了特殊圖上的頂點覆蓋k-路問題，證明了頂點覆蓋3-路問題與頂點覆蓋4-路問題在三正則圖上都是NP-完全的，並分別給出了1.25-近似算法與2-近似算法； （3）研究了樹、單圈圖、仙人掌圖上的頂點覆蓋k-路問題，並給出了這些圖上的多項式時間的精確算法； （4）考察了頂點覆蓋k-路問題的參數化算法，用疊代壓縮方法分別給出了頂點覆蓋3-路問題與頂點覆蓋4-路問題的固定參數算法； （5）研究了相關的組合最佳化問題：部分頂點覆蓋問題與獎勵收集的頂點覆蓋問題，對這兩個問題給出了目前最好的近似算法，以及研究了其他的一些圖論問題，得到一些研究成果。