The Minimum Weight Connected Vertex Cover P₃ Problem

The vertex cover problem of graphs is a popular topic in graph theory. Given a graph G=(V. E) and a positive integer k?|V|, the question in VC is whether there exists a vertex cover(ing) of size at most k in G, i.e., a subset S C V such that |S|< k and every edge of E has an end vertex in S. Given a connected and weighted graph G = (V, E) with each vertex v having a nonnegative weight w(v), the minimum weighted vertex cover problem is required to find a vertex cover subset of vertices of the graph with minimum total weight. This problem is a special case of the vertex deletion problem:to find a minimum weight set of vertices whose deletion gives a graph satisfying a given property. For example, the feedback vertex set problem is to find a minimum weight set S of vertices in V(G) such that the graph G[V - S] induced by V - S has no cycle. These problems have applications in many areas, such as network design, network optimization, etc. Motivated by these observations, we introduce the minimum weighted connected vertex cover Pk problem:to find a minimum weight vertex cover set S C V such that the graph G[V\S] has no Pk as a subgraph, where Pk is the path on k vertices, and the subgraph G[S] of G induced by S is required to be connected. In this thesis, we consider the case that k= 3.Bostjan (2011) proved that minimum vertex cover Pk problem is NP-complete for any fixed integer k?2, Tu and Zhou (2011) gave a 2-approximation minimum weight vertex cover P3 set by using the primal-dual method. With the condition of connectivity, Liu (2013) et al. present a PTAS for the minimum k-path connected vertex cover problem in unit disk graphs. In this thesis, we consider the minimum vertex cover P3 problem in the conditions of connectivity and the weighted graph.The thesis has four chapters. In Chapter 1, we introduce some notations, gen-eral fundamental principles, known conclusions of the vertex cover P3 problem, and present our main methods and main results. In Chapter 2, we first prove the complex-itv result in grid eraph. After presenting the complexity proof, we give the constant- factor approximation result that can be used in our algorithm, and then we give a polynomial time approximation scheme (PTAS) for the minimum weighted connect-ed vertex cover P3 problem (MWCVCP3) if we assume that the problem is c-local and the unit disk graphs have minimum degree at least two. In Chapter 3, we give the first polynomial time approximation scheme for MWCVCP3 in unit ball graphs under the assumption that the problem with smooth weights is weak c-local. At the end of this thesis, we propose some questions for further research.