0
$\begingroup$

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):

Furer,Yu

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

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Gamow
    Commented Mar 24, 2018 at 16:58
  • $\begingroup$ 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\}$. $\endgroup$
    – AstridNeu
    Commented Mar 25, 2018 at 11:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Mar 30, 2018 at 22:50
  • $\begingroup$ @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? $\endgroup$
    – AstridNeu
    Commented Apr 1, 2018 at 19:25
  • $\begingroup$ @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. $\endgroup$
    – AstridNeu
    Commented Apr 1, 2018 at 19:32
  • $\begingroup$ 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). $\endgroup$
    – Sasho Nikolov
    Commented Apr 1, 2018 at 23:48
  • $\begingroup$ @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. $\endgroup$
    – Yixin Cao
    Commented Apr 2, 2018 at 2:46

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.