# Definition of k-set cover

I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from this article) and in their proof they reduce the k-SAT problem to the k-set cover problem. But their definition of the problem seems to be different from the definition found in other articles where the problem is simply the normal set cover with the addition that each set is limited to contain a maximum of k elements from the universe, as can be seen in eg. this description from Führer and Yu (taken from this article): The solution to this problem then consists of a collection of sets whose union covers the universe. But IPZ states the problem in this way: and in that, the solution is defined as a set C that contains at least one element from each of the sets S in $\mathscr{S}$. It is not stated that the collection of sets necessarily covers the universe. Finding a C of size |$\mathscr{S}$| is therefore trivial and finding a minimal C corresponds to finding elements that overlap different sets from $\mathscr{S}$ in the best possible way.

After this lengthy intro my question is this: Am I somehow not reading the definition given by IPZ correctly and is it just an other way of stating the same problem? Or is this two different problems that unfortunately has been given the same title?

• It's the same problem. You may assume wlog that the union of all sets in $\cal S$ equals the universe $U$ (as otherwise $U$ cannot be covered and you would have a trivial NO-instance). – Gamow Mar 24 '18 at 16:58
• But the second definition does not ask for $U$ to be covered, but for "$C \cap S = \emptyset$ for each $S \in \mathscr{S}$". I can only get this to mean that all $C$ should just overlap each $S$ in at least one element, but not cover the whole universe. $C$ is a set of elements, not a set of sets, so for $C$ to cover the whole universe, we would only have the trivial solution $C = \{x_1, ...,x_n\}$. – AstridNeu Mar 25 '18 at 11:20

• BTW, this hitting set formulation is equivalent to set cover where every element appears in at most $k$ sets, which is still a little different from what Fuehrer and Yu call "$k$-set cover". For example, according to Fuehrer and Yu, "2-set cover" is min edge cover, while according to IPZ "2-set cover" is min vertex cover. – Sasho Nikolov Mar 30 '18 at 22:50
• You can transform an instance $S_1, \ldots, S_m\subseteq [n]$ of hitting set where $|S_i| \le k$ for all $i$, to the instance $T_1, \ldots, T_n \subseteq [m]$ of set cover where $T_j = \{i: j \in S_i\}$. A subset $C \subseteq [n]$ hits all sets $S_i$ if and only if $\{T_j: j \in C\}$ is a set cover. Notice that $|\{j: i \in T_j\}| = |S_i| \le k$. When $k=2$ the hitting set problem is equivalent to vertex cover (i.e. the $S_i$ are the edges of the graph). – Sasho Nikolov Apr 1 '18 at 23:48