Domination問題的算法和復雜性.pdf

1、Domination問題是組合學中最具有代表性的一類判定問題,一般可分為：支配集問題,強支配集問題,獨立支配集問題和聯(lián)通支配集問題等。其中研究最多的是支配集問題。它和集合覆蓋問題是等價的,是Karp于1972年提出的21個經典NP-完全問題之一[80]。Domination問題在計算機網絡、計算生物學以及社會計算等方面都有實際應用。因此研究Domination問題具有極其重要的意義。本文主要從復雜性和算法兩個方面,深入研究Dominat

2、ion問題。在經典復雜性框架下,我們分別證明在界度圖、正則圖和稀疏圖中最小支配集問題、最小強支配集問題和最小獨立支配集問題都是NP-完全的。在參數復雜性框架下,我們證明在界度圖、正則圖中,最小支配集問題、最小強支配集問題和最小獨立支配集問題都是屬于FPT。此外我們還證明在稀疏圖中,這三個問題屬于W[2]-hard,與一般圖中的性質一樣。在近似算法方面,我們主要研究最小強支配集。這里給出最小強支配集問題的一步貪心算法,其近似度是ln(δ？

3、 0.5) + 1.5。同時還給出近似度保留規(guī)約,證明在無向圖和有向圖中,最小強支配集問題的不可近似性質,表明本文給出近似算法的近似度與下界幾乎重合。在精確算法方面,我們主要在子圖類上研究支配集問題。首先我們提供了一個精確算法可以在O？(1.3759n)的時間內求解split圖上的支配集問題,這個算法基于Liedloff的前期工作和在split圖上找最大獨立集算法。其次我們證明了對于任意的？ >； 0,當n充分大的時候,4-正則圖的