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.
