Timeline for Definition of k-set cover
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2018 at 2:46 | comment | added | Yixin Cao | @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. | |
| Apr 1, 2018 at 23:48 | comment | added | Sasho Nikolov | 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). | |
| Apr 1, 2018 at 19:32 | comment | added | AstridNeu | @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. | |
| Apr 1, 2018 at 19:25 | comment | added | AstridNeu | @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? | |
| Apr 1, 2018 at 13:58 | vote | accept | AstridNeu | ||
| Mar 30, 2018 at 22:50 | comment | added | Sasho Nikolov | 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. | |
| Mar 30, 2018 at 13:11 | history | answered | Yixin Cao | CC BY-SA 3.0 |