Abstract:
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.
Citation:
Abu-Khzam, F. N. (2007). Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. Theory of Computing Systems, 41(3), 399-410.
