（计算机软件与理论专业论文）带测度函数的连通支配集问题及其近似算法.pdf

摘要 连通支配集问题在网络广播上有着广泛的应用，本文引入测度函数的 概念，提出了带测度函数的连通支配集问题( c d s ( f ) ) ，使得它具有 更广的应用范围。文中首先给出问题的形式定义，证明了它在几种情形卜 的n p 完全性，并给出多项式时间的近似算法，它的近似度为l n l v | + 3 ， 最后给出了一个不可近似下界。 关键词：近似算法，n p ，n p 完全，n p 难，多项式时间归约，连通支配 集问题，组合优化 中图法分类号：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 第一章 引言 支配集问题是集合覆盖问题的一种特殊情况，在现实中有着很广泛的 应用。如果把一一个图中的点想象成需要警戒的点，每条边表示两个端点之 间可以互相守望，那么在支配集中的每个点的位置放一个守卫就口j 以保证 图中的每个点都被警戒到。近年关于支配集的近似算法和参数复杂性问题 的研究很多，现在已经证明它是可以在1 + l 0 9 2 l v l ( v 表示图的顶点集) 内 近似v , j1 6 】，而同时它的不可近似下界是c l 0 9 2 i y l ( c 是0 到1 之间的某常 数) f 7 1 。这个问题的近似算法已经研究的相当成熟了，现在关于它的变种问 题的研究也有很多。b a k e r 对平面图研究支配集问题，给出了一个p t a s 算法8 1 。其他的变种问题包括独立支配集问题，完美支配集问题( 一般情 况下这不是一个n p 完全问题1 ，连通支配集问题。其中连通支配集在网 络广播中有很重要的应用。比如说，图q j 每个节点是一个广播站或者接受 站，两个点之问的边代表他i f w j 。以被互相广播到，于是，j 要让连通支配 集里边的每个点在收到广播的时候，都往自己的邻居再广播一次，就能保 证网络中每个节点都被广播到。现实应用中显然是有局限性的。凶此我们 应该考虑点的支配范围超过1 的情况， 本文第二章对计算复杂性及n p 完全的背景做一个简短的概括，介 绍了问题和语言的定义，p 和n p 类问题，以及多项式规约的意义。第 三章叙述近似算法的相关知识，包括近似度的定义，近似算法的紧致 性，n p 难问题的不可近似性，近似度和可近似下界之间的鸿沟，p t a s 和f p t a s ，最后还介绍了f p t 的相关理论。第四章从连通支配集问题开 始，引入测度函数对其进行研究，对几种情况考虑了它的n p 完全性质： 测度函数，n 一1 ：带测度函数，的连通支配集问题是多项式时间可解 的。 测度函数f n o ，有0s c l g ( n ) ，( n ) c z 9 ( 佗) ) 。 定义2 2o 符号：给定函数9 ( n ) ，0 ( g ( n ) ) 表示这样的一族函数：0 ( 9 ( n ) ) = f ( n ) ：存在正常数c 和正常数礼 使得对所有n n 0 ，有0 ，( n ) c g ( n ) ) 。 定义2 3q 符号：给定函数g ( n ) ，n ( 9 ( n ) ) 表示这样的一族函数：q ( 9 ( 佗) ) 3 ，( n ) ：存布正常数c 和正常数n o ，使得对所有他 n o ，有0sc g ( n ) 曼 厂( 扎) ) 。 定义2 40 符号：给定函数9 ( n ) ，o ( 9 ( n ) ) 表示这样的一族雨数：o ( g ( n ) ) = 厂( n ) ：对任意正常数c ，存在正常数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 的关系不作要求，如果要求运行时 间不仅是规模的多项式，也是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 不可近似性 始终小能指望近似算法能解决所有问题，从一开始我们就知道，妥协 是必须有的，这就是近似算法的不口r 近似性。首先，在p 尸的假设 下，任何n p 难问题是有1 不可近似性的。除此之外，我们仍然希望研究 不同问题的特点，找出它的难度核心( h a r d c o r e ) ，也就是说证明这个算 法不可能( 或者至少很难) 找到小于某一个近似度的算法，这往往能省却 许多无谓的寻找不可能存在的近似算法的努力。 和进行n p 规约的想法一样，我们希望把证明这种难度的工作归结到 已有的一些难度结果卜，直接想到的就是n p 难问题。如果对于一个n p 难问题l 和一个优化问题2 ，能够给出一个( 多项式的) 算法，从n 2 的近似度为p 的近似结果可以得到】的解，那么在p p 的假设下， 我们就可以蜕。小存在p 的近似算法。 一般性的，对于n p 难判定问题1 和优化问题2 ，给定函数p ，如 果存在从。到2 的多项式规约，使得对任意i i ，实例厶，都有2 的实 例如和函数，满足 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 的假设下，优化问题。不存在近似度为，) 的近似算 法。 当然，我们也可以从已有的不可近似性结果得到其他问题的不可近似 性。如果我们已经有从n p 难优化问题。到2 的多项式时间规约 ， 并且这个规约是保持解的规模的( 即，对如= 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 与问题的规模有关，那么要作相应的换算) 。 关于不叫近似界和近似度之间的鸿沟( g a p ) ：如果个问题，我们 证明了它有p l 的不可近似性，同时我们对这个问题有也的近似算法( 当 然p 22p 1 ) ，我们称p 2 和p l 之间有一个鸿沟( g a p ) ，我们对于这个问 题的努力总是循着减小这个鸿沟的目的。如果p - 一p z ，那么从复杂性的角 度，我们基本可以认为这个问题已经彻底解决了( 当然只是在近似算法领 域) 。 不可近似性的证明中，p c p 定理有着不可忽视的作用，下面将用一节 的篇幅介绍一下p c p 定理。 3 2 1p c p 定理 p c p 模型给出了n p 问题的另外种描述，本来这个章节的内容是属 于计算复杂性理论的，p c p 模型起源于交互式证明系统2 4 1 ，最初足为， 研究密码学及其复杂性关系，但既然p c p 定理对于证明不可近似性做出 了巨大的贡献，我们决定把它放在这一章来讲述。 1 5 定义3 1 概率可验证明系统：一个概率可验证明系统是一个多项式图灵机 v ( r ，g ) ，除了工作带，输入带之外，它还有证明带和随机带。它有两个参 数r 和q ，q 代表y 能从证明带上读取的证据的大小，r 代表v 从随机带 上读取的随机串的大小。 接着我们定义p c p 语言类。 定义3 2p c p ( r ( n ) ，q ( n ) ) ：我们称语言l p c p ( r ( n ) ，q ( n ) ) ，如果存在 概率口j 验证明系统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 ) 的证据来进行计算，而丁没有随机带，它对 所有长度为o ( 1 0 9 n ) 的随机串都进行一次计算，如果所有随机串的计算 结果都返同1 ，t 接受当前输入，否则t 拒绝当前输入。由于证据长度 为0 ( 1 ) ，每次计算耗费常数时间，而长度为o ( 1 0 9 n ) 的随机串有p o l y ( n ) 种，因此丁是多项式时间的图灵机。 x l ，存在一个证据y ，v 以概率1 接受。，于是对于这个证据，丁 也接受z 。 16 岳l ，对任何证据y ，v 以小于1 2 的概率接受x ，于是对于t 来 说，它将拒绝z 。 3 3 对n p 难问题的另一种妥协一参数复杂性 ( p a r a m e t e r i z e dc o m p l e x i t y ) 我们前边把近似算法看作是n p 难问题的一种妥协，这一节我们将要 介绍对n p 难问题的另外一种妥协办法一固定参数算法。 这个想法最初是从实用的角度出发，希望能弥补理论上好的算法实际 上并不理想这样的缺陷。首先让我们来看看为什么会这样。 我们知道，对于n p 难问题的近似算法，我们都希望能有f p t a s 或是 p t a s ，这是我们所能期待的最好的结果。a r o r a 曾经为欧基里得平面上 的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 的复杂度也远远不是当前的计算 机所能承受得了的! 这样的算法是根本不实用的! 什么是参数复杂性呢，让我们来看一个关系数据库的例子。现实中的 关系数据库规模都很大，但往往我们需要查询的结果只是很少几条，也就 是说，如果把数据库的规模作为输入规模记为n ，把查询结果的规模作为 参数记为k ，那我们可能主要关心算法复杂性跟n 的关系，至于a ，因为 它相对较小，就算复杂性是七的指数时间，我们也许也能接受。这里就引 出了参数复杂性的概念。如果说复杂性理论就是研究解决问题的复杂性， 也就是解决问题所需要的资源，那么参数复杂性就是对复杂性的更细致的 剥离，它把复杂性看作从输入规模和参数规模两方面来衡量，而不像经典 复杂性理论那样全部笼统的j f 为输入规模。 为了更直观一些，我们用参数复杂性的定义重写顶点覆盖问题的描 述。 顶点覆盖问题 1 7 输入：无向图g ( e ) 参数：正整数 问题：g 是否存在小于等于k 的顶点覆盖集。 和语言的定义相对应，我们有参数化语言。一个参数化语言l 是 e + p 的幂集合的一个元素，lce 。+ ，或者，如果我们规定参数为 正整数，我们可以这样定义：l c + n 。 接下来可以定义何谓参数可解性。 定义3 3 固定参数可解性( f i x e dp a r a m e t e rt r a c t a b l e ) ：一个参数化语 言厶如果存在可计算函数，以及常数c ，存在确定图灵机f ，使得对任 意x e + ，k n ， ( 茁，k ) l 车 t a c c e p t ( z ，) 并且t 的时间界限是f ( k ) l x 。i ，则称l 是固定参数可解的，简称p p l 例如，顶点覆盖问题是参数可解的，支配集问题不是参数可解的，但甲面 图上的支配集问题是参数可解的 1 6 】。 作为补充，我们给出顶点覆盖集的一个简单的f p t 算法。 给定图g ( v e ) ，正整数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 算法已经可以达到o ( k n + 1 2 8 5 2 。) e ，【1 4 ，1 5 】相比最初的算法 已经多考虑了许多因素，我们这里的算法省略了许多细节，要旨是把思想 表达出来。 1 9 第四章 带测度函数的连通支配集问题 4 1 一般的支配集问题 定义4 1 支配集f 咧问题：给定无向图g r k 司，要求找到一个最小的 点集dcv ，使得刘任意u v ，或者ved ，或者存在扎d ，并且 ( “， ) e 。 c h e n 给出了支配集问题的测度函数的些n p 完全性结果f 1 7 ，他通 过从普通的支配集问题进行规约，可惜的是，对于c d s ( f ) 问题并不能做 类似的规约，这也使得我们目前并不能得到很好的不可近似结果，这将作 为下一步的努力方向之一。事实上，测度函数的概念可以推广到一些其他 图论问题，他们有的具有相同的性质，有的存在差异，比如，如果把测度 函数推广到顶点覆盖问题，我们可以得到一些在支配集问题下不能得到的 性质( 这个问题并没有得到系统的结果，所以没有在本文中涉及) 。 定义4 2 连通支配集( c d 剐问题：给定无向图g r e 剧，要求找到一个最 小的连通点集dcv ( 即要求d 的生成子图是连通的) ，使得对任意 v v ，或者v d ，或者存在u d ，并且( ， ) e 。 连通支配集问题是n p 难问题，它在网络广播上有着重要的应用，目前对 于这个问题的最好的近似算法可以达到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 的第三步，之所以选择使覆盖点增加 最多的点对，而不仅仅是一个点，是因为假如最优连通支配集d 。中的某 一个点d ，它所覆盖的某个点在贪心算法某一步被覆盖到，那么下一次或 者可以取到d 作为支配集中的点，或者取到的点覆盖的点一定比d 所覆盖 的点多，这将在证明近似度的时候用到。 为了证明算法1 的近似度，茸先定义个点的分担权的概念，也就是 把d 中的点分摊到它覆盖的点上去。注意到在贪心算法中，一个点可能同 时被几个点覆盖，假设点u 使得点v 由着色w h i t e 变为g r a y ，则称点u 是 初次覆盖点v 。 2 】 定义4 3 假设在算法4 中，点“是被点对 钆v 2 ) 所初次覆盖的，则定 义点“的分担权c ( 2 2 ) = ；，k 表示同时被 u 1 ，v 2 ) 所初次覆盖的点的个 数。 为了证明算法4 1 的近似度，首先给出下面的命题。它的证明是显而 易见的，冈此不再赘述。 命题4 1 算法4 的输出l d l = 。yc ( “) 。 定理4 1 算法4 的近似度为2 ( 1 + h ( ) ) 。 证明：设_ d 。舛为最优支配集方案，记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 执行的顺序，假设第一次c o v e r ( u ) 中有 点被覆盖以后剩下的点的个数为u ，第二次c o v e r ( u ) 中有点被覆盖以后剩 下的点的个数为u 2 ，第k 次c o v e r ( u ) 中有点被覆盖以后剩下的点的 个数为2 2 k = 0 。 下面计算c o v e r ( u ) 中点的分担权之和。 第一次被覆盖的点数为u 。一2 2 ，由于这一次可能同时还覆盖r 其他的 点，于是这些点的分担权均小于等于2 ( 2 2 0 一1 ) 。 第二次被覆盖的点数为1 一“2 ，由于第一次已经覆盖了c o v e r ( u ) 中 的点，而算法4 1 每次取覆盖点最多的点对，所以若第二次没有取到点 u ( 从而把c o v e r ( u ) 中剩下的点全部覆盖) ，那么第二次覆盖的点数一定 不少于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 步每次循环会在结果集d 中增加两 个点，而d 最多不会超过v ，于是第3 步最多执行o f n ) 次。每次执行。 需要寻找当前着色为g r a y 的一个点以及一个与它相邻的点构成的点对中， 能使被着色点增加最多的。g 中的相邻点对个数为o ( m ) ，对于每个点对， 查看连接矩阵得到他们所覆盖的点( o ( n ) 时问) ，所以每次循环的时间复杂 度为o f n m ) 。 于是算法4 1 的时间复杂度为o ( n 2 m ) 。 4 2 带测度函数的连通支配集问题 前面对支配集问题的相关方而做了描述，下面来看它的一个扩展一带 测度函数的连通支配集问题。对于这个问题，我们是出于这样的考虑，希 望能扩展原问题的应用范围。以上面提到的网络广播的应用来说明，我们 期望我们提供的解可以适应尽量不受限制的嘲络广播能力的情况。 在这个问题中，我们为结点的覆盖范围定义了个函数称为测度函数 ，以结点个数i v i 为自变量，它定义的意义是图g 中个结点可以覆盖 跟它相邻的多远的结点。我们对于这个问题讨论了不同测度函数的n p 完 全性，对于n p 难的情况，我们通过从顶点覆盖问题进行规约来证明它的 n p 完全性。 我们首先需要一些辅助定义。 定义4 4 给定无向图g ( k e ) 中的两个顶点u ，w 和函数，称u ，u 是，一相 邻的，如果g 中存在一条“到”的路径l ，并且满足l e n g t h ( 1 ) sf 。 定义4 5 给定无向图g k e ) 中的一个顶点集u 和函数，称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 ) 中的两个顶点，”和函数，称u 是，一可覆 盖 的，如果“和口是，一相邻的。 在继续之前首先说明一下，下面为了描述简便，本章中我们将假设 m = e l ，n = i y i a 定义4 7c d s ( f ) 问题是指：给定连通无向图g 及测度函数，要求图 g 的最小点集d y ，满足： 可覆盖性：对任意v v ，或者 d ，或者存在d ，使得和 是 l ，一相邻的。 连通性：d 在g 中是，一连通的。 这样定义的c d s ( f ) 问题显然是n p 难问题( 因为c d s 问题是它的 一种特殊情况) ，但是我们并不满足，我们想要对更细致的情况进行讨 论。 定理4 2 若测度函数，( n ) 21 1 , 一l ，刚c d s ( f ) 的优化问题是多项式时间 j 。解问题。 证明：显然，任意取一个点都是图g 的一个支配集。于是，图g 的带测 度函数的最小连通支配集的大小为1 。 定理4 3 若测度函数，( 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 知，每次循环至少会从t 中删掉i f ( n ) 1 个点，同时往d 中添加个点，并且我们的算法保证每次删除的点都被d 中某一个点所覆 盖，而n l ，( 佗) j c ，于是l d ls c 。 现在我们知道对于f n 一1 ，f = p ( n ) ，带测度函数，的连通支配集是 多项式时间可解的，那么我们寻找问题的难解性的希望就落在，一o ( n 1 的 范围内。 定理4 4 对于任意0 e 1 ，带测度函数f = k n ( k 为任意大于口