Electronic Colloquium on Computational Complexity, Report No. 73 (2004) A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set

In this paper, we show how to systematically improve on parameterized algorithms and their analysis, focusing on search-tree based algorithms for d-Hitting Set, especially for d = 3. We concentrate on algorithms which are easy to implement, in contrast with the highly sophisticated algorithms which have been elsewhere designed to improve on the exponential base in the algorithms. The algorithm analysis is based on a novel way to exploit a so-called auxiliary parameter, a technique which we believe can be used in other circumstances, as well.