0
$\begingroup$

The Hitting Set problem, when parameterized by the size $k$ of the hitting set, is W[2]-hard. Is it also W[2]-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[2]-complete. Is it still W[2]-hard when parameterized by $k + |S|?$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Noel Arteche
    Commented Jun 4, 2022 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.