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

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

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

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

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

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

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