Maximum Vertex Cover In Trees

Combinatorial Optimization is an old and important subject, that is related to our daily life. Among the many combinatorial problems, in this paper, we consider Vertex Cover Problems.Different from the well known Minimum Vertex Cover problem, that covers all edges with a minimum number of vertices in a graph G=(V, E), we deal with a dual version, called Maximum Vertex Cover, in which one is asked to pick k vertices covering as many edges as possible, where k is a given positive integer.We can prove that the Maximum Vertex Cover Problem is an NP-hard problem, so we can not expect to find an optimal solution in polynomial time, unless P=NP. In this paper we just consider a special graph—tree, which is an interesting problem. For it we will design some approximation algorithms and analyze their performance.There are three chapters in this paper.In Chapter 1, we describe what is Combinatorial Optimization and give some knowledge about how to design and analyze an algorithm.In Chapter 2, we introduce the Minimum Vertex Cover Problem and present some known results about it.In Chapter 3, we describe the Maximum Vertex Cover in a tree. According the greedy idea we design two approximation algorithms. The approximation ratio of the first algorithm, called Fully Greedy, is 2, while the ratio of thesecond, called Dynamic Greedy, is 4/3.