To Determine The Parameters Of The Vertex Cover Problem Solution Algorithm Research

Parameterized complexity theory provides a framework for a refined analysis of hard algorithmic problems. Parameterized complexity theory is a fairly new branch of complexity theory. It was developed by Downey and Fellows in a series of ground breaking articles in the early 1990s. In these articles, Downey and Fellows defined the notion of fixed-parameter tractability, came up with suitable notions of reductions, defined the most important complexity classes, and proved a number of fundamental completeness results. Since then, numerous other researchers have contributed to the theory. Downey and Fellows' 1998 monograph [1] gives a fairly complete picture of the theory then. The development has not slowed down since then, quite to contrary. Though, parameterized complexity attracted more and more theoretical computer scientists attention, little theoretical computer scientist do research in this field. It is hard to find paper related to this field written in Chinese. Therefore, my professor and I feel that the field has matured to a degree that it deserves a comprehensive introduction, which we hope to begin by this article.This thesis focuses on parameterized tractability problems. Parameterized tractability includes two important topics. One is fixed parameterized tractability algorithm design. Another one is kernelization. These topics were covered in chapter 2, chapter 3 and chapter 4.In chapter 1, the thesis introduced the background of the parameterized complexity, and recently research progress. In this chapter, the main topic is to show the difference between parameterized complexity theory and classical complexity theory. Parameterized complexity theory concerned why the problem is hard. In the other hand, classical complexity theory concerned whether the problem is hard. Because in parameterized complexity theory, the researchers assume many natural problems as hard problem.In chapter 2, the thesis introduced the basic definitions of the parameterized tractability, including fixed parameterized tractable, fixed parameterized tractability reduction, and kernelization. Because parameterized tractable enlarge the definition of the tractability, so firstly the thesis introduced the definition of the fixed parameterized tractability. In addition, parameterized tractability enlarge the definition of the tractability, thus the turning reduction can not used in the parameterized theory. Then the thesis defined the appropriate reduction—fixed parameterized tractability reduction. Kernelization is another important concept in the parameterized tractability theory, because a parameterized problem has fixed parameterized tractability algorithm if and only if this problem can be kernelized. In the end of this chapter, the thesis answered a well known open question in the parameterized complexity. The open problem is whether every fixed parameterized tractability problems has a linear sized kernel. Unfortunately, the answer to this problem is "no" and the thesis gave the counter example in the end of the chapter 2.In chapter 3, the thesis introduced the writer's research result on the kernelization algorithm of the vertex cover problem. In the first part of this chapter, the thesis introduced three different kernelization algorithms and given the disadvantage of these algorithms. Then the thesis showed the writer's kernelization algorithm. The algorithms is proved get the 2k size kernel, which is the lower bound of the problem, and the running time is more efficient.In chapter 4, the thesis showed the writer's research result on the fixed parameterized problems. The results are two fixed parameterized algorithms solving two variants of the vertex cover problem---connected vertex cover problem and weighted tree vertex cover problem. The connected vertex cover problem required the vertices in the vertex cover should be connected in the original graph. And weighted tree vertex cover required the vertices in the vertex cover could construct a tree using the edges in the original graph and the total weight should under some constraints. The thesis proved these two problem are fixed parameterized tractable and the running time of these two problems are the best results right now. In chapter 5, the thesis reviewed the whole contents of the thesis and gave the future research interests.