| At first we give a brief introduction to the classical complexity theory, then descriptions about parameterized complexity. In the second part we give out the basic concepts and definitions about parameterized theory, and FPT. The main technique of kernelization, reduction and search tree, some examples of those methods and analysis also could be found in this part. The third part that we use two sets of reductions rule to design the algorithm for dominating set on planar graph, give out the running time of the algorithm, and the experiment results and analysis.Complexity theory is the foundation of computer science. It could be used to conduct the design of algorithm besides the value of theory. Complexity theory is used to classify the problems which could be solved by computer the class-P and NP. Reduction leads to the amazing class NP-complete, which means it could not be solved in polynomial time and have to resolve to random algorithm and approximation algorithm.Dominating Set in graphs is considered to be among the most important problems in combinatorial optimization, which is NP-complete in classical complexity theory. Even from the point of Fixed-Parameter Tractable view, this problem is well-known to be W[2]-complete for general graph, which means that it is impossible to design the algorithm solving the problem with running time f (k)no(1). We investigate the version where we are given a planar graph G=(V, E), a parameter k and ask for a set of vertices of size at most k that dominate all other vertices. It is known to be FPT when restricted to planar graph. We also give the search tree algorithm based on two sets of reduction rules and the experiments to show the efficiency between different sets of reduction rules. We use C++and LEDA library to accomplish the algorithm and give experiments, wish it would be helpful to those interesting to FPT.We hope this paper would be useful to those who want to learn the theory and techniques about FPT. |
PDF Full Text Request