<p>This is FPT, because by interchanging sets with elements in the usual way, this is just set cover where the universe size <span class="math-container">$n$</span> is the parameter. This is known to be FPT (see e.g. the <a href="https://parameterized-algorithms.mimuw.edu.pl/" rel="nofollow noreferrer">parameterized algorithms book</a>, Chapter 6)</p>

CC BY-SA 4.0
2022-06-04T16:12:20.890Z
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?
Noel Arteche
CC BY-SA 4.0
2022-05-05T23:06:47.200Z
2022-05-05T23:06:47.200Z
daniello
<p>The Hitting Set problem, when parameterized by the size <span class="math-container">$k$</span> of the hitting set, is <strong>W</strong>[2]-hard. Is it also <strong>W</strong>[2]-hard when parameterized by <span class="math-container">$k$</span> plus the number of subsets in the instance?</p>
<p>I explain in a bit more detail. A Hitting Set instance consists of a universe <span class="math-container">$U = \{ u_1, \dots, u_n\}$</span> and a set <span class="math-container">$S = \{ S_1, \dots, S_m\} \subseteq \mathcal{P}(U)$</span> together with a natural number <span class="math-container">$k$</span>. A hitting set is a set <span class="math-container">$H \subseteq U$</span> of size <span class="math-container">$k$</span> such that for each <span class="math-container">$i \in [m]$</span>, <span class="math-container">$H \cap S_i \neq \emptyset$</span>. We know that Hitting Set parameteized by <span class="math-container">$k$</span> is <strong>W</strong>[2]-complete. Is it still <strong>W</strong>[2]-hard when parameterized by <span class="math-container">$k + |S|?$</span></p>

<cc.complexity-theory><reductions><parameterized-complexity>
Parameterized complexity of Hitting Set with slightly bigger parameter
Noel Arteche
# Parameterized complexity of Hitting Set with slightly bigger parameter

(Asked by: username_0 on 2022-05-05)

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|?$

**Tags:** cc.complexity-theory, reductions, parameterized-complexity

---

## 1 answers

### Answer by username_1 on 2022-05-05. Score: 2 | Accepted answer

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](https://parameterized-algorithms.mimuw.edu.pl/), Chapter 6)

> **Comments:**
> **username_0**: 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?  

---

