基于樹分解的難解問題的參數(shù)算法研究.pdf

1、NP難解問題是理論計(jì)算機(jī)科學(xué)的主要研究對(duì)象，對(duì)NP難解問題提出實(shí)際有效的固定參數(shù)可解算法是理論計(jì)算機(jī)科學(xué)中的一個(gè)新的研究方向。參數(shù)計(jì)算方法是求解實(shí)際應(yīng)用問題的一種新的有效手段，目前已在相當(dāng)多領(lǐng)域中得到了成功的應(yīng)用。本文選取社會(huì)學(xué)和生物信息學(xué)中的正負(fù)支配、三值支配、聯(lián)盟和序列結(jié)構(gòu)比對(duì)等經(jīng)典的NP難解問題為研究對(duì)象，對(duì)這些問題進(jìn)行參數(shù)化建模后，基于樹分解技術(shù)并綜合運(yùn)用核心化、分支限界、動(dòng)態(tài)規(guī)劃等多種參數(shù)計(jì)算技術(shù)對(duì)它們展開了一系列的研究。其主

2、要研究工作包括:
　　本文證明了社會(huì)學(xué)中的正負(fù)支配問題即使在二分圖，弦圖上都是NP-完全的，并通過抓住圖中頂點(diǎn)要么在正負(fù)支配集內(nèi)，要么與集合中至少兩個(gè)頂點(diǎn)相鄰的特點(diǎn)，分析集合中頂點(diǎn)與集合外頂點(diǎn)之間邊的關(guān)系，給出了參數(shù)化正負(fù)支配集問題在一般圖、平面圖、二分圖、限定最大度圖、正則圖以及網(wǎng)格圖上的核。然后利用正負(fù)支配集大小和正負(fù)支配函數(shù)權(quán)值之間的線性關(guān)系快速地得到了這些圖上正負(fù)支配函數(shù)的最小權(quán)值的下界，并證明了都是嚴(yán)格下界。最后對(duì)參數(shù)化

3、正負(fù)支配集問題提出了一個(gè)在限定樹寬t的圖上時(shí)間復(fù)雜度為O（（4k）2tmn）的固定參數(shù)算法，并由此得到了平面圖上時(shí)間復(fù)雜度為O（2O（√klogk）n2）的亞指數(shù)時(shí)間算法。
　　本文從兩個(gè)角度對(duì)三值支配問題進(jìn)行參數(shù)化并研究其參數(shù)復(fù)雜性。如果以三值支配函數(shù)的權(quán)值大小為參數(shù)，證明了該問題是NP-完全但不存在固定參數(shù)算法。如果以三值支配集的大小為參數(shù)，本文不但通過將紅-藍(lán)支配集問題參數(shù)化規(guī)約到該問題上，證明該問題在一般圖上是W[2]-難

4、度的，還通過限定樹寬圖上的參數(shù)算法和Bidimensionality理論也提出了該問題在平面圖上亞指數(shù)時(shí)間算法。最后通過對(duì)間隔圖上三值支配問題所有的狀態(tài)分析及狀態(tài)轉(zhuǎn)換，利用有限狀態(tài)自動(dòng)機(jī)給出了三值支配問題在間隔圖上的線性時(shí)間算法。
　　本文給出了聯(lián)盟問題中的防守聯(lián)盟、進(jìn)攻聯(lián)盟、全局防守聯(lián)盟和全局進(jìn)攻聯(lián)盟的參數(shù)算法和核。首先利用防守聯(lián)盟中頂點(diǎn)度不超過2k-1以及至少有一半鄰居在防守聯(lián)盟中的特點(diǎn)，運(yùn)用分支限界技術(shù)對(duì)防守聯(lián)盟問題提出了時(shí)

5、間復(fù)雜度為O（kkn）的參數(shù)化算法，并利用核下界理論證明了這防守聯(lián)盟和進(jìn)攻聯(lián)盟問題不存在多項(xiàng)式大小的核。對(duì)全局防守聯(lián)盟和全局進(jìn)攻聯(lián)盟問題，本文給出了限定樹寬圖上的固定參數(shù)算法以及一般圖和平面圖上的核。
　　序列結(jié)構(gòu)比對(duì)是生物信息學(xué)中的經(jīng)典NP難解問題，本文利用序列有小樹寬和序列之間堿基映射小范圍這兩個(gè)小參數(shù)特性給出了序列結(jié)構(gòu)比對(duì)問題的參數(shù)算法。通過將限定樹寬圖上的最大團(tuán)問題進(jìn)行規(guī)約證明了序列結(jié)構(gòu)比對(duì)問題是固定參數(shù)可解的，并在此基礎(chǔ)