（計算機軟件與理論專業(yè)論文）帶測度函數(shù)的連通支配集問題及其近似算法.pdf

摘要 連通支配集問題在網(wǎng)絡廣播上有著廣泛的應用，本文引入測度函數(shù)的 概念，提出了帶測度函數(shù)的連通支配集問題( c d s ( f ) ) ，使得它具有 更廣的應用范圍。文中首先給出問題的形式定義，證明了它在幾種情形卜 的n p 完全性，并給出多項式時間的近似算法，它的近似度為l n l v | + 3 ， 最后給出了一個不可近似下界。 關鍵詞：近似算法，n p ，n p 完全，n p 難，多項式時間歸約，連通支配 集問題，組合優(yōu)化 中圖法分類號：t p 3 0 1 6 a b s t r a c t c o n n e c t e dd o m i n a t i n gs e t sp r o b l e mh a sw i d e l yu s e di nn e t w o r kb r o a d c a s t t h i sp a p e ri n t r o d u c e st h ec o n c e p to fm e a s m e df u n c t i o na n dd e f t n e s c o n n e c t e dd o m i n a t i n gs e t sp r o b l e mw i t hm e a s u r e df u n c t i o n s ( c d s ( f ) ) a f o r m a ld e f i n i t i o no ft h ec d s ( f ) i sf i r s t l yg i v e n ，w h o s en p p r o p e r t yi st h e n p r o v e di ns e v e r a ls i t u a t i o n sw ea l s op r e s e n ta na p p r o x i m a t i o na l g o r i t h m w i t ha p p r o x i m a t i o nr a t i ot n l v l + 3a n dl a s t l yw ep r o v ei ti si n a p p r o x i m a t e d w i t h i n1 1 6 6 6u n l e s sp - - n p _ k e yw o r d s ： a p p r o x i m a t i o na l g o r i t h m ，n rn p c o m p l e t e ，n p h a r d ，p o l y n o m i mr e _ d u c t i o n ，c o n n e c t e dd o m i n a t i n gs e t ，c o m b i n a t o r i a lo p t i m i z a t i o n c l a s s i f i c a t i o nc o d e ：t p 3 0 1 6 i i 第一章 引言 支配集問題是集合覆蓋問題的一種特殊情況，在現(xiàn)實中有著很廣泛的 應用。如果把一一個圖中的點想象成需要警戒的點，每條邊表示兩個端點之 間可以互相守望，那么在支配集中的每個點的位置放一個守衛(wèi)就口j 以保證 圖中的每個點都被警戒到。近年關于支配集的近似算法和參數(shù)復雜性問題 的研究很多，現(xiàn)在已經(jīng)證明它是可以在1 + l 0 9 2 l v l ( v 表示圖的頂點集) 內(nèi) 近似v , j1 6 】，而同時它的不可近似下界是c l 0 9 2 i y l ( c 是0 到1 之間的某常 數(shù)) f 7 1 。這個問題的近似算法已經(jīng)研究的相當成熟了，現(xiàn)在關于它的變種問 題的研究也有很多。b a k e r 對平面圖研究支配集問題，給出了一個p t a s 算法8 1 。其他的變種問題包括獨立支配集問題，完美支配集問題( 一般情 況下這不是一個n p 完全問題1 ，連通支配集問題。其中連通支配集在網(wǎng) 絡廣播中有很重要的應用。比如說，圖q j 每個節(jié)點是一個廣播站或者接受 站，兩個點之問的邊代表他i f w j 。以被互相廣播到，于是，j 要讓連通支配 集里邊的每個點在收到廣播的時候，都往自己的鄰居再廣播一次，就能保 證網(wǎng)絡中每個節(jié)點都被廣播到?，F(xiàn)實應用中顯然是有局限性的。兇此我們 應該考慮點的支配范圍超過1 的情況， 本文第二章對計算復雜性及n p 完全的背景做一個簡短的概括，介 紹了問題和語言的定義，p 和n p 類問題，以及多項式規(guī)約的意義。第 三章敘述近似算法的相關知識，包括近似度的定義，近似算法的緊致 性，n p 難問題的不可近似性，近似度和可近似下界之間的鴻溝，p t a s 和f p t a s ，最后還介紹了f p t 的相關理論。第四章從連通支配集問題開 始，引入測度函數(shù)對其進行研究，對幾種情況考慮了它的n p 完全性質： 測度函數(shù)，n 一1 ：帶測度函數(shù)，的連通支配集問題是多項式時間可解 的。 測度函數(shù)f n o ，有0s c l g ( n ) ，( n ) c z 9 ( 佗) ) 。 定義2 2o 符號：給定函數(shù)9 ( n ) ，0 ( g ( n ) ) 表示這樣的一族函數(shù)：0 ( 9 ( n ) ) = f ( n ) ：存在正常數(shù)c 和正常數(shù)禮 使得對所有n n 0 ，有0 ，( n ) c g ( n ) ) 。 定義2 3q 符號：給定函數(shù)g ( n ) ，n ( 9 ( n ) ) 表示這樣的一族函數(shù)：q ( 9 ( 佗) ) 3 ，( n ) ：存布正常數(shù)c 和正常數(shù)n o ，使得對所有他 n o ，有0sc g ( n ) 曼 廠( 扎) ) 。 定義2 40 符號：給定函數(shù)9 ( n ) ，o ( 9 ( n ) ) 表示這樣的一族雨數(shù)：o ( g ( n ) ) = 廠( n ) ：對任意正常數(shù)c ，存在正常數(shù)n o ，使得對所有n n o ，有0s ，( n ) n o ，有 0 c g ( n ) 0 ，4 的運行時間都是實例j 覿模的多項式，就稱是問題的 多項式時問的近似方案( p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ， 簡稱p t a s 。 1 3 p t a s 的定義對4 運行時間與e 的關系不作要求，如果要求運行時 間不僅是規(guī)模的多項式，也是1 店的多項式，那么4 就稱是問題的 完全多項式時間的近似方案( f u l lp o l y n o m i a lt i m ea p p r o x i m a t i o n s c h e m e ) ，簡稱f p t a s 。 在p n p 的假定下，對一個n p 難問題來講，最好的可能就是設計 這個問題的f p i 、a s ，但并升i 是所有n p 難問題都存在f p t a s 。比如背包 問題是存在f p r a s 的。 3 2 不可近似性 始終小能指望近似算法能解決所有問題，從一開始我們就知道，妥協(xié) 是必須有的，這就是近似算法的不口r 近似性。首先，在p 尸的假設 下，任何n p 難問題是有1 不可近似性的。除此之外，我們?nèi)匀幌Ｍ芯?不同問題的特點，找出它的難度核心( h a r d c o r e ) ，也就是說證明這個算 法不可能( 或者至少很難) 找到小于某一個近似度的算法，這往往能省卻 許多無謂的尋找不可能存在的近似算法的努力。 和進行n p 規(guī)約的想法一樣，我們希望把證明這種難度的工作歸結到 已有的一些難度結果卜，直接想到的就是n p 難問題。如果對于一個n p 難問題l 和一個優(yōu)化問題2 ，能夠給出一個( 多項式的) 算法，從n 2 的近似度為p 的近似結果可以得到】的解，那么在p p 的假設下， 我們就可以蛻。小存在p 的近似算法。 一般性的，對于n p 難判定問題1 和優(yōu)化問題2 ，給定函數(shù)p ，如 果存在從。到2 的多項式規(guī)約，使得對任意i i ，實例厶，都有2 的實 例如和函數(shù)，滿足 1 ) 若2 是最小化問題 若厶是”y e s ”實例，則o p t ( 如) f ( 1 2 ) 若j 1 是”n o ”實例，則o p t ( 1 2 ) p ( 1 2 1 ) f u 2 ) 2 1 若2 是最大化問題 若厶是”y e s ”實侈4 ，則o p t ( 1 2 ) ，( 如) 若厶是”n o ”實例，則o p t ( 1 2 ) i 南，) 那么，在p p 的假設下，優(yōu)化問題。不存在近似度為，) 的近似算 法。 當然，我們也可以從已有的不可近似性結果得到其他問題的不可近似 性。如果我們已經(jīng)有從n p 難優(yōu)化問題。到2 的多項式時間規(guī)約 ， 并且這個規(guī)約是保持解的規(guī)模的( 即，對如= q ) ，( 7 1 s 。( 1 1 ) ，觀 島一。( 如) ，n 。( 口，) 一，。( 觀) ) ，那么就有 1 1 2c 扎b epa p p r o x i m a t e d 辛i i ic a n6 epa p p r o x i m a t e d 等價于 h i ( x l nn o tb epa p p r o x i m a t e d 號1 1 2c a t tn o tb epa p p r o x i m a t e d 于是從1 的不口j 近似結果就可以得到。的不可近似結果( 這當中要注 意，如果p 與問題的規(guī)模有關，那么要作相應的換算) 。 關于不叫近似界和近似度之間的鴻溝( g a p ) ：如果個問題，我們 證明了它有p l 的不可近似性，同時我們對這個問題有也的近似算法( 當 然p 22p 1 ) ，我們稱p 2 和p l 之間有一個鴻溝( g a p ) ，我們對于這個問 題的努力總是循著減小這個鴻溝的目的。如果p - 一p z ，那么從復雜性的角 度，我們基本可以認為這個問題已經(jīng)徹底解決了( 當然只是在近似算法領 域) 。 不可近似性的證明中，p c p 定理有著不可忽視的作用，下面將用一節(jié) 的篇幅介紹一下p c p 定理。 3 2 1p c p 定理 p c p 模型給出了n p 問題的另外種描述，本來這個章節(jié)的內(nèi)容是屬 于計算復雜性理論的，p c p 模型起源于交互式證明系統(tǒng)2 4 1 ，最初足為， 研究密碼學及其復雜性關系，但既然p c p 定理對于證明不可近似性做出 了巨大的貢獻，我們決定把它放在這一章來講述。 1 5 定義3 1 概率可驗證明系統(tǒng)：一個概率可驗證明系統(tǒng)是一個多項式圖靈機 v ( r ，g ) ，除了工作帶，輸入帶之外，它還有證明帶和隨機帶。它有兩個參 數(shù)r 和q ，q 代表y 能從證明帶上讀取的證據(jù)的大小，r 代表v 從隨機帶 上讀取的隨機串的大小。 接著我們定義p c p 語言類。 定義3 2p c p ( r ( n ) ，q ( n ) ) ：我們稱語言l p c p ( r ( n ) ，q ( n ) ) ，如果存在 概率口j 驗證明系統(tǒng)y ( o ( r ( r 1 ) ) ，6 ( q ( r 。) ) ) ，對于任意茁p 若z l ，則存在一個證明y 使得v 接受? 的概率為1 。 若z 彰l ，則對于所有長度為0 ( q ( n ) ) 的證明y ，v 接受z 的概率小 于1 2 。 以上的概率是基于所取的不同的隨機串。 斷言3 1 p = p c p ( o ，p o l y ( n ) ) ：由p c p 的定義直接口j 得。 利用p c p 定理可以直接證明可滿足性問題，集合覆蓋問題，團問題 等基礎性問題的一些不可近似結果，但是p c p 定理的討論超出了本文的 范圍，我們在這里僅僅給出p c p 定理及其。半的證明。 定理3 2p c p 定理：_ p = p c p ( 1 0 9 n ，1 ) 證明：我們僅僅給出p c p ( 1 0 9 n ，1 ) cn p 的證明。 令語言l p c p ( 1 0 9 n ，1 ) ，我們要證明l 也能被n p 所判定。構造這 樣一個圖靈機1 1 ，丁與y 不同的地方只在于，y 從隨機帶上取o ( 1 0 9 n ) 的 隨機串，從輸入帶上取0 ( 1 ) 的證據(jù)來進行計算，而丁沒有隨機帶，它對 所有長度為o ( 1 0 9 n ) 的隨機串都進行一次計算，如果所有隨機串的計算 結果都返同1 ，t 接受當前輸入，否則t 拒絕當前輸入。由于證據(jù)長度 為0 ( 1 ) ，每次計算耗費常數(shù)時間，而長度為o ( 1 0 9 n ) 的隨機串有p o l y ( n ) 種，因此丁是多項式時間的圖靈機。 x l ，存在一個證據(jù)y ，v 以概率1 接受。，于是對于這個證據(jù)，丁 也接受z 。 16 岳l ，對任何證據(jù)y ，v 以小于1 2 的概率接受x ，于是對于t 來 說，它將拒絕z 。 3 3 對n p 難問題的另一種妥協(xié)一參數(shù)復雜性 ( p a r a m e t e r i z e dc o m p l e x i t y ) 我們前邊把近似算法看作是n p 難問題的一種妥協(xié)，這一節(jié)我們將要 介紹對n p 難問題的另外一種妥協(xié)辦法一固定參數(shù)算法。 這個想法最初是從實用的角度出發(fā)，希望能彌補理論上好的算法實際 上并不理想這樣的缺陷。首先讓我們來看看為什么會這樣。 我們知道，對于n p 難問題的近似算法，我們都希望能有f p t a s 或是 p t a s ，這是我們所能期待的最好的結果。a r o r a 曾經(jīng)為歐基里得平面上 的t s p 問題給出過一個f t p a s ，它的算法的時間復雜度是( ) ( i 訾) 1 3 1 ， 我們不妨來看看這意味著什么。這意味著，如果我們想要得到11 的近似 度，算法的時間復雜度將達到0 ( n 3 ”o o ) ，可見，即使它是個多項式時間 算法，但就算對于很小的輸入1 0 ，1 0 3 0 0 0 0 的復雜度也遠遠不是當前的計算 機所能承受得了的! 這樣的算法是根本不實用的! 什么是參數(shù)復雜性呢，讓我們來看一個關系數(shù)據(jù)庫的例子。現(xiàn)實中的 關系數(shù)據(jù)庫規(guī)模都很大，但往往我們需要查詢的結果只是很少幾條，也就 是說，如果把數(shù)據(jù)庫的規(guī)模作為輸入規(guī)模記為n ，把查詢結果的規(guī)模作為 參數(shù)記為k ，那我們可能主要關心算法復雜性跟n 的關系，至于a ，因為 它相對較小，就算復雜性是七的指數(shù)時間，我們也許也能接受。這里就引 出了參數(shù)復雜性的概念。如果說復雜性理論就是研究解決問題的復雜性， 也就是解決問題所需要的資源，那么參數(shù)復雜性就是對復雜性的更細致的 剝離，它把復雜性看作從輸入規(guī)模和參數(shù)規(guī)模兩方面來衡量，而不像經(jīng)典 復雜性理論那樣全部籠統(tǒng)的j f 為輸入規(guī)模。 為了更直觀一些，我們用參數(shù)復雜性的定義重寫頂點覆蓋問題的描 述。 頂點覆蓋問題 1 7 輸入：無向圖g ( e ) 參數(shù)：正整數(shù) 問題：g 是否存在小于等于k 的頂點覆蓋集。 和語言的定義相對應，我們有參數(shù)化語言。一個參數(shù)化語言l 是 e + p 的冪集合的一個元素，lce 。+ ，或者，如果我們規(guī)定參數(shù)為 正整數(shù)，我們可以這樣定義：l c + n 。 接下來可以定義何謂參數(shù)可解性。 定義3 3 固定參數(shù)可解性( f i x e dp a r a m e t e rt r a c t a b l e ) ：一個參數(shù)化語 言厶如果存在可計算函數(shù)，以及常數(shù)c ，存在確定圖靈機f ，使得對任 意x e + ，k n ， ( 茁，k ) l 車 t a c c e p t ( z ，) 并且t 的時間界限是f ( k ) l x 。i ，則稱l 是固定參數(shù)可解的，簡稱p p l 例如，頂點覆蓋問題是參數(shù)可解的，支配集問題不是參數(shù)可解的，但甲面 圖上的支配集問題是參數(shù)可解的 1 6 】。 作為補充，我們給出頂點覆蓋集的一個簡單的f p t 算法。 給定圖g ( v e ) ，正整數(shù)k ，求問g 是否有小于等于k 的頂點覆蓋 集? 它的f p t 算法偽碼如下： a 擊： s 一 4 ) ； f o re a c he = ( ，u ) ed o f o re a c ha sd o s s a ： i fl a u “) i t h e n s 仁s u 4 u 亂； i fi a u ) iskt h e n ，5 r 一5 | u a u “； i f i 4 u ， l k t h e n 1 8 s s u a u 札， ) ) ； e n d e n d 簡單的分析就可以得到l e l 2 。的時間復雜度，事實上，頂點覆蓋日前 的f p t 算法已經(jīng)可以達到o ( k n + 1 2 8 5 2 。) e ，【1 4 ，1 5 】相比最初的算法 已經(jīng)多考慮了許多因素，我們這里的算法省略了許多細節(jié)，要旨是把思想 表達出來。 1 9 第四章 帶測度函數(shù)的連通支配集問題 4 1 一般的支配集問題 定義4 1 支配集f 咧問題：給定無向圖g r k 司，要求找到一個最小的 點集dcv ，使得劉任意u v ，或者ved ，或者存在扎d ，并且 ( “， ) e 。 c h e n 給出了支配集問題的測度函數(shù)的些n p 完全性結果f 1 7 ，他通 過從普通的支配集問題進行規(guī)約，可惜的是，對于c d s ( f ) 問題并不能做 類似的規(guī)約，這也使得我們目前并不能得到很好的不可近似結果，這將作 為下一步的努力方向之一。事實上，測度函數(shù)的概念可以推廣到一些其他 圖論問題，他們有的具有相同的性質，有的存在差異，比如，如果把測度 函數(shù)推廣到頂點覆蓋問題，我們可以得到一些在支配集問題下不能得到的 性質( 這個問題并沒有得到系統(tǒng)的結果，所以沒有在本文中涉及) 。 定義4 2 連通支配集( c d 剮問題：給定無向圖g r e 劇，要求找到一個最 小的連通點集dcv ( 即要求d 的生成子圖是連通的) ，使得對任意 v v ，或者v d ，或者存在u d ，并且( ， ) e 。 連通支配集問題是n p 難問題，它在網(wǎng)絡廣播上有著重要的應用，目前對 于這個問題的最好的近似算法可以達到h ( a ) + 2 的近似度f 1 0 】，并且在 n p d t i m e ( n o ( 抽g l o g n ) ) 的假設下，它是h ( a ) 不町近似的 1 1 ，1 2 。令 人驚奇的是，連通支配集問題問題達到h ( a ) + 2 的近似度的算法僅僅是 一個簡單的貪心策略。下面我們給出一個連通支配集的近似算法，它也使 用了貪心算法的策略，它的近似度能達到2 ( 1 + 打f ) 1 。 算法4 1 連通支配集問題的近似算法： 輸入：圖g ( v e ) 。 輸出：圖g 的連通支配集d 。 步驟： 1 ) 初始化：給g 中所有點著色w h i t e ( 表示”未覆蓋”) 。任取。點 “，初始化d = u ，給“著色為b l a c k ( 表習i ”選中作為支配集 中的點”) ，所有與u 相鄰的點著色為g r a y ( 表示”已覆蓋”) 。 2 ) 如果g 沒有顏色為w h i t e 的點，則輸出d ，算法結束。 3 ) 從v p 中尋找能使被覆蓋點增加最多的一個點對，要求這個 點對加到d 巾仍能使d 保持連通性( 也即其中至少有一個點要 與d 中的點相鄰，也即其中至少要有一個點的著色為g r a y ) 。 假設找到的點對的集合為礦，令d = d u u ，并把u 著色為 b l a c k ，u 所覆蓋到的新的點著色為g r a y 。 4 ) 轉別。 由算法第二步易知，這樣找到的d 確實是g 的一個連通支配集。 對算法4 1 的分析：在算法4 1 的第三步，之所以選擇使覆蓋點增加 最多的點對，而不僅僅是一個點，是因為假如最優(yōu)連通支配集d 。中的某 一個點d ，它所覆蓋的某個點在貪心算法某一步被覆蓋到，那么下一次或 者可以取到d 作為支配集中的點，或者取到的點覆蓋的點一定比d 所覆蓋 的點多，這將在證明近似度的時候用到。 為了證明算法1 的近似度，茸先定義個點的分擔權的概念，也就是 把d 中的點分攤到它覆蓋的點上去。注意到在貪心算法中，一個點可能同 時被幾個點覆蓋，假設點u 使得點v 由著色w h i t e 變?yōu)間 r a y ，則稱點u 是 初次覆蓋點v 。 2 】 定義4 3 假設在算法4 中，點“是被點對 釓v 2 ) 所初次覆蓋的，則定 義點“的分擔權c ( 2 2 ) = ；，k 表示同時被 u 1 ，v 2 ) 所初次覆蓋的點的個 數(shù)。 為了證明算法4 1 的近似度，首先給出下面的命題。它的證明是顯而 易見的，岡此不再贅述。 命題4 1 算法4 的輸出l d l = 。yc ( “) 。 定理4 1 算法4 的近似度為2 ( 1 + h ( ) ) 。 證明：設_ d 。舛為最優(yōu)支配集方案，記o p t l d 小對于d ( ，礎中每 一個點u ，定義c o v e r ( u ) 為點u 所覆蓋的點集，這樣可把v 中所有點都唯 一地歸到某一個c o v e r ( u ) 中( 對于同時被幾個d 。中的點所覆蓋的點， 把它隨便歸于其中某一。個支配點的c o v e r 集合) 。 對于c o v e r ( u 1 中所有的點，最終它們將被某一個d 中的點所覆蓋。 設i c o w r ( u ) 1 = u o ，按照算法4 1 執(zhí)行的順序，假設第一次c o v e r ( u ) 中有 點被覆蓋以后剩下的點的個數(shù)為u ，第二次c o v e r ( u ) 中有點被覆蓋以后剩 下的點的個數(shù)為u 2 ，第k 次c o v e r ( u ) 中有點被覆蓋以后剩下的點的 個數(shù)為2 2 k = 0 。 下面計算c o v e r ( u ) 中點的分擔權之和。 第一次被覆蓋的點數(shù)為u 。一2 2 ，由于這一次可能同時還覆蓋r 其他的 點，于是這些點的分擔權均小于等于2 ( 2 2 0 一1 ) 。 第二次被覆蓋的點數(shù)為1 一“2 ，由于第一次已經(jīng)覆蓋了c o v e r ( u ) 中 的點，而算法4 1 每次取覆蓋點最多的點對，所以若第二次沒有取到點 u ( 從而把c o v e r ( u ) 中剩下的點全部覆蓋) ，那么第二次覆蓋的點數(shù)一定 不少于c o v e r ( d ) 中剩下的點“，( 這里用到了分析1 的結論) ，于是第二次每 個點的分擔權小于等于2 札。按照同樣的方法可以對c o v e r ( u ) 其他被覆 蓋的點進行分析，于是c o v e r ( u ) 中所有點的分擔權之和。g m ) c ( ) i i 蘭五( “o 一1 ) + 。k ：1 1 瓦2 、u 。 一2 u i + 1 ) 2 ( 1 + 等u i - - 。u 。i + l 。莖2 ( 1 + 日( ) ) 于是。d 。，；。g 。( 。) c ( ) 2 ( 1 + 口( ) ) o p t 而卜式的左邊正好是v 中所有點的分擔權之和，也即 2 2 。礦c ( ) = 。d 。c ( u ) 莖2 ( 1 + h ( z x ) ) o p t 再由命題4 ，1 ，就得到d = 。；vc ( u ) 2 ( 1 + 日( ) ) o p t 算法4 1 的時間復雜度分析：第3 步每次循環(huán)會在結果集d 中增加兩 個點，而d 最多不會超過v ，于是第3 步最多執(zhí)行o f n ) 次。每次執(zhí)行。 需要尋找當前著色為g r a y 的一個點以及一個與它相鄰的點構成的點對中， 能使被著色點增加最多的。g 中的相鄰點對個數(shù)為o ( m ) ，對于每個點對， 查看連接矩陣得到他們所覆蓋的點( o ( n ) 時問) ，所以每次循環(huán)的時間復雜 度為o f n m ) 。 于是算法4 1 的時間復雜度為o ( n 2 m ) 。 4 2 帶測度函數(shù)的連通支配集問題 前面對支配集問題的相關方而做了描述，下面來看它的一個擴展一帶 測度函數(shù)的連通支配集問題。對于這個問題，我們是出于這樣的考慮，希 望能擴展原問題的應用范圍。以上面提到的網(wǎng)絡廣播的應用來說明，我們 期望我們提供的解可以適應盡量不受限制的嘲絡廣播能力的情況。 在這個問題中，我們?yōu)榻Y點的覆蓋范圍定義了個函數(shù)稱為測度函數(shù) ，以結點個數(shù)i v i 為自變量，它定義的意義是圖g 中個結點可以覆蓋 跟它相鄰的多遠的結點。我們對于這個問題討論了不同測度函數(shù)的n p 完 全性，對于n p 難的情況，我們通過從頂點覆蓋問題進行規(guī)約來證明它的 n p 完全性。 我們首先需要一些輔助定義。 定義4 4 給定無向圖g ( k e ) 中的兩個頂點u ，w 和函數(shù)，稱u ，u 是，一相 鄰的，如果g 中存在一條“到”的路徑l ，并且滿足l e n g t h ( 1 ) sf 。 定義4 5 給定無向圖g k e ) 中的一個頂點集u 和函數(shù)，稱u 是，一連 通的，在ge e ) ，如果對于u 中任意兩個點，v ，在g 中存在一條 t t 到u 的 路徑z ，并h 假設z 上有k 個礦中的點，依次是v 1 = “，v 2 ，v r _ 1 v 女= ， 要求它們滿足：地與u 是f 一千目鄰的( i = l ，2 ，一1 ) 。 定義4 6 給定無向圖g ( v e ) 中的兩個頂點，”和函數(shù)，稱u 是，一可覆 蓋 的，如果“和口是，一相鄰的。 在繼續(xù)之前首先說明一下，下面為了描述簡便，本章中我們將假設 m = e l ，n = i y i a 定義4 7c d s ( f ) 問題是指：給定連通無向圖g 及測度函數(shù)，要求圖 g 的最小點集d y ，滿足： 可覆蓋性：對任意v v ，或者 d ，或者存在d ，使得和 是 l ，一相鄰的。 連通性：d 在g 中是，一連通的。 這樣定義的c d s ( f ) 問題顯然是n p 難問題( 因為c d s 問題是它的 一種特殊情況) ，但是我們并不滿足，我們想要對更細致的情況進行討 論。 定理4 2 若測度函數(shù)，( n ) 21 1 , 一l ，剛c d s ( f ) 的優(yōu)化問題是多項式時間 j 。解問題。 證明：顯然，任意取一個點都是圖g 的一個支配集。于是，圖g 的帶測 度函數(shù)的最小連通支配集的大小為1 。 定理4 3 若測度函數(shù)，( n ) l ，( n ) j ，于是在從樹根v 到u 的路徑h ，存在一點w ，使得l ( w ，t ) = l ，( n ) j 。令d = d u w ) ， 從t 中刪去以w 為根的子樹( 不包括w ) 作為新的t ( 因為l ( w ，“) 一 l ，( n ) j ，所以可以保證這一棵子樹的所有結點都可以被w 所覆蓋) 。 轉第二步。 從上面的算法口j 知，每次循環(huán)至少會從t 中刪掉i f ( n ) 1 個點，同時往d 中添加個點，并且我們的算法保證每次刪除的點都被d 中某一個點所覆 蓋，而n l ，( 佗) j c ，于是l d ls c 。 現(xiàn)在我們知道對于f n 一1 ，f = p ( n ) ，帶測度函數(shù)，的連通支配集是 多項式時間可解的，那么我們尋找問題的難解性的希望就落在，一o ( n 1 的 范圍內(nèi)。 定理4 4 對于任意0 e 1 ，帶測度函數(shù)f = k n ( k 為任意大于口