摘要：图修改问题是一类经典的NP难解问题,在计算生物学、机器学习、蛋白质内聚发现和网络设计等众多领域都有着广泛的应用。在过去的几十年中,图修改问题得到了国内外学者的广泛研究。本文分别从设计问题的固定参数可解算法、证明问题的计算复杂性以及问题的核心化三个方面对2-Club簇图顶点删除问题、d-MDEAT问题和d-A2VDBPT问题进行了研究。从设计问题的固定参数可解算法角度,本文主要研究了2-Club簇图顶点删除问题的固定参数可解算法。本文首先通过分析问题实例的结构特征,提出了一些简化规则,并综合应用自底向上和自顶向下的分支搜索技术提出了时间复杂度为O*(3.24k)的固定参数可解算法,改进了目前文献中最好的结果O*(3.31k)。同时,本文将自顶向下的分支搜索技术应用到cograph顶点删除问题上,提出了时问复杂度为O*(3.06k)的固定参数可解算法,改进了目前文献中最好的结果O*(3.12k)。从计算复杂性和核心化角度,本文研究了一般性d-MDEAT问题的计算复杂性和d-MDEAT问题的核心化。本文通过将参数化顶点覆盖问题在多项式时间内规约到一般性d-MDEAT问题,首次证明当d≥4时,一般性d-MDEAT问题是NP-完全的。然后对d-MDEAT问题实例应用简单的核心化规则,证明d-MDEAT问题有一个大小为(3k+1)·(3k)d/(3k-1)+1的多项式核,因此本文首次证明d-MDEAT问题是固定参数可解的。以上证明解决了MDEA问题在树上是否为NP-完全问题的开放问题,完善了这个问题的计算复杂性研究。从核心化角度,本文研究了d-A2VDBPT问题的核心化。其中,d-A2VDBPT问题已被证明是NP-完全的,本文首次证明d-A2VDBPT问题有一个大小为4kd+8k的多项式核,因此d-A2VDBPT问题也是固定参数可解的。图6幅,表1个,参考文献63篇。