顶点覆盖问题的确定参数可解算法研究

摘要

参数复杂性作为经典复杂性研究的一个新的分支发展时问并不长。在20世纪90年代初期基于图镜定理的证明后[50][51][52],Downey和Fellows两人首先在这个领域发表了多篇具有理论突破意义的文章[36][28][29][30][40]。在这些文章中,Downey和Fellows明确定义了确定参数可解性,同时他们给出了与确定参数可解性相适应的规约规则,既而他们定义了多个重要的参数复杂性类,最后他们证明了一组各个参数复杂性类的完全问题。自此,参数复杂性开始得到了广泛的研究,大量的学者贡献于参数复杂性的研究。Downey和Fellows于1998年关于参数复杂性的书[1],给出了这个领域的全貌。自那以后,参数复杂性的研究并没有放缓,恰恰相反,参数复杂性研究收到了更多的关注,并且有了专门关于参数复杂性研究的国际会议,同时在各个复杂性研究的最高级会议中出现了多篇关于参数复杂性研究的结果[11][12][37][38][39]。即使参数复杂性研究在国际上受到了越来越多的关注,但是与此同时,我国的学者并没有跟上相应的步伐。中文的参考文献只能找到我导师和我合著的论文,除此之外再没有相关的学者进行过比较系统的研究。正是因为这种情况,我的导师和我认为参数复杂性研究已经进入成熟阶段,需要通过一篇完整的全面的研究论文的介绍来引入中国,我们希望这篇论文是这个介绍的开始。本文主要研究了参数可解问题,在参数可解领域主要涉及两个方面的研究,一个是方面参数问题的内核化研究,而另外一个方面是确定参数可解问题的算法设计。本文的第二章,第三章和第四章分别涉及到了这两方面的问题。本文的第一章主要是参数复杂性研究的概述以及研究现况的介绍,主要是说明参数复杂性不同于传统复杂性研究的地方。最本质的区别在于,参数复杂性是在尝试解决这个问题为什么难,而传统的复杂性研究实在回答这个问题是否是难的。正是由于这个区别,在参数复杂性的研究中,是以默认一些自然问题是难的为基础开始的。论文的第二章主要是参数可解领域重要概念的介绍,包括确定参数可解的定义,确定参数可解的规约定义以及内核化的定义。因为参数复杂性放宽了可解性定义,所以首先我们介绍了在参数复杂性中对于可解性的定义,就是确定参数可解。正是因为这种对于可解性定义的放宽,所以参数复杂性中图灵规约并不适用,所以有了确定参数可解规约的定义。在这章的最后作者介绍了内核化的定义,主要是因为一个问题是确定参数可解与这个问题可内核化是等价的。这章中作者的主要工作是在全章的最后解决了一个参数复杂性研究中的重要的开放问题,回答了是否所有的确定参数可解问题都有线性大小内核这个问题。但不幸的是,作者的答案是一个否定的答案。论文的第三章是作者关于顶点覆盖问题内核化算法的研究成果。作者首先回顾了已有的三种顶点覆盖问题的内核化算法,并说明了这些方法的不足之处。然后作者给出了一个新的关于顶点覆盖问题的内核化算法,这个算法得出的理论下界的结果,同时运行效率也相较于本章所介绍的三种内核化算法有所提高。论文的第四章是作者关于确定参数可解算法设计的成果。作者主要研究了两个顶点覆盖问题的变体问题,一个是连接的顶点覆盖问题,这个问题要求求得的顶点覆盖集合在原图是连通的,另一个是含权树型顶点覆盖问题,这个问题要求所得的顶点覆盖集合在原图构成一颗树的同时还要满足问题的权重要求。作者对于这两个问题都给出了确定参数可解算法并且这两个算法的运行时间都是目前所知结果中最优的结果。论文的第五章就是全文的回顾以及未来工作的展望。

目录

摘要

Abstract

第一章 综述

1.1 参数复杂性研究的介绍

1.2 主要的算法设计思路—与魔鬼的交易

1.3 参数复杂性中不可解问题的概述

第二章 基础概念

2.1 确定参数可解

2.2 确定参数可解的规约

2.3 内核化

第三章 顶点覆盖问题的内核化算法研究

3.1 顶点覆盖问题内核化的算法

3.1.1 预处理

3.1.2 大度数内核化方法

3.1.3 线性编程的内核化方法

3.1.4 网络流内核化方法

3.2 一种新的顶点覆盖问题的内核化算法

3.2.1 预处理

3.2.2 规约设计

3.2.3 顶点覆盖问题的新内核算法

第四章 顶点覆盖问题变体的确定参数可解问题

4.1 研究概述

4.2 连接顶点覆盖问题的确定参数可解算法

4.3 含权的树型顶点覆盖问题的确定参数可解算法

第五章 文章总结和展望

5.1 论文总结

5.2 未来工作的展望

参考文献

附录 研究生期间撰写的论文

后记