Pseudo-Kernelization - Abu-Khzam, Faisal N. (2007)
Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Pseudo-kernelization applies well to hitting set problems. It can be used either to improve the search tree size of a 3-Hitting-Set algorithm from O*(2.179k) to O*(2.05k), or to improve the kernel size from k3 to 27k. In this paper the parameterized 3-Hitting-Set and Face Cover problems are used as typical examples.