具有小距離屬性的NP難圖問(wèn)題核心化算法研究.pdf

1、在當(dāng)前的算法框架下，圖上的NP難問(wèn)題不大可能存在多項(xiàng)式時(shí)間的精確算法（除非P=NP）。關(guān)于NP難問(wèn)題的研究主要集中在參數(shù)算法、近似算法、啟發(fā)式算法和精確算法等多方面。核心化算法作為參數(shù)算法理論的重要組成部分，不僅可用于設(shè)計(jì)更好的參數(shù)算法，同時(shí)由于其本身的特性，也常常作為NP難問(wèn)題常用的預(yù)處理手段。
　　核心化算法的主要思想是，對(duì)于參數(shù)化問(wèn)題Q的輸入大小為n的一個(gè)實(shí)例(G,k)進(jìn)行快速預(yù)處理，或者將該問(wèn)題解決，或者輸出一個(gè)等價(jià)的實(shí)例

2、(G′,k′)。算法同時(shí)保證G′的大小不超過(guò)由k確定的一個(gè)界g(k)，而與輸入大小n無(wú)關(guān)。g(k)便稱為該問(wèn)題的問(wèn)題核。由于大多數(shù)問(wèn)題在實(shí)際應(yīng)用中都存在一個(gè)小參數(shù)k，因此在實(shí)際問(wèn)題中問(wèn)題核通常不會(huì)很大，此時(shí)即便運(yùn)用暴力算法也可快速將原問(wèn)題解決。
　　核心化的特點(diǎn)，在于它不僅在實(shí)際中運(yùn)用效果良好，而且存在嚴(yán)格的理論支撐，它保證了得到的解是原問(wèn)題的精確解。也正因?yàn)榇?，核心化算法用于近似算法、啟發(fā)式算法和精確算法時(shí)的預(yù)處理手段也取得了很

3、好的效果。對(duì)于某些問(wèn)題，核心化算法甚至能夠直接得到最優(yōu)的精確解。同時(shí)，一個(gè)問(wèn)題存在問(wèn)題核當(dāng)且僅當(dāng)它是固定參數(shù)可解的。因此核心化算法也常常做為其他參數(shù)算法的設(shè)計(jì)基礎(chǔ)。
　　本文從當(dāng)前的核心化技術(shù)入手，結(jié)合了核心化技術(shù)中“皇冠分解”和“區(qū)域分解”的思想并將其擴(kuò)展延伸。針對(duì)圖上的參數(shù)化幾乎導(dǎo)出匹配問(wèn)題及3-路徑覆蓋問(wèn)題，分別提出核心化算法，通過(guò)點(diǎn)集劃分和局部規(guī)則調(diào)整，尋找到圖的一種特定劃分，對(duì)于每一部分的大小分別進(jìn)行分析。如果該部分包含

4、頂點(diǎn)超過(guò)某個(gè)界，我們或者可以將該問(wèn)題解決，或者可以確定該問(wèn)題實(shí)例滿足一定性質(zhì)。本文分別對(duì)兩個(gè)問(wèn)題定義了一種“類皇冠結(jié)構(gòu)”，在上述性質(zhì)下可快速找到該結(jié)構(gòu)，并利用該結(jié)構(gòu)對(duì)問(wèn)題進(jìn)行約簡(jiǎn)。因此，當(dāng)實(shí)例中不存在該類結(jié)構(gòu)時(shí)我們得到了問(wèn)題的問(wèn)題核。本文的算法改進(jìn)了之前的最好結(jié)果，針對(duì)參數(shù)化的幾乎導(dǎo)出匹配問(wèn)題和3-路徑覆蓋問(wèn)題分別得到大小為8k和5k的問(wèn)題核。
　　此外，本文針對(duì)某一類具有小距離屬性的NP難圖問(wèn)題，提出了一種一般性的核心化算法框架