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

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

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

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

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

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