Research On Parameterized Algorithms And Kernelizations For Several Graph Modification Problems

Abstract:Graph modification problems are classical NP-hard problems, and there are many important applications of these problems in many fields, such as computational biology, machine learning, analyzing protein clusters and network designing. In the last decades, graph modification problems have received extensive attentions in the graph theory community. This paper makes a research on three problems:2-Club cluster vertex deletion, d-MDEAT and d-A2VDBPT in the aspects of fixed-parameterized tractable algorithms, computational complexity and kernelizations。In this paper, we study the2-Club cluster vertex deletion problem from the fixed-parameterized tractable algorithm point of view. By analyzing the structure of the problem instance, we advocate some reduction rules according to some structures of the2-Club cluster graph instances. Then, we present for the problem a fixed-parameterized tractable algorithm with running time O*(3.24k) by combining the top-down and bottom-up branching search approaches, which improves the previous best result O*(3.31k). We also apply the top-down branching search approach to cograph vertex deletion problem, and present a fixed-parameterized tractable algorithm with running time O*(3.06k), which also improves the previous best result0*(3.12k).We study the NP-completeness of the generalization d-MDEAT problem and the kernel of the problem d-MDEAT. In this paper, we prove that the generalization d-MDEAT problem is NP-complete when d≥4by a polynomial reduction from the parameterized vertex cover problem and give a polynomial kernel of size(3k+1)-(3k)d/(3k-1)+1for the problem d-MDEAT by applying one reduction rule. Therefore, the problem d-MDEAT is fixed-parameterized tractable. The above proof solves an open problem and is an important complement to the study of computational complexity for the problem.We also study the problem d-A2VDBPT from the kernel point of view. The problem d-A2VDBPT had already been proved to be NP-complete. In this paper, we also give a polynomial kernel of size 4kd+8k for the problem. Therefore, the problem d-A2VDBPT is also fixed-parameterized tractable. There are six figures, one table and sixty-three references in this thesis.