Fixed-Parameter Algorithms For D-Hitting Set Problems

The HITTING SET problem is one of classic computational problems in combina-torics. Its task is to find a set D C S with a given cardinality such that D∩B(?)θfor all B∈C, that is, D is a hitting set, where S is a finite set and C is a collection of subsets of S, i.e., C(?)P(S). In terms of hypergraph theory, (S, C) could be regarded as a hypergraph H=(V,ε) such that S and C correspond to the vertex set V and the hyperedge setε, respectively. In this sense, a hitting set is equivalent to a vertex cover of H, and the d-HITTING SET problem is the same as the VERTEX COVER problem on d-uniform hypergraphs in which every hyperedge consists of d many vertices.It is well known that both the HITTING SET problem and every d-HITTING SET problem for d≥2 are NP-complete. Hence, there is no polynomial time algorithm to solve them unless P=NP. However, if we look at these problems from the viewpoint of parameterized theory, the former problem is W[2]-complete and all the latter ones are fixed-parameter tractable.Parameterized complexity theory is a young branch of complexity theory. It has developed rapidly during the last 15 to 20 years and made its way into various areas of computer science including database theory, artificial intelligence, and computational biology. Parameterized complexity theory measures complexity not only in terms of the input size, but in addition in terms of a parameter, which is a numerical value that may depend on the input in arbitrary way. It relaxes the classical notion of tractability, polynomial time solvability, by admitting algorithms whose "nonpolynomial behavior" is confined by the parameter. Complementing the notion of fixed-parameter tractabil-ity, parameterized intractability is built on a weakened notion of tractability and a corresponding notion of reduction. By taking a more refined view of complexity of the problems, the world of parameterized intractability is expectedly much more complex than that of the classical complexity which is overwhelmingly dominated by the P-NP dichotomy.In this thesis, we study fixed-parameter algorithms of d-HITTING SET problems and our main results are as follows:We begin with many kernelizations of the VERTEX COVER problem on graphs in- eluding reduction rules, crown reduction, linear programming and network flow. Based on those techniques, we study the corresponding feasible kernelizations on d-HITTING SET problems for d≥2 systematically.We study the VERTEX COVER problem on d-uniform hypergraphs for d≥2 with bounded degree l≥3. We show that this problem is NP-complete. More-over, we propose two kernelizations with kernel sizes l·k and ((d-1)·l+1)·k for it, respectively. In addition, we consider its dual problem——the INDEPEN-DENT SET problem and give two kernelizations with corresponding kernel sizes for it on this type of hypergraphs.We study the VERTEX COVER problem on planar d-uniform hypergraphs for d≥2 and prove its NP-completeness. By the D-region decomposition technique, we provide a kernelization with kernel size 67k for the VERTEX COVER problem on planar 3-uniform hypergraphs. For the dual, we give a kernelization with kernel size 12k on this type of hypergraphs. Furthermore, we show that it is impossible to get a kernel of size O(k) for the VERTEX COVER problem on planar d-uniform hypergraphs by a similar technique for d> 4.We consider the VERTEX COVER problem on quasi-regularizable d-uniform hy-pergraphs for d> 2. We show that it is NP-complete. Using linear programming, we propose a kernelization with kernel size d·k for this problem. On the other hand, we prove that the INDEPENDENT SET problem is W[l]-complete on this type of hypergraphs.We deduce lower bounds on the kernel size for some NP-complete problems including the VERTEX COVER problem, the INDEPENDENT SET problem and the DOMINATING SET problem on several special types of d-uniform hypergraphs for d> 2 from the parametric duality.We investigate bounded search tree algorithms for the d-HITTING SET problem with d> 2. We improve the running time of bounded search tree algorithms for the VERTEX COVER problem on graphs. Additionally, we characterize the VERTEX COVER problem on 3-uniform hypergraphs. Using heuristic branch-ing rules and quasi-convex programming, we also improve the running time of bounded search tree algorithms for the VERTEX COVER problem on 3-uniform hypergraphs.In summary, we systematically study fixed-parameter algorithms of d-HITTING SET problems under the framework of parameterized complexity and made some con-tributions to the research on d-HITTING SET problems and parameterized complexity.