Research On Parameterized Algorithms For Several NP-hard Problems

NP-hard problems are the focus area in theoretical computer science. Work on the fixed-parameter tractable algorithms for them has become a new research topic in theoretical computer science in recent years.In this thesis, we study several classical NP-hard problems, such as Matching,Packing,Maximum Cut and MultiCut. In discovering some hidden structure characters of these problems, we develop a series of fixed-parameter tractable algorithms by employing the techniques in parameterized computation.The weighted m-D Matching and weighted m-Set Packing problems are usually solved through approximation algorithms. In this thesis, we define the parameterized versions of these problems and study their algorithms. For the weighted m-Set Packing problem, we develop a parameterized algorithm of running time O(12.2mknO(1)), which is based on the recently improved color-coding technology and dynamic programming. By refining the techniques, we also develop a more efficient parameterized algorithm of running time O(12.2(m-1)knO(1)) for the weighted m-D Matching problem, which is a restricted version of the weighted m-Set Packing. On the basis of the study above, we also present a fixed-parameter enumeration algorithm of running time O(5.483kkn2z) for the weighted 3-D Matching problem, where z is the number of optimal k-machtings to be enumerated.The computational complexity of the parameterized 3-D Matching counting problem has been open. It is conjectured that the problem is not fixed-parameter tractable. In this thesis, we present a fixed-parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers s andδ, and a given set S of n triples and an integer k, produces a number N in time O(5.483kn2ln(2/8)/ε2) such that Prob[(1-ε)NO≤N≤(1+ε)N0]≥1-δ, where No is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and Monte-Carlo self-adjusting coverage algorithm developed by Karp, Luby and Madras.The maximum cut problem is also studied in terms of parameterized computational complexity theory. After defining the parameterized version of the problem, we present a randomized parameterized algorithm based on random separation. The algorithm randomly bipartitions the vertex set of a given instance for [ln(1/ε)] x2k (0<ε<1) times, and returns a k-cut of maximum weight as the output, so that it can obtain the solution with probability at least 1-εin time O*(ln(l/ε)2k). On the basis of the study above, mainly employing the recent improved (n,k)-universal set techniques, we also propose a deterministic parameterized algorithm of running time O*(22k+12log2(2k)), which shows that the maximum cut problem is fixed-parameter tractable.The MaxCut problem parametrizing above guaranteed values is studied further, and its kernel and algorithm are improved. Based on the analysis of some structure characters about the problem, we present a lower bound of (?) for its kernel based on vertex, and a new kernel of 8k2+10k+2 based on edge, which improves the previous one of 16k2-18k+6. On the basis of the study above, we also propose a parameterized algorithm for the problem of running time O*(8.999), improving the previous one of time O*(16k).The Multicut problem is for a given graph and a given collection of terminal pairs to find a vertex set of minimum size such that the two terminals in any pair are not connected after deletion of this vertex set. By employing the strategy of set partition and the improved results of another related problem, we propose, based on the discovery of some hidden structure characters, a parameterized algorithm for the problem of running time O*((?)4k), in which l denotes the number of terminal pairs and k denotes the number of removed vertices. This algorithm significantly improves the previous one of time O*(2klkk4k3).