（计算机应用技术专业论文）加权边支配集问题的参数算法研究.pdf

摘要 边支配集( e d g ed o m i n a t i n gs e t ) 问题是一类著名的n p 难问题，在 很多领域都有重要应用。在参数复杂性领域中，人们已对边支配集和 加权边支配集问题的参数算法作了大量研究。本文主要从参数复杂性 角度出发，对加权边支配集的两个参数问题：最小加权肛边支配集问 题和加权边支配集固定参数枚举问题展开研究。 本文首先介绍了边支配集问题的研究现状，并阐述了固定参数枚 举算法的基本概念及其具体应用。 在边支配集问题的参数算法研究中，分支搜索技术是解决该问题 的重要技术。本文对分支搜索技术的应用进行简要介绍，提出了最小 加权肛边支配集问题的定义，并通过对问题结构的深入分析，结合匹 配的性质，获得了一个算法运行时f n - - n 0 ( 4 2 馆4 - 4 2 ) 的确定性参数算 法。 在加权边支配集问题的固定参数枚举算法研究中，本文主要采用 枚举扩展的方法，将分支搜索技术和动态规划技术结合起来，提出了 时间复杂度为0 ( 5 6 2 讹2 + 4 2 k n k 3 z ) l 拘有效枚举算法对给定图中前z 个 权值最小的红边支配集进行枚举，有效求解了加权边支配集的枚举问 题。此外，文章通过进一步的分析将算法时间复杂度改进为0 ( 4 2 馆孑 + 4 2 2 萨z ) 。 文章最后对本文所做的研究工作进行了总结，并阐述了加权边支 配集问题中其他相关问题的进一步研究工作。 关键词加权边支配集，参数算法，固定参数可枚举，边覆盖集，匹 配 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：豳：煎叠日期：丑年上月旦日 ， 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：埠年上月4 日 硕士学位论文第一章绪论 第一章绪论 复杂性研究是2 l 世纪科学关注的中心议题之一【l 】。计算复杂性理论是用数 学方法研究使用数位计算机解决各种算法问题困难度的理论 2 1 ，当代几乎所有重 要的科学问题都与计算复杂性有关【3 】。目前计算机所做的信息处理问题大致分为 可解( t r a e t a b l e ) i n - 题与难解( i n t r a c t a b l e ) i h - 题两类。对于可解问题，人们可以找到有 效算法在可容忍的时间和空间内解决这些问题。而对于难解问题，人们很难找到 这样的算法。然而，在实际应用中，很多问题都属于难解问题，如数据库、资源 调度、网络设计等领域中的一些问题。寻求好的算法来解决这些难解问题有很重 要的理论意义和实际意义。 人们为了解决这些难解问题提出了很多有用的方法，包括多项式时间近似算 法【4 - 5 1 、平均事例分析 6 1 、随机算法【7 8 1 以及启发式算法【弘1 川等。然而，这些算法 都有无法避免的缺陷。例如，近似算法只能得到问题的近似解，随机算法有一定 几率得不到正确解。 参数复杂性理论利用各种参数来解决实际的问题，使得许多理论上难解的计 算问题在实际中有可能得到有效解决，成为解决这些难解问题的一种很有前途的 新方法。 本文从参数复杂性理论角度出发，研究加权边支配集两个具体的参数问题： “最小加权肛边支配集问题 和“加权边支配集固定参数枚举问题 。这两个问 题在电话交换网络等领域中具有重要的应用价值。 1 1 课题研究背景 利用计算机解决实际问题时，需要研究的关键问题之一就是：所要求解的问 题是易解的还是难解的。若知道了给定问题的计算时间下界，我们就可以正确的 评价解决该问题的各种算法的效率，进而可以确定对已有算法还有多少改进的余 地。 问题的计算复杂度可以通过求解此问题所需要的计算量的多少进行衡量。目 前通常将可以在多项式时间内求解的问题看作是易解的问题；将在指数时间内求 解的问题看作是难解的问题。对于实际遇到的许多问题，人们至今无法准确了解 其内在的复杂性，因此只能利用分类的方法将计算复杂性大致相同的问题归类进 行研究，而对于能够进行较彻底分析的问题则尽可能准确地确定其计算复杂性， 硕士学位论文第一章绪论 从而更深刻的认识问题。 为了研究问题的计算复杂度，将它们大致分为以下几类【l l 】： p 类问题：是所有可在多项式时间内用确定算法求解的判定问题的集合( 判 定问题是指只需要回答是或不是的问题) 。 n p 问题：是所有可在多项式时间内用不确定算法求解的判定问题的集合。 n p 难问题：对于判定问题q ，如果可满足性问题可在多项式时间内归约到 它，就称q 是n p 一难问题。 n p - 完全问题：如果判定问题q 属于n p 问题，且q 是n p - 难的，就称q 是 n p - 完全问题。 在p n p 的假设下，n - p 难问题是不可能有多项式时间算法的，则n p 完全 问题也不可能有多项式时间算法。 n p 完全理论的发展是理论计算机科学中最伟大的成就之一。n p 。完全理论 为难解计算问题的研究提供了坚实可信的基础。由于这些难解计算问题在实际应 用中的重要性，人们提出了很多方法来解决它们，但是没有一个方法能满足所有 工业和应用上的需求。 近年来，参数复杂性理论成为计算机研究中发展起来的一种用来在实际中解 决大量工程中出现的难解计算问题的新方法。参数复杂性理论的研究主旨在于 “并不是所有形式的难解问题都是等价的 ，有部分难解问题是可以通过一定的 手段使之在实际中可解的。 参数计算与复杂性理论的研究最初来源于人们观察到很多计算问题的解都 与一个取值远小于问题规模的重要参数相关。因此，人们开始研究是否能够为那 些难解问题找到一个指数时间判定算法，使得该算法时间复杂度的指数部分只与 该小参数有关。多年来，人们利用小参数这一特征，使得许多理论上难解的计算 问题在实际中得到了有效解决。 以一个重要的n p 完全问题点覆盖问题为例，目前已知的点覆盖问题最 优精确算法的时间复杂度为( 1 1 9 勺。点覆盖问题的参数化定义为：给定一个图g = ( kd 和一个非负整数k ，l 明= n ，判断图g 是否存在包含阶点的集合c c _ 以使得 图g 中的每条边至少有一个端点在c 中。参数计算与复杂性理论中，撇力) 被看 作参数。利用参数k ，人们为点覆盖问题提出了很多实际有效的算法。目前已知 的最优确定性参数算法的时间复杂度为( 1 2 7 3 2 k + k n ) t 1 2 】。当k 0 7 3 n 时，点覆盖 问题参数算法的可行性就优于其精确算法。 参数计算与复杂性理论的发展为研究计算复杂性下界提供了强有力的工具 0 3 - 1 4 1 ，成功地解释了为何某些理论上能解的计算问题在实际中找不到有效的计算 机算法。 2 硕士学位论文第一章绪论 参数计算与复杂性理论主要对判定问题的参数化问题进行研究。 如果一个参数问题q 可在苁助防i c 时间内解决，其中c 为常数，伪任意函数，就 称q 是固定参数可解的( f i x e d p a r a m e t e rt r a c t a b l e ，f p d 。 许多n p 难问题，如点覆盖问题等，都属于f p t 问题。对于大多数f p t 问题的 参数算法，函狮会很大( 比如，苁p = 矿，d 1 ) 。因此，对于给定的小参数k ， 参数算法的运行时间脚防l c 是可接受的。 然而并不是所有参数问题都是固定参数可解的，例如，在实际中还存在一类 问题，称之为w i t 类问题，其中沩正整数。类似于n p 难度和n p 完全性，参数复 杂性理论中给出了w i t 一难问题及研日完全问题的定义l l 引。 当前理论普遍认为对于所有正整数t ，f p t w i t ，因此，如果一个问题为 w i t 一难的，则认为它是固定参数不可解的，即不能在苁助k i c 时间内判断其某个问 题实例是否为真实例。 参数复杂性研究领域的学者已经鉴定出了上百个参数问题对应的啡度及 完全性【1 6 1 。例如，独立集问题、团问题、加权3 s a t 问题是研1 1 完全问题；加 权c n f s a t 问题、支配集问题、集合覆盖问题、碰撞集问题，以及0 1 整型规划 问题是2 】完全问题。这些问题中很多都在理论和实践方面有着重要意义，很 多专家学者都对其算法进行了广泛的研究。然而，对上述问题尚没有f p t 算法， 这为前面所做的假设- f p t 研，】提供了强有力的支持。 参数计算与复杂性理论研究的具体内容包括：设计更高效的固定参数可解算 法，从而提高算法的有效性、实用性和算法结构的简单性；研究计算难解问题的 计算复杂性，证明某些f p t 问题参数算法的时间复杂度下界；研究最优化问题 的固定参数可解性和近似性之间的联系【1 7 1 。设计固定参数可解算法时用到的主 要技术包括核心化【1 5 1 8 9 1 、分枝界定法【1 9 - 2 2 、贪婪局部法 2 3 - 2 4 1 、图分割【2 5 之6 1 以及 挖掘理论 2 7 - 2 9 】等，事实证明这些技术在设计高效率参数算法中是非常有效的。 如何提高参数算法的运行效率以及寻求新的算法技术是人们在未来的研究 中非常关注的问题。除了在理论上的研究，人们更感兴趣的是参数算法如何在实 际应用中有效的运行。因此，利用参数算法解决实际的计算问题也是很重要的， 这也为参数计算与复杂性理论的研究方向提出了新的挑战【3 0 1 。 1 2 课题研究意义 边支配集问题是一类重要的n p 难问题，被广泛应用于电话交换网络等重要 领域。 目前已知的加权边支配集问题的参数化定义仅对所得边支配集的权值作出 限制，即要求所得边支配集的权值应小于给定的参数。然而，在很多实际问题中， 3 硕士学位论文 第一章绪论 人们希望能够对所得边支配集的边数也做出限制。因此，为加权边支配集问题提 出一个以边数为参数的参数化定义，并寻求有效算法对满足条件的所有边支配集 中权值最小的解进行求取在理论上和实际中都是很有意义的。基于此，本文针对 加权图上的边支配集问题提出了一个新的问题定义最小加权肛边支配集问 题，并对该问题给出了一个f p t 算法。 最优化问题通常要求求出问题实例的一个最优解【3 。然而在处理很多实际 问题时，问题的最优解不一定就是人们需要的最合适的解。因此，人们往往希望 获得问题实例的多个解，即对问题的解进行枚举，从而能够从这些解中选取最合 适的解。传统的枚举策略要求对一个问题实例的所有解进行枚举，这通常是不可 行的。因为即便求取问题的一个解需要的时间是可容忍的，然而问题解的数目有 可能很大，从而造成对问题的所有解进行枚举不可行。此外，对问题的所有解进 行枚举通常也是不必要的【3 2 1 。一般情况下，只需要枚举部分较优解就足以满足 实际的需要【3 3 琊】。 文献 3 6 】中给出了求解加权图中前k 个权值最大的完美匹配的算法，文献 3 7 】 中给出了求解加权图中前k 个权值最小的生成树的算法。然而，这些算法都是 针对一些可在多项式时间内求解的n p 优化问题提出的，并没有对n p 一难优化问 题进行研究。 最近，参数理论中产生了固定参数可枚举( f i x e d p a r a m e t e re n u m e r a b l e ，f p d 这一新概念 3 2 1 ：如果一个n p 优化问题存在一个算法，使得能够在，( 幼刀q 1 匕烈1 ) 时间内枚举问题的前z 个最优，且大小( 即问题解的组成元素个数) 为k 的解，则 称此问题是固定参数可枚举的，其中，【肋是关于k 的一个函数。 对固定参数枚举算法的研究已经引起参数计算研究领域学者的关注。文献 【3 2 分别采用分支搜索、彩色编码和树分解技术，给出加权点覆盖、k - p a t h 以及 平面支配集问题的固定参数枚举算法。 加权边支配集问题已经被证明了是f p t 问题，且目前还没有有效的枚举算 法能够对该问题的解进行枚举。因此，对加权边支配集问题固定参数枚举算法的 研究是具有可行性和实际意义的。 1 3 课题研究内容 本课题着重从参数复杂性理论角度出发，研究加权边支配集问题两个相关的 参数问题：最小加权肛边支配集问题和加权边支配集固定参数枚举问题。主要研 究思想为：根据加权边支配集问题本身的特性，利用图论中边支配集的性质，对 其相关参数算法展开设计和研究，并借此为其他固定参数可解问题提供求解的新 4 硕士学位论文 第一章绪论 方法与新途径。 文章对边支配集问题及其相关问题的定义及研究现状做了介绍，并利用分支 搜索技术和动态规划技术，结合匹配的相关性质为最小加权船边支配集问题和加 权边支配集固定参数枚举问题提出了有效的参数算法，使得能够分别对给定的加 权图g 中权值最小的缸边支配集和前z 个权值最小的矗边支配集( 即将图g 中所 有肛边支配集按权值进行非降序排列得到的前z 个肛边支配集) 进行求取，填补 了这两个问题的研究空白。 1 4 论文组织 论文全文共分五章： 第一章，绪论。这一章首先介绍了课题的研究背景，详细说明了参数计算与 复杂性理论的相关知识，并对本课题的研究意义和主要研究内容做了阐述。 第二章，相关研究工作。这一章首先介绍了边支配集问题的一些相关问题的 定义及其研究现状。同时对固定参数枚举算法做了简要介绍，并以点覆盖问题的 固定参数枚举算法为例阐述了固定参数枚举算法在f p t 问题中的具体应用。 第三章，最小加权肛边支配集问题的参数算法研究。这一章简要介绍了分支 搜索技术及其在点覆盖问题求解过程中的应用，并对最小加权缸边支配集问题参 数算法的实现过程进行了详细描述，具体的分析了算法求解过程以及时间复杂 度。 第四章，加权边支配集问题的固定参数枚举算法研究。这一章首先对动态规 划技术做了简要说明，然后介绍了加权边支配集问题固定参数枚举算法的实现过 程，并对算法中的分支搜索和动态规划过程进行了详细说明，同时分析了算法的 正确性及时间复杂度。 第五章，结束语。这一章总结了课题研究内容，并对将来进一步的研究工作 提出了建议与展望。 5 硕士学位论文第二章相关研究工作 第二章相关研究工作 计算复杂性理论中，边支配集( e d s ) n 题是一类重要的问题，被广泛应用于 很多重要领域，例如，在电话交换网络中为输入线和输出中继线之间建立通话路 由。假设网络中每条中继线在同一时刻只允许进行一个通话，在实际应用中，人 们希望能够找出网络的最坏使用情况，例如，当网络饱和时，可进行的通话数目 最少时的线路使用情况。为此，我们可以构建一个二分图曰，且当且仅当某条线 路可以转换成某条中继线时，才将这个线路与这个中继线相连。从而可将上述问 题转换为寻找图b 的最小独立边支配集问题【3 引。文献【3 9 】中对边支配集问题的应 用做了进一步的阐述。 近年来，人们利用动态规划、加权分治等技术对边支配集问题的精确算法进 行设计与分析，并通过将边支配集问题转化为边覆盖问题提出了边支配集问题的 多项式时间近似算法。随着参数计算理论的发展，人们对参数化边支配集问题做 了大量研究，证明了一般图上的边支配集问题是固定参数可解的，并利用分支搜 索等技术，对其提出了一系列f p t 算法。 本章首先给出了图的一些相关概念和术语；然后对边支配集问题进行分类， 并对每类问题的定义及研究现状进行了介绍；此外，还对固定参数枚举算法的相 关概念及具体应用做了阐述。 2 1图的相关概念和术语 为了更好的描述算法，首先介绍图的一些相关概念和术语嗍。 图：即为一个二元组( k 毋，其包含一个顶点集玎一个边集e 。i 明表示图 中顶点的数目，旧表示图中边的数目。 子图：给定图g = ( kd 和图h = ( 巧，e 1 ) ，如果n k 且e l e l ，则称 日是g 的子图，记为日g 。 二分图：若图g 的顶点集可划分为两个非空子集x 和l 使得图g 中任意 一条边都有一个端点在x 中，另一个端点在】，中，则称g 为二分图( 或偶图) ，记 为g = ued ，d 称为g 的一个划分。 平面图：如果图g 能够满足以下条件，就称图g 是平面图1 4 l 】： 1 ) 图中每条边都是两个点之间的一段弧； 2 ) 不同的边具有不同的端点集合； 6 硕士学位论文第二章相关研究工作 3 ) 图中每条边除端点外，不包含其它点，也不和其它边有交点。 邻居点：给定图g = ( l 毋，如果图g 中两个点v 和u 之间存在边，就称材 和1 ，互为邻居点，称一个点的邻居点的个数为这个点的度。 2 2 边支配集问题研究现状 近年来，人们对边支配集问题的精确算法和近似算法做了大量研究，通过改 进算法本身使得算法具有更优的时间复杂度或近似度，从而使得算法在实际应用 中更可行。参数计算理论被提出后，人们开始对边支配集问题的参数算法进行研 究，并证明了一般图上的边支配集问题为固定参数可解问题。本节根据所研究问 题的差异，对边支配集问题进行分类，并对每类问题的相关算法进行总结。 2 2 1一般边支配集问题 给定图g = ( k 毋，集合s e ，如果图g 中不属于s 的边都至少和s 中一 条边有公共交点，就称s 是图g 的边支配集。下面给出边支配集问题的定义： 定义2 - 1 边支配集( e d g ed o m i n a t i n gs e t ) l h 题：给定图g = ( kd ，目标是 求出图g 中所含边数最少的边支配集。 实际应用中，图g 中每条边的作用可能不一样，对不同的边进行操作需要 付出的代价也可能不一样，为此需要给图g 中每条边赋予不同的权值。从而， 人们开始对加权边支配集问题进行研究。 定义2 - 2 加权边支配集( w e i g h t e de d g ed o m i n a t i n gs e t ) 问题：给定加权图g = ( k 目，图g 的每条边都有一个大于0 的权值，目标是求出图g 中权值最小的 边支配集( 边支配集的权值即为边支配集中所有边的权值之和) 。 人们对一般边支配集问题的精确算法和近似算法进行了大量研究。文献 4 2 】 通过将最小边支配集问题规约为最小极大匹配问题进行求解。 给定图g = ( 以目，集合m c _ e ，如果m 是图g 的匹配，且对于e m 中任 意边p ，m u e 均不是图g 的匹配，就称m 是图g 的极大匹配。 定义2 3 1 4 2 1 极大匹配( m a x i m a lm a t c h i n g ) 问题：给定图g = ( k 目，目标是 求出图g 中所含边数最少的极大匹配。 对于给定的图g 和它的极大匹配m 来说，图g 中不属于m 的边至少和m 中一条边有公共交点。因此，图g 的极大匹配同时也是图g 的边支配集，图g 的边支配集必定包含图g 的一个极大匹配中所有边。文献【4 2 】给出了一个多项式 时间算法使得能够将图g 的任意边支配集转换为图g 的极大匹配，且得到的匹 配大小不会超过边支配集的大小，并对极大匹配问题给出时间复杂度为 7 硕士学位论文第二章相关研究工作 伙1 4 4 2 3 ) 的精确算法，从而得到边支配集问题可在d ( 1 4 4 2 3 ) 时间内解决，其 中n 为给定图中点的数目。 分支搜索技术常常被用于快速指数时间算法的构造中。分支搜索算法( 又称 搜索树算法) 利用规约规则和分支规则，通过递归的调用算法本身来解决n p 一难组 合问题。 f o m i n 4 3 1 将分支搜索技术和动态规划技术结合起来得到极大匹配问题时间 复杂度为0 ( 1 4 0 8 2 ) 的精确算法，从而得到边支配集问题可在d ( 1 4 0 8 2 ) 时间内 解决。 边支配集问题很多相关算法的提出都是基于以下重要结论：给定图g = ( k 曰 和e 的子集d ，如果d 是图g 的边支配集，则d 中所有边的端点集合即为图g 的一个点覆盖。从而得到，图g 的边支配集就是图g 中一个点覆盖的边覆盖集。 因此，人们通常首先利用分支搜索技术对给定图中的极小点覆盖进行枚举，然后 通过一个多项式时间算法求取每个极小点覆盖的最小边覆盖集，从而得到原图的 最小边支配集。 文献【4 4 】通过对极小点覆盖的枚举过程进行改进，得到边支配集问题的指数 时间精确算法，并利用加权分治技术对算法进行分析，得到其时间复杂度为 伙1 3 3 2 3 ) 。算法构造过程基于一个重要思想：当对给定的图g 中度数较大的点 进行分支时，不仅要把这个点从原图中删除，同时还将降低其邻居点的度数。基 于此，算法选择对图g 中长度大于3 的路径上的第三个点进行分支，通过证明 可得该分支算法得到的子问题个数不会超过优1 3 3 2 3 ) ，从而得到算法的时间复 杂度为伙1 3 3 2 3 ) 。此外，文章通过对上述算法添加一组新的规约规则，迸一步 得到加权边支配集问题时间复杂度为0 ( 1 3 2 2 6 ) 的精确算法。 近似算法中，通常也是将边支配集问题转化为边覆盖集问题求解【4 5 4 7 1 。其中， 文献【4 7 】对加权边支配集问题给出近似度为2 的多项式时间近似算法，为目前该 问题近似算法中的最好结果。 2 2 2 参数化边支配集问题 近年来，人们开始利用参数计算的思想对边支配集问题和加权边支配集问题 进行求解，并且已经证明了这两个问题均为f p t 问题。下面给出它们的参数化 定义 4 8 1 ： 定义2 - 4 参数化边支配集( p a r a m e t e r i z e de d g ed o m i n a t i n gs e t ) 问题：给定图 g = ( kd 和正整数k ，目标是求出图g 中一个所含边数不大于k 的边支配集。 定义2 - 5 参数化加权边支配集( p a r a m e t e r i z e dw - e i 曲t e de d g ed o m i n a t i n gs e t ) 问题：给定加权图g = ( 巧毋和正实数k ，图g 的每条边都有一个不小于l 的权 8 硕士学位论文第二章相关研究工作 值，目标是求出图g 中一个权值不大于k 的边支配集。 边支配集问题的参数算法通常基于以下结论 4 8 1 ：给定图g = ( k 日和e 的子 集d ，如果d 是图g 的县边支配集( 即所含边数等于k 的边支配集) ，则d 中所 有边的端点集合即为图g 中一个不大于2 七的点覆盖。因此，图g 的缸边支配集 即为图g 中某个不大于嫩的极小点覆盖的后边覆盖集。所以，边支配集问题的 求解过程通常由两部分组成：枚举给定图中所有不大于2 七的极小点覆盖，该步 骤的时间复杂度为( 4 令【4 9 】，得到的点覆盖数目不超过矿；对每个极小点覆盖求 取其缸边覆盖集，该步骤通常需要用到匹配的相关理论。 f e m a u 【4 8 j 基于以上方法，得到边支配集和加权边支配集问题时间复杂度为 o ( 2 6 1 8 l 勺的参数算法：首先对给定的图g 中所有度数大于l 的点进行分支，从 而得到一组子实例。然后，在多项式时间内对每个子实例对应的最小边支配集进 行求取，从而得到图g 的最小边支配集。f o 血n 【5 0 】对文献【4 8 】中的方法进行进一 步改进，在分支过程中仅对图g 中度数大于2 的点进行分支，从而得到时间复 杂度为( 2 4 1 8 1 勺的参数算法。 2 2 3 边支配集相关研究概述 表2 1 中列出了边支配集和加权边支配集问题一些相关算法的时间复杂度及 用到的关键技术。 表2 - 1 边支配集和加权边支配集问题相关算法比较 人们对边支配集问题所做研究大致可分为三类： 一、对边支配集问题的精确算法进行研究：无论算法如何改进，其时间复杂 度中总有个n 的指数，通常我们认为刀是个很大的数，因此精确算法几乎无法在 实际应用中执行【5 l l ； 二、对边支配集问题的多项式时间近似算法进行研究：然而已知的相关近似 算法的近似率并不理想； 9 硕士学位论文第二章相关研究工作 三、对边支配集问题的参数算法进行研究：目前得到的最优算法时间复杂度 为d 枣( 2 4 1 8 1 勺。当k 较小时，参数算法的时间复杂度在实际操作中是可接受的。 因此，参数计算理论的产生推动了边支配集问题研究的发展，使之成为热点研究 问题。 此外，人们还对一些特殊图上的边支配集问题进行了研究，这些问题中很多 都能够在实际中被用到。 y a n n a k a k i s 和g a v r i l 3 9 j 证明了低度平面图和低度二分图上的边支配集问题仍 然是n p 完全问题。h o r t o n 和k i l a k o s 进一步证明了平面二分图，线图，完美无爪 图以及平面立方图上的边支配集问题也是n p 完全问题【5 2 j 。同时，人们也为部分 特殊图上的边支配集问题找到了多项式时间精确算法，例如，树【5 3 】，无爪弦图， 局部连通无爪图，弦图的线图【5 2 1 ，同三角图【3 8 1 等。 2 3固定参数枚举算法概述及具体应用 典型的复杂性理论中，包含三类主要的计算问题：判定问题( d e c i s i o n p r o b l e m ) 、功能i h - j 题( f u n c t i o n a lp r o b l e m ) ，以及计数问题( c o u m i n gp r o b l e m ) 【5 4 1 。 以无向图上的点覆盖问题( v e r t e xc o v e r ) 为例，该问题对应的判定问题定义如 下： 输入：无向图g = ( ke ) 参数：正整数k 问题：判断图g 中是否存在不大于k 的点集合c 使得e 中每条边都至少有 一个端点属于c ? 点覆盖问题对应的功能问题要求得到一个算法使得能够求出图g 中一个不 大于k 的点覆盖；计数问题要求得到一个算法使得能够求出图g 中不大于k 的 点覆盖的个数。 为满足实际的需要，第四类问题枚举问题( e n u m e r a t i o np r o b l e m ) 也随之 提出。点覆盖问题对应的枚举问题要求得到一个算法使得能够对图g 中所有缸 点覆盖进行枚举( 缸点覆盖即为包含点数为k 的点覆盖) 。 枚举所有矗点覆盖的时间复杂度取决于参数k 是否等于给定图中最小点覆盖 的大小。f e r n a u 5 4 1 证明了，如果k 等于最小点覆盖的大小，则枚举所有舡点覆盖 的时间复杂度为d ( 梦妒+ k n ) ，否则不存在运行时间为贝枷p 1 的算法能够对所有 缸点覆盖进行枚举。因此，对于任意k ，找不到一个可行的算法对所有肛点覆盖 进行枚举。 然而，对于最优化问题，在很多实际情况中并不要求对问题的所有解进行枚 1 0 硕士学位论文第二章相关研究工作 举，往往只需要得到一部分较优的解就足够了。基于此，最近参数理论中产生了 固定参数可枚举这一新概念【3 2 】，对固定参数枚举算法的研究也得到了越来越多 的关注。 定义2 - 6 t 3 2 1 固定参数可枚举( f i x e d p a r a m e t e re n u m e r a b l e ，f p e ) ：如果一个 n p 优化问题存在一个算法，使得能够在必助，1 0 ( 1 彬1 ) 时间内枚举该问题的前z 个 最优，且大小( 问题解的组成元素个数) 为k 的解，则称此问题是固定参数可枚举 的，其中疋幼是关于k 的一个函数。 如果存在一个算法可在，( 助，l d 0 k 时间内枚举某个n p 优化问题的前z 个最优， 且大小为k 的解，就称该问题是固定参数线性可枚举的。 固定参数枚举这种新的枚举模式在理论上和实际中都很有意义。一个问题如 果是固定参数可枚举的，则该问题必定是固定参数可解的。这两类问题之间的相 关联系也是很值得研究的。 文献【3 2 】分别对加权点覆盖问题、k - p a t h 问题，以及平面点支配集问题提出 了有效的固定参数枚举算法。下面以点覆盖问题为例简要的介绍固定参数枚举算 法的应用。首先给出加权点覆盖固定参数枚举问题的定义： 定义2 7 1 3 2 1 加权点覆盖固定参数枚举问题：给定一个加权图g 和整数k 、k ， 图g 的每个点都有一个大于0 的权值，目标是枚举出图g 中前k 个权值最小的 缸点覆盖( 点覆盖的权值即为点覆盖中所有点的权值之和) 。 文献中给出的点覆盖问题的固定参数枚举算法由两部分组成：结构算法和枚 举算法。 结构算法通过一个分支搜索过程将原问题实例( g ，助转化为一组子实例qd ， r ) ，并返回这些子实例的集合。每个子实例伍d ，尺) 对应的点覆盖应包含集合， 中所有点，且不包含集合d 中的点，集合r = v 一( ，w g ) 。结构算法的具体思想 是：每轮从图g 中任取一度数大于2 的点，进行分支，分支一，1 ，属于点覆盖， 则将1 ，放入集合，中，k = k l ；分支二，不属于点覆盖，则将1 ，的所有邻居点 放入集合j 中，并将1 ，放入集合d 中，k = k 一瞅力i ( 拟d 为1 ，的所有邻居点的集 合) 。当k 0 或k = 0 且此时的剩余图中还存在边时，则分支过程结束，并返回 空集；当剩余图中不存在度数大于2 的点时，则分支过程结束，并返回集合 ( 矽， ，功) 。经证明得到，该结构算法的时间复杂度为o ( 1 4 7 锄，算法返回的集合中 包含的子实例个数不超过1 4 6 6 七，且图g 中每个忌点覆盖均和一个子实例对应。 在得到一组子实例后，可通过一个基于动态规划技术的枚举算法分别对每个 子实例他d r ) 对应的前k 个权值最小的肛点覆盖进行求取。 由于此时的剩余图中仅存在度数不大于2 的点，因此可以推断出剩余图中仅 存在三种可能的连通块：孤立点( 度数为0 的点) 、简单路径( 除端点的度数为l 硕士学位论文 第二章相关研究工作 外，其它点的度数均为2 的路径) 、简单圈( 所有点的度数均为2 的圈) 。首先将剩 余图中的点进行编号，使得在同一个连通块中的点具有连续的编号；然后通过一 个动态规划过程，按照编号顺序每次将一个点添加到由编号比该点小的所有点构 成的子图中，并对所有不大于k 的正整数，求取此时图中对应的前k 个权值最 小的，- 点覆盖，直至剩余图中所有点均被添加为止。在求取每个中间图对应的前 k 个权值最小的点覆盖时，需根据新加入的点属于以上哪种连通块，进而对应不 同的处理方案。 经证明可得，枚举算法的时间复杂度为o ( k k n ) 。 对结构算法中得到的所有子实例执行完枚举算法后，从得到的所有肛点覆盖 中选取权值最小的k 个即为图g 中前k 个权值最小的肛点覆盖。 文献通过详细证明得到加权点覆盖问题是固定参数线性可枚举的，其固定参 数可枚举算法的时间复杂度为o ( 1 4 7 k n + 1 2 2 k k n ) 。该算法的提出使得能够更好 的对点覆盖问题的解进行有效枚举，从而更好的满足实际的需要。 通过对一些n p 优化问题的固定参数枚举算法进行研究，人们发现很多能够 被应用于固定参数可解算法的技术同样可被应用到固定参数枚举算法的设计中。 2 4 本章小结 本章首先介绍了边支配集问题及其相关问题的研究现状。 对于加权边支配集问题，通常将所求边支配集的权值作为参数。然而在实际 应用中，我们有时需要对所求边支配集的边数做出限制，从而希望将边支配集所 含边数作为参数提出一个新的问题定义，并为该新问题提出一个有效的算法对其 进行求解。 此外，本章还对固定参数枚举算法的思想进行了简要介绍，并以点覆盖问题 为例介绍了固定参数枚举算法的具体应用。 对于边支配集问题，目前还没有有效的枚举算法对其解进行枚举。基于固定 参数可枚举的思想，希望对加权边支配集问题提出一个有效的固定参数枚举算法 使之能够对问题的一部分较优解进行枚举。 1 2 硕士学位论文第三章最小加权七- 边支配集问题的参数算法研究 第三章最小加权卜边支配集问题的参数算法研究 在参数复杂性理论领域内，加权边支配集问题已经被证明了是固定参数可解 问题。近年来，人们对其参数算法作了大量研究。上一章中介绍了各类边支配集 问题的相关算法及用到的关键技术，本章提出了最小加权肛边支配集问题的参数 化定义，对其参数算法进行讨论，并给出了算法的具体步骤及详细分析过程。 对最小加权肛边支配集问题，目前还没有有效的参数算法对其进行求解，本 章通过对加权边支配集问题的深入分析，在文献【4 8 】提出的算法基础上结合枚举 所有匹配可能包含的端点集的思想，提出了运行时间为o ( 4 2 k k 3 + 4 w ) 的确定性 参数算法，有效求解了最小加权缸边支配集问题。算法首先对图g 中所有不大 于2 七的极小点覆盖进行枚举，并通过对每个极小点覆盖穷举其偶数子集将原问 题实例转换为一组子实例；然后基于极小点覆盖与边支配集的关系，对每个子实 例求取其对应的权值最小的肛边支配集；最后，从得到的肛边支配集中选取权值 最小的即为原问题的解。 3 1 基本知识 给定图g = ( k 目和y 的子集彳，e 的子集b ，表示b 中所有边的端点集 合，助表示图g 中两个端点都属于么的边集合，图g 口】= 似，玩) ，图g ( ke 功 表示将召中的边从图g = ( 以目中删除后得到的子图。 引理3 1 1 4 8 1 给定图g = ( k 毋和e 的子集d ，如果d 是图g 的肛边支配集( 即 包含边数为k 的边支配集) ，则是图g 中一个不大于2 后的点覆盖。 定义3 1 极小点覆盖( m i n i m a lv e r t e xc o v e r ) ：给定图g = ( k 目和g 的点覆 盖c ，如果c 的所有子集( 不包括c 本身) 均不是图g 的点覆盖，就称c 是图g 的极小点覆盖。 引理3 2 1 4 8 1 给定图g = ( k 日和g 的缸边支配集d ，必定包含图g 中一 个不大于2 七的极小点覆盖。 定义3 - 2 边覆盖集( e d g ec o v e r ) ：给定图g = ( k 毋和y 的子集f ，如果存在 边集合c 能够覆盖f 中所有点，就称c 是f 的边覆盖集。 引理3 3 1 4 8 1 给定图g = ( k 目和g 的点覆盖c ，c 的边覆盖集c 是图g 的 边支配集。 根据引理3 2 和引理3 3 可知，假设形是图g 的知边支配集，那么形必定 1 3 硕士学位论文第三章最小加权如边支配集问题的参数算法研究 是图g 中一个不大于2 后的极小点覆盖c 的肛边覆盖集。 定义3 - 3 i 弱l 匹配( m a t c h i n g ) ：给定图g = ( kd ，图g 的匹配是图g 中若干 条没有公共端点的边集合。 给定图g = ( k 目，若图g 中存在匹配m 使得等于乃就称m 是图g 的 完美匹配( p e r f e c tm a t c h i n g ) 。图g 中完美匹配的大小均为i 阳2 ，图g 中所有大小 为l 明2 的匹配都是它的完美匹配。 引理3 _ 4 给定图g = ( 以d 和y 的子集c ，c 的一个边覆盖集g 与图g 【c 】 中边集合的交集为彳，则彳的最大匹配m i ( i l p 包含边数最多的匹配) 是图g q 的 一个匹配( 这个匹配可能为空集，也可能由图g 【c 】中没有公共端点的若干条边组 成) 。 证明：c 的边覆盖集g 有两种可能情况：一、g 不包含图g 【c 】中的边，则 e 与图g 【q 中边集合的交集彳以及彳的最大匹配尬均为空集，就称尬包含图 g c 】中一个为空的匹配；二、c 包含图g 【q 中a 条边，则这a 条边的集合彳的 最大匹配尬即为图g c 】中一个不为空的匹配。基于对这两种情况的分析可知， 彳的最大匹配蚴即为图g 【c 】的一个匹配。 e l 引理3 5 给定一个包含刀个元素的集合s ，s 中每个元素都有一个非负权值， 则在d ( 以) 时间内可以找出s 中前z 个权值最小的元素。 证明：为了找出s 中前z 个权值最小的元素，首先需找到s 中权值为第z 小 的元素s ，很显然查找这个元素花费的时间应为d ( 刀) 。然后，可在d ( 拧) 时间内将 s 中其它元素和s 进行比较，s 中权值比s 小的z 1 个元素即为s 中前z 一1 个 权值最小的元素。因此，求取s 中前z 个权值最小元素的时间复杂度为以门) 。口 加权边支配集问题的定义是将所求边支配集的权值作为参数。为了更好的满 足实际的需要，本章以边支配集所含边数为参数，对最小加权肛边支配集问题的 参数算法进行研究。下面给出该问题的参数化定义： 定义3 - 4参数化最小加权肛边支配集( p a r a m e t e r i z e dm i n i m u mw e i g h t e d k - e d g ed o m i n a t i n gs e t ) 问题：给定加权图g = ( 巧日和正整数k ，图g 的每条边都 有一个大于o 的权值，目标是求出图g 中权值最小的肛边支配集。 本章将在后面部分对参数化最小加权缸边支配集问题提出一个由两部分过 程组成的有效f p t 算法，并对算法的正确性和时间复杂度进行详细的说明和分 析。 3 2b u s s - k e r n e i 算法 核心化是设计参数问题算法的主要技术之一，其定义如下f 1 s l ： 1 4 硕士学位论文第三章最小加权矗边支配集问题的参数算法研究 定义3 5 如果存在一个多项式时间算法k 和一个递归函数g ，使得对于q 的任意实例瓴助，算法k 都能得到q 的一个实例 ，的，其中i x is 反p ，fs k ， 并且当且仅当( x ，的是参数问题q 的一个真实例时，也移才是q 的一个真实例， 那么就称参数问题q 可核心化，称算法k 为核心化算法。 核心化技术将一个问题简化到一个等价的核，且核的大小应为一个关于参数 k 的函数。所以说，核心化是降低问题规模的一个过程，对问题进行核心化预处 理可以大大的提高算法的运行效率。 目前，研究人员针对很多f p t 问题开发了相应的核心化算法，或证明了问 题核的上界。例如，参数化点覆盖问题的核被限定在2 芦1 2 】；平面独立集问题存 在大小为4 后的核【5 6 】；平面支配集问题存在大小为3 3 5 k 的核【5 7 1 。 为了解决点覆盖及其相关问题，常常需要用n b u s s k e r n e l 算法对给定实例进 行局部简化：对实例中每个点v 的度数进行判断，如果这个点的度数为o ，则删除 这个点及其关联边；如果这个点的度数大于k ，则将这个点加入到点覆盖中，并 删除这个点及其关联边。算法具体步骤如图3 一l 所示。 b u s s k e m e l 算法中，步骤1 处理的理由是孤立点不可能出现在最小点覆盖中， 该步骤的时间复杂度为伙以) ，其中以为图g 中点的个数。步骤2 处理的理由是度数 大于k 的点必定属于肛点覆盖，否则，就需要多于阶点才能覆盖这个点的所有邻 边。由于原图g 中点的个数为，l ，且最多只需对每个点的k + 1 条邻边进行遍历， 因此步骤2 的时间复杂度为d ( 砌) 。从而得到，b u s s k e r n e l 算法的时间复杂度为 o ( k n ) ， b u s s k e r n e l 算法将返回一个更小的问题实例，用( g ，妁表示，则图g 最多包 含炉条边和2 k 2 个点。这是因为图g 中所有点的度数均不大于k ，且图g ，的最小点 覆盖中最多有肜个点，f k ，因此g 中边的数目最多为舻。由点数目不会超过边 数目的两倍可知，g 中最多有2 舻个点。如果g 中有多于2 萨个点，就意味着原问 1 5 硕士学位论文第三章最小加权肛边支配集问题的参数算法研究 题实例不存在肛点覆盖。 3 3 分支搜索技术 分支搜索技术( b r a n c h - a n d s e a r c h ) 是基于分支搜索树产生的，被广泛应用于很 多有效精确算法和参数算法的设计中【l 引。 对于一个包含分支搜索过程的参数算法么来说，其分支过程实际上是一个递 归的过程：给定一个实例 ，助，算法彳为原实例构造一组子实例o l ，霸) ，忱，恕) ， ，妫，对于所有来说，白 k 。递归的对所有子问题进行求解最终可得到 原实例的解。 整个分支搜索过程可用一棵搜索树来描述：根节点表示原问题实例o ，肋，它 的孩子分别表示子实例 l ，后1 ) ，阮，恕) ，伍，约，这些子实例均对应一棵搜索 子树( 即以该子实例对应的节点为根结点的子树) 。搜索树中每个叶子节点对应的 子实例都能够很容易被解决。 如果搜索树中每个节点都可以很容易得到( 例如，可在多项式时间内得到) ， 则参数算法彳的时间复杂度可以用搜索树中的节点数目来衡量。由于搜索树中的 节点数目不会超过其叶子节点数目的两倍( 假设搜索树中每个非叶子节点至少包 含两个孩子) ，则分支搜索过程的时间复杂度可用搜索树中叶子节点的数目来衡 量。 如果搜索树r 中某节点t = g ，的的孩子节点分别为 l ，岛) ，( 配，恕) ，妫， 用玎价表示以百为根节点的子树中叶子节点的个数，可得： 致力= 及k 1 ) + 及k 2 ) + + 致蚴 公式( 3 1 ) 令= ，可将公式( 3 - 1 ) 转变成下面的式子： p ( a ) = 口一乞一口 一t k 2 一七，一一口一- k s 一1 = 0公式( 3 - 2 ) 假设x o 为公式( 3 2 ) 的最大正实数根，则致妁0 c o r ，由f k 可知，分支搜 索过程的时间复杂度上界不会超过0 【o 七。 点覆盖问题的参数算法中常常会用到分支搜索技术。给定图g = ( kd 和正 整数k ，对图g 中某个度数为d 的点1 ，进行分支时，通常将其分为两个分支进行 讨论。分支一，1 ，属于点覆盖，则接下来需要在图g 一 v 中求取不大于k l 的 点覆盖：分支二，1 ，不属于点覆盖，则1 ，的所有邻居点都应属于点覆盖中，因此， 接下来需要在图g 一( ，o n ( 力) 中求取不大于k d 的点覆盖