The Parameterized Vertex Cover Problem And The Minimum Vertex Cover Problem

The Parameterized Vertex Cover Problem (short as PVC or VC) and the Minimum Vertex Cover Problem (short as Min-VC) are two important NP-hard problems. Up to now, there has been a remarkable line of research in the study of algorithms of the problems including kernelization algorithms for PVC.Among the kernelization algorithms, Crown Reduction and NT algorithm are two major methods which have long been thought to be different from each other.In this paper, a survey on kernelization algorithms for VC is firstly presented in order to establish a synthetic understanding of kernelization techniques aiming at reducing the size of instances of the PVC problem. Base on the recently discovered fact that NT algorithm can be used to construct a Crown Reduction for a given graph, we do further study on the relationship of the two methods. We give out a theorem to determine a crown-free graph. And by distinguishing proper and non-proper crowns, we prove that NT algorithm can remove all proper crowns. We also develop an expanded NT algorithm to remove all crowns including proper and nonproper ones. And this polynomial algorithm can be used to determine crown-free graphs.Moreover, a special case of Min-VC is studied. We assume that if the size of the minimum vertex cover of a graph is exactly half of the total graph (i.e., k=n/2), the minimum vertex cover can be found in polynomial time, which is markedly better than the best now exponential algorithm. By taking this into account we develop deterministic and randomized algorithms solving problems in which k is slightly larger than n/2, which results in a wider range of applications.Finally, this paper sums up the whole study work on PVC and min-VC problem and discusses the further work on the problems.