# Parameterized complexity of Hitting Set with slightly bigger parameter

The Hitting Set problem, when parameterized by the size $$k$$ of the hitting set, is W-hard. Is it also W-hard when parameterized by $$k$$ plus the number of subsets in the instance?

I explain in a bit more detail. A Hitting Set instance consists of a universe $$U = \{ u_1, \dots, u_n\}$$ and a set $$S = \{ S_1, \dots, S_m\} \subseteq \mathcal{P}(U)$$ together with a natural number $$k$$. A hitting set is a set $$H \subseteq U$$ of size $$k$$ such that for each $$i \in [m]$$, $$H \cap S_i \neq \emptyset$$. We know that Hitting Set parameteized by $$k$$ is W-complete. Is it still W-hard when parameterized by $$k + |S|?$$

This is FPT, because by interchanging sets with elements in the usual way, this is just set cover where the universe size $$n$$ is the parameter. This is known to be FPT (see e.g. the parameterized algorithms book, Chapter 6)
• Related to this: do we know some bound on the minimal number of sets over all equivalent Hitting Set instances? That is, if I have an instance $(U, S, k)$ of Hitting Set with $n$ elements in the universe and $m = |S|$ sets and I find an equivalent instance $(U, S_0, k)$ (i.e. they have the same hitting sets) such that $|S_0|$ is minimal over all equivalent instances... can we say something about $|S_0|$? Is it perhaps bounded by some function of $k$? I would imagine that if we parameterize by $|S_0|$ instead of by $|S|$ then the problem becomes hard? Jun 4, 2022 at 16:12