頂點覆蓋問題的確定參數(shù)可解算法研究.pdf

1、參數(shù)復(fù)雜性作為經(jīng)典復(fù)雜性研究的一個新的分支發(fā)展時問并不長。在20世紀(jì)90年代初期基于圖鏡定理的證明后[50][51][52],Downey和Fellows兩人首先在這個領(lǐng)域發(fā)表了多篇具有理論突破意義的文章[36][28][29][30][40]。在這些文章中,Downey和Fellows明確定義了確定參數(shù)可解性,同時他們給出了與確定參數(shù)可解性相適應(yīng)的規(guī)約規(guī)則,既而他們定義了多個重要的參數(shù)復(fù)雜性類,最后他們證明了一組各個參數(shù)復(fù)雜性類的完全

2、問題。自此,參數(shù)復(fù)雜性開始得到了廣泛的研究,大量的學(xué)者貢獻于參數(shù)復(fù)雜性的研究。Downey和Fellows于1998年關(guān)于參數(shù)復(fù)雜性的書[1],給出了這個領(lǐng)域的全貌。自那以后,參數(shù)復(fù)雜性的研究并沒有放緩,恰恰相反,參數(shù)復(fù)雜性研究收到了更多的關(guān)注,并且有了專門關(guān)于參數(shù)復(fù)雜性研究的國際會議,同時在各個復(fù)雜性研究的最高級會議中出現(xiàn)了多篇關(guān)于參數(shù)復(fù)雜性研究的結(jié)果[11][12][37][38][39]。即使參數(shù)復(fù)雜性研究在國際上受到了越來越多的

3、關(guān)注,但是與此同時,我國的學(xué)者并沒有跟上相應(yīng)的步伐。中文的參考文獻只能找到我導(dǎo)師和我合著的論文,除此之外再沒有相關(guān)的學(xué)者進行過比較系統(tǒng)的研究。正是因為這種情況,我的導(dǎo)師和我認(rèn)為參數(shù)復(fù)雜性研究已經(jīng)進入成熟階段,需要通過一篇完整的全面的研究論文的介紹來引入中國,我們希望這篇論文是這個介紹的開始。本文主要研究了參數(shù)可解問題,在參數(shù)可解領(lǐng)域主要涉及兩個方面的研究,一個是方面參數(shù)問題的內(nèi)核化研究,而另外一個方面是確定參數(shù)可解問題的算法設(shè)計。本文的

4、第二章,第三章和第四章分別涉及到了這兩方面的問題。本文的第一章主要是參數(shù)復(fù)雜性研究的概述以及研究現(xiàn)況的介紹,主要是說明參數(shù)復(fù)雜性不同于傳統(tǒng)復(fù)雜性研究的地方。最本質(zhì)的區(qū)別在于,參數(shù)復(fù)雜性是在嘗試解決這個問題為什么難,而傳統(tǒng)的復(fù)雜性研究實在回答這個問題是否是難的。正是由于這個區(qū)別,在參數(shù)復(fù)雜性的研究中,是以默認(rèn)一些自然問題是難的為基礎(chǔ)開始的。論文的第二章主要是參數(shù)可解領(lǐng)域重要概念的介紹,包括確定參數(shù)可解的定義,確定參數(shù)可解的規(guī)約定義以及內(nèi)核

5、化的定義。因為參數(shù)復(fù)雜性放寬了可解性定義,所以首先我們介紹了在參數(shù)復(fù)雜性中對于可解性的定義,就是確定參數(shù)可解。正是因為這種對于可解性定義的放寬,所以參數(shù)復(fù)雜性中圖靈規(guī)約并不適用,所以有了確定參數(shù)可解規(guī)約的定義。在這章的最后作者介紹了內(nèi)核化的定義,主要是因為一個問題是確定參數(shù)可解與這個問題可內(nèi)核化是等價的。這章中作者的主要工作是在全章的最后解決了一個參數(shù)復(fù)雜性研究中的重要的開放問題,回答了是否所有的確定參數(shù)可解問題都有線性大小內(nèi)核這個問題

6、。但不幸的是,作者的答案是一個否定的答案。論文的第三章是作者關(guān)于頂點覆蓋問題內(nèi)核化算法的研究成果。作者首先回顧了已有的三種頂點覆蓋問題的內(nèi)核化算法,并說明了這些方法的不足之處。然后作者給出了一個新的關(guān)于頂點覆蓋問題的內(nèi)核化算法,這個算法得出的理論下界的結(jié)果,同時運行效率也相較于本章所介紹的三種內(nèi)核化算法有所提高。論文的第四章是作者關(guān)于確定參數(shù)可解算法設(shè)計的成果。作者主要研究了兩個頂點覆蓋問題的變體問題,一個是連接的頂點覆蓋問題,這個問題