参数化反馈顶点集问题的研究

摘要

反馈顶点集（Feedback Vertex Set，简称FVS）问题是经典的NP难问题，在电路测试、操作系统解死锁、网络设计、分析工艺流程、生物计算等领域都有重要应用。 人们提出了一系列解决FVS问题算法技术，包括近似算法、精确算法和随机算法等。随着参数计算理论的发展，近年来参数化FVS问题引起了人们的重视，并对此问题的研究取得了很大突破。目前已经证明了无向图和有向图中FVS问题都是固定参数可解的（fixed-parameterized tractable，简称FPT）。 本文研究了带权无向图中FVS问题的固定参数枚举技术，提出了一种有效的基于分支搜索技术的固定参数枚举算法。首先求出给定图G的一个含k个顶点的FVS F；然后基于F对图G进行结构划分，对各结构划分利用分支搜索技术求得满足一定条件的图结构，从而将FVS问题转化为反馈边集（Feedback Edge Set，简称FES）问题；最后通过枚举z个权值最大森林来枚举z个权值最小的FES，进而枚举出z个权值最小的含k个顶点的FVS。整个算法时间复杂度为0（5kkn2+（5k+3kz）n2 logn）。 本文还研究了竞赛图（Toumaments）的参数化带权FVS问题，即在竞赛图中找一个权值最小的含顶点数不超过k的FVS。首先，利用求解竞赛图中不带权FVS问题的FPT算法求出一个含k个点的FVS F；然后对F进行划分，并对每种划分，将问题转化为相同子序列（Common Subsequence）问题而求得基于此划分的权值最小的FVS；基于所有划分的FVS中权值最小的一个FVS即为问题的解。本文分别用分支搜索和动态规划两种技术求解相同子序列问题，从而对参数化带权FVS问题提出了时间复杂度分别为O（3kn）和O（2kn2（logn+k））的算法。 本文最后对FVS问题的研究工作进行了总结，并阐述了对该问题的进一步研究工作。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题研究背景

1.2课题研究意义

1.3课题研究内容

1.4论文组织

第二章FVS问题的研究现状

2.1相关定义

2.2无向图中FVS问题

2.2.1无向图中MFVS和MWFVS问题

2.2.2无向图中PFVS问题

2.3有向图中FVS问题

2.3.1一般有向图中FVS问题

2.3.2竞赛图上的FVS问题

2.4其他特殊图上的FVS问题

2.5小结

第三章FVS问题的固定参数枚举

3.1相关定义和引理

3.2 FVS的固定参数枚举算法

3.2.1元组构造

3.2.2基于元组的局部枚举

3.2.3固定参数枚举算法及分析

3.3小结

第四章竞赛图中参数化带权FVS问题

4.1相关定义及引理

4.2竞赛图中PW-MFVS的FPT算法

4.2.1求解Reduce-WFVST问题的算法

4.2.2基于分支搜索的算法

4.2.3基于动态规划的算法

4.3小结

第五章结束语

5.1研究工作总结

5.2进一步研究工作展望

参考文献

致谢

研究成果