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 3-Hitting Set. We concentrate on algorithms which are easy to implement, in contrast with the highly sophisticated algorithms which have been designed previously to improve on the exponential base in the algorithms. However, this necessitates a more complex algorithm analysis based on a so-called auxiliary parameter, a technique which we believe can be used in other circumstances, as well.