Approximation Algorithms For Vertex Deletion Problems

In this thesis,we focus on studying approximation algorithms and parametrized algorithms for vertex deletion problem.The vertex deletion problem is an important research problem in the field of theoretical computer science,and has a wide application in the real world.This thesis consists of the following four parts:In the first part,for a given graph G,the minimum weight connected-k-subgraph cover problem(MinWCkSC)is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C.Previously,Zhang et al.[93]presented a(k-1)-approximation algorithm for MinWCkSC under the assumption that the girth of G,which is the length of a shortest cycle of G,is at least k.In this paper,we improve this result by showing that(k-1)-approximation can be achieved when the girth requirement is relaxed from k to 2k/3.In the second part,we study the minimum weight connected-k-subgraph cover prob-lem with connectivity requirement(MinWCkSCcon),the goal of which is to find a mini-mum weight vertex set C such that every connected subgraph on k vertices of G contains at least one vertex of C,and the induced graph G[C]is connected.For k=4,We present a two-stage approximation algorithm for MinWC4SCcon on graphs without vertex of de-gree 2,achieving approximation ratio at most(ln(?max)+7+ln3),where ?max denote the maximum degree of graph G.In the third part,we study the minimum(connected)k-bounded-degree node deletion problem(Min(C)kBDND).For a connected graph G,and a constant k,a vertex set C(?)V(G)is a kBDND-set if the maximum degree of graph G-C is at most k.If furthermore,the subgraph of G induced by C is connected,then C is a CkBDND-set.The goal of MinkBDND(resp.MinCkBDND)is to find a kBDND-set(resp.CkBDND-set)with the minimum size.This paper presents a(1+?)and a 3.76-approximation algorithm for MinkBDND and MinCkBDND on unit disk graphs,respectively,where 0<?<1 is an arbitrary constant.In the fourth part,we first present a PTAS for MinCkSC in H-minor-free graphs where H is a fixed graph with a constant number of vertices.Then we design an O(?(2(k-1)?)3?)|V| time FPT algorithm for MinCkSCcon on graphs with bounded treewith ?,where k is a constant,and an O((?))time FPT algorithm for MinCkSCcon on H-minor free graphs,where t is an upper bound of solution size.