<p>The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements.  You can find more information on the <a href="https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation" rel="nofollow noreferrer">wikipedia page</a>.</p>

CC BY-SA 3.0
2018-03-30T22:50:42.527Z
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
CC BY-SA 3.0
2018-04-01T19:25:02.270Z
@Yixin Cao: It makes perfectly sense that they are describing the hitting set problem. I did not see that. But then, why are they not just using the hitting set directly instead of calling it k-set cover, I wonder?
AstridNeu
CC BY-SA 3.0
2018-04-01T19:32:07.257Z
@Sasho Nikolov: I have given your comment a lot of thought, but I don't see why the hitting set formulation makes a limit of k sets that each element can appear in. Could I ask you for an elaboration? Also I do not understand your distinction between 'min edge cover' and 'min vertex cover' in this connection. Sorry for maybe failing to understand something that is obvious for someone more seasoned in the area.
AstridNeu
CC BY-SA 3.0
2018-04-01T23:48:52.020Z
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
CC BY-SA 3.0
2018-04-02T02:46:14.383Z
@AstridNeu I would not try to answer your question, because I don't have the answer or even any clue. But I suppose it doesn't really matter, right? A general comment is: the longer a paper has been written, the possibility that its notations are different from nowadays is higher.
Yixin Cao
CC BY-SA 3.0
2018-03-30T13:11:08.443Z
2018-03-30T13:11:08.443Z
Yixin Cao
<p>I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from <a href="https://ac.els-cdn.com/S002200000191774X/1-s2.0-S002200000191774X-main.pdf?_tid=f33bb445-b4c1-48c6-870d-18da87785bad&amp;acdnat=1521899595_b2d4474776d5b1163206a2c6374a7e28" rel="nofollow noreferrer">this article</a>) 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 <a href="https://arxiv.org/pdf/1109.3418.pdf" rel="nofollow noreferrer">this article</a>):</p>

<p><a href="https://i.sstatic.net/ovJ21.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ovJ21.png" alt="Furer,Yu"></a></p>

<p>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:</p>

<p><a href="https://i.sstatic.net/PzTEZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PzTEZ.png" alt="Impagliazzo, Paturi, Zane"></a></p>

<p>and in that, the solution is defined as a set <em>C</em> that contains at least one element from each of the sets <em>S</em> in $\mathscr{S}$. It is not stated that the collection of sets necessarily covers the universe. Finding a <em>C</em> of size |$\mathscr{S}$| is therefore trivial and finding a minimal <em>C</em> corresponds to finding elements that overlap different sets from $\mathscr{S}$ in the best possible way.</p>

<p>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?</p>

CC BY-SA 3.0
2018-03-24T16:58:32.167Z
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
CC BY-SA 3.0
2018-03-25T11:20:42.853Z
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
<set-cover><definitions>
Definition of k-set cover
AstridNeu
# Definition of k-set cover

(Asked by: username_0 on 2018-03-24)

I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from [this article](https://ac.els-cdn.com/S002200000191774X/1-s2.0-S002200000191774X-main.pdf?_tid=f33bb445-b4c1-48c6-870d-18da87785bad&acdnat=1521899595_b2d4474776d5b1163206a2c6374a7e28)) 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](https://arxiv.org/pdf/1109.3418.pdf)):

[![Furer,Yu](https://i.sstatic.net/ovJ21.png)](https://i.sstatic.net/ovJ21.png)

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:

[![Impagliazzo, Paturi, Zane](https://i.sstatic.net/PzTEZ.png)](https://i.sstatic.net/PzTEZ.png)

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?

**Tags:** set-cover, definitions

> **Comments:**
> **username_1**: 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).  
> **username_0**: 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\}$.  

---

## 1 answers

### Answer by username_2 on 2018-03-30. Score: 2 | Accepted answer

The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements. You can find more information on the [wikipedia page](https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation).

> **Comments:**
> **username_3**: 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.  
> **username_0**: @username_2: It makes perfectly sense that they are describing the hitting set problem. I did not see that. But then, why are they not just using the hitting set directly instead of calling it k-set cover, I wonder?  
> **username_0**: @username_3: I have given your comment a lot of thought, but I don't see why the hitting set formulation makes a limit of k sets that each element can appear in. Could I ask you for an elaboration? Also I do not understand your distinction between 'min edge cover' and 'min vertex cover' in this connection. Sorry for maybe failing to understand something that is obvious for someone more seasoned in the area.  
> **username_3**: 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).  
> **username_2**: @username_0 I would not try to answer your question, because I don't have the answer or even any clue. But I suppose it doesn't really matter, right? A general comment is: the longer a paper has been written, the possibility that its notations are different from nowadays is higher.  

---

