d-Hitting Set問題的固定參數(shù)化算法.pdf

1、HITTING SET-問題是組合學(xué)中的一個經(jīng)典計(jì)算問題,它和集合覆蓋(Set Cover)問題等價(jià),其任務(wù)是計(jì)算有限集合S的一個基數(shù)較小的子集D使之滿足和集合C的每一個元素相交非空,其中集合C是集合S的冪集的一個子集(即C()P(S)),集合D稱為C的一個hitting set。
　　 從超圖理論的角度來看HITTING SET問題,S和C分別是超圖H=(S,C)的節(jié)點(diǎn)集合和超邊集合,D是超圖H的節(jié)點(diǎn)覆蓋。如果超圖H的每條超邊

2、大小都等于某個自然數(shù)d,則稱H為d-一致超圖,其對應(yīng)的節(jié)點(diǎn)覆蓋問題就等價(jià)于d-HITTING SET問題。在經(jīng)典復(fù)雜性理論框架下,無論HITTING SET-問題還是任意的d-HITTINGSET問題都是NP-完全的,其中d≥2。這意味著不存在多項(xiàng)式時(shí)間的確定性算法計(jì)算它們除非P=NP。然而在參數(shù)復(fù)雜性框架下,d-HITTING SET問題是固定參數(shù)易求解的,而HITTING SET問題卻是W[2]-完全的。
　　 參數(shù)復(fù)雜性理

3、論是復(fù)雜性理論中的一個新興分支。近些年來,參數(shù)復(fù)雜性的發(fā)展非常迅速并且已經(jīng)滲透到計(jì)算機(jī)科學(xué)的許多領(lǐng)域,它從參數(shù)化的角度研究可計(jì)算問題的復(fù)雜性:除把輸入長度n作為計(jì)算耗費(fèi)的考察對象外,還引入一個新的參數(shù)k,并提出了固定參數(shù)易求解的概念,從而拓寬了易求解的傳統(tǒng)概念--多項(xiàng)式時(shí)間可解性。因此,這也使得復(fù)雜類的層次結(jié)構(gòu)劃分更加細(xì)致,問題的歸約更加復(fù)雜。
　　 HITTING SET問題尤其是d-HITTING SET問題的研究在計(jì)算機(jī)理

4、論和應(yīng)用兩方面都具有相當(dāng)重要的意義和價(jià)值。本文在參數(shù)復(fù)雜性理論框架下系統(tǒng)研究了d-HITTING SET問題的固定參數(shù)化算法,并做出了如下幾方面的貢獻(xiàn):
　　 ●本文系統(tǒng)研究了d-HITTING SET問題的多種核化算法。文章以一般圖的節(jié)點(diǎn)覆蓋問題作為切入點(diǎn),詳細(xì)研究了基于約減規(guī)則、皇冠約減、線性規(guī)劃和網(wǎng)絡(luò)流技術(shù)在內(nèi)的多種不同主流核化算法,并且探索了基于這些技術(shù)計(jì)算d-HITTINGSET問題的核化算法的可能性,其中d≥2。

5、r>　　 ●本文分別研究了度數(shù)受限于l的、平面的和擬正則的d-一致超圖上的節(jié)點(diǎn)覆蓋問題,其中l(wèi)≥3和d≥2。一方面,文章證明了這些特殊d-一致超圖上的節(jié)點(diǎn)覆蓋問題都是NP-完全的。另一方面,文章基于兩個不同的規(guī)模函數(shù),分別提出了核大小為l·k和((d-1)·l+1)·k的核化算法計(jì)算度數(shù)受限于l的d-一致超圖的節(jié)點(diǎn)覆蓋問題。隨后,文章基于計(jì)算平面圖支配集問題的核化算法,提出了計(jì)算平面的3-一致超圖節(jié)點(diǎn)覆蓋問題核大小為67k的核化算法。

6、同時(shí),文章也證明了平面的d-一致超圖節(jié)點(diǎn)覆蓋問題無法基于類似平面的3-一致超圖的技術(shù)獲得核大小為O(k)的核化算法,其中d≥4。最后,文章基于線性規(guī)劃技術(shù),提出了計(jì)算擬正則的d-一致超圖節(jié)點(diǎn)覆蓋問題核大小為d·k的核化算法,其中d≥2。
　　 ●本文分別研究了度數(shù)受限于l的、平面的和擬正則的d-一致超圖上的節(jié)點(diǎn)覆蓋問題的對偶問題--獨(dú)立集問題,其中l(wèi)≥3和d≥2。一方面,文章基于兩個不同的規(guī)模函數(shù)提出了核大小分別為l/d d-1

7、i(1+(d-1)·l·k和d-1(1+(d-1)·l·k的核化算法計(jì)算度數(shù)受限于l的d-一致超圖的獨(dú)立集問題。隨后,文章借助平面的3-一致超圖的強(qiáng)獨(dú)立集問題和平面圖的導(dǎo)出匹配問題,提出了核大小為12k的核化算法計(jì)算平面的3-一致超圖的獨(dú)立集問題。另一方面,文章證明了擬正則的d-一致超圖的獨(dú)立集問題是W[1]-完全的。
　　 ●本文基于參數(shù)化對偶技術(shù)并結(jié)合計(jì)算結(jié)構(gòu)特殊的d-一致超圖上節(jié)點(diǎn)覆蓋問題、獨(dú)立集問題和支配集問題等若干相關(guān)

8、問題的核化算法,分別給出了這些核化算法核大小的下界,其中d≥2。
　　 ●本文全面研究了d-HITTING SET問題的搜索樹算法。一方面,文章通過更加細(xì)致的算法分析進(jìn)一步改進(jìn)了節(jié)點(diǎn)覆蓋問題的搜索樹算法的時(shí)間復(fù)雜度。另一方面,文章在新的度量方式下重新刻畫了3-一致超圖的節(jié)點(diǎn)覆蓋問題,并且結(jié)合已有的啟發(fā)式規(guī)則,運(yùn)用擬凸規(guī)劃技術(shù)系統(tǒng)分析了的搜索樹算法,改進(jìn)了前人的結(jié)果。
　　 本文從參數(shù)復(fù)雜性理論的角度系統(tǒng)全面地研究了d-H