中文摘要：

图修正问题即对给定的图作最少的修改使之具有某种特定的属性。大量具体的图修正问题是NP难的，参数计算是实际处理图修正难解问题的一种新的有效手段。本项目运用参数计算理论及技术深入系统地研究难解的图修正问题，其目标是对该类问题设计实际有效的固定参数可解算法。本项目将深入研究多种具体图修正问题的参数计算复杂性，对固定参数可解问题设计有效的核心化规则和提出高效的固定参数可解算法，对固定参数难解问题从新的角度引入新的参数进而研究其新的结果。在此基础上，本项目还将深入探究不同图修正问题参数计算复杂性之间的内在联系，揭示同类图修正问题的参数计算复杂性规律，提炼图修正问题的通用性核心化方法，拓展图修正问题的参数化算法设计技术。本项目的研究将为图修正难解问题的成功应用创立理论基础和新的实用方法。

结论摘要：

在本基金的资助下，课题组对图修正问题的参数化算法进行了深入系统的研究，并且取得了很大进展。研究内容既包括一系列不同具体问题的算法研究，也包含同类问题算法设计技术的规律探究；既包括以求解为目标的分支算法的研究，也包含以精简实例为目标的核心化算法的研究；既注重经典图修正问题的研究，也包含其他相关问题的研究。 课题组将一系列不同的图修正问题分为边删除问题、边添加问题和边编辑问题三种类型分别进行了深入研究。对于边删除问题，我们分别对3-Leaf Power边删除问题、Thereshold边删除问题和Co-trivially Perfect边删除问题进行了研究，并相应地提出了改进的固定参数可解算法。对于边添加问题，我们主要对Proper Interval 边添加问题和3-Leaf Power边添加问题分别进行了研究，并相应地提出了时间复杂度明显改进的固定参数可解算法。对于边编辑问题，课题组着重对Cograph 边编辑问题进行了研究。我们首次证明了该问题的计算复杂性是NP-完全的，解决了一个保持近二十年一直悬而未定的难题。同时我们对该问题首次提出了一个非平凡的固定参数可解算法。在核心化算法研究方面，课题组着重对平面图上连通支配集问题进行了深入研究。我们提出了一种区域分解扩展技术，在此基础上得到了该问题的一个大小不超过130k的核，肯定地回答了一个开放性问题。 在同类问题算法设计技术的规律性探究方面，课题组着重对分支策略进行了深入研究。特别地，对目标图类含有多个禁戒导出子图的边删除和边添加问题，我们首次提出了一种基于不同禁戒导出子图之间内在结构关系的链式分支策略。这一策略是参数计算分支技术中继基于邻居扩展策略、目标图类松弛策略之后的又一种新的分支策略，是参数计算技术的一个重要发展。 课题组同时还运用图修正问题参数化算法设计的一些相关技术对带权的Matching, Packing问题和图P2-packing 问题进行了研究，并得到了明显改进的固定参数可解算法。 项目的研究成果为一批NP难解的图修正问题提供了实际有效的新处理途径，对图修正问题在实际工程中的应用起到很大的促进作用。同时，研究成果丰富和发展了参数计算理论及技术。