Parameterized algorithmics for d-Hitting Set

Abstract

Based on the methodology we presented in earlier work on parameterized algorithms for 3-Hitting Set, we develop simple search tree-based algorithms for d-Hitting Set. We considerably improve on the bounds that were elsewhere derived for these problems.

Keywords:

• Hitting Set problems
• parameterized algorithms
• analysis of search tree algorithms

2010 AMS Subject Classifications :

• 68Q25
• 90C27
• 05C65

Acknowledgements

We thank the referees for their scholastic labours.

Notes

Some doubts concerning the validity of this result are discussed on the homepage of Wahlström.

The values computed this way will also satisfy other assumptions made above, as for example Equation (8).

As suggested by one of the referees.

Additional information

Notes on contributors

Henning Fernau

Most of the work on this material has been done while the author was with University of Tübingen, Germany, as well as with University of Hertfordshire, Hatfield, UK, although it all started (and it was all finished) while he was working at the University of Newcastle, Australia. The according support is gratefully acknowledged.