Fixed-parameter algorithms for hitting set problems. (c2006)

Abstract

The Hitting Set problem received a great deal of attention lately due to its plethora of applications in scientific domains. Many Algorithms have been developed to solve this problem by targeting the reduction of the worst-case run time. The most recent proposed algorithm employs a technique called pseudo-kernelization, introduced by F. Abu Khzam. Pseudo-kernelization seeks to find favorable conditions whose presence leads to a faster search strategy, and whose absence leads to a better reduction of the problem instance. When applied to the 3-Hitting Set problem, it provides a great improvement over the previously known algorithms. In this paper, we consider the algorithm ofH. Fernau, which has the best worst-case run time. We show that combining the methods used in Fernau's algorithm and the pseudokernelization technique gives the best run times for 3-Hitting Set. We provide empirical evidence that supports this claim. Moreover, we show how applying pseudo-kernelization to the general d-Hitting Set problem provides an improvement over the previously developed algorithms.