1
$\begingroup$

I've come with an idea for reduction from the set-cover problem to the vertex-cover problem, But I'm not sure if this reduction is correct. I saw in this post's comments that "There cannot be a nice reduction of this sort".

Consider the set of $S$ to be $S_1,...,S_n$ where the element of $S$ is $s_1, ..., s_m$. In the graph $G=(V,E)$ for each $S_i$ there is a vertex, and an edge from $S_i$ to $S_j$ will be iff there is some element $x\in S_i \land x\in S_j$.

is this reduction even right?

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Jun 1 '17 at 10:19
  • 1
    $\begingroup$ If you want to know if a reduction is correct, try to prove it. If that doesn't work, try to find a counterexample. If that doesn't work, try to find a proof based on what you learnt while failing to construct a counterexample. If that doesn't work, try to find a counterexample based on what you learnt while failing for the second time to produce a proof. If that doesn't work... Well, then maybe post here and explain what you tried and why it didn't seem to work. $\endgroup$ – David Richerby Jun 1 '17 at 10:21
5
$\begingroup$

No, since ​ {{0,1},{1}} ​ and ​ {{0,1},{1,2}} ​ yield isomorphic graphs
but the sizes of their minimum set covers are different.

$\endgroup$
1
$\begingroup$

Another reason which may help understanding why this reduction (from Set Cover to Vertex Cover) is not possible is as follows. See the slide below (taken from Kleinberg, Tardos).

Reducing Vertex Cover to Set Cover

Here, a single element (represented as an edge) appears in exactly two sets (nodes). If this was not the case (and an element appeared in less than or more than two sets), drawing such a graph would not be possible (an edge can only have exactly two ends (nodes)).

Going from Vertex Cover to Set Cover is easy because Vertex Cover is applied on a graph that already exists (we do not need to draw a graph).

Edit (by Discrete lizard): Constructing such a graph from arbitrary sets is possible, but then there must be multiple edges representing the same element. The construction of a graph fails for another reason: there may be at most one edge for every pair of nodes, which need not be the case for arbitrary sets.

$\endgroup$
  • $\begingroup$ 'This is not really a good answer'. Then why post it? You should have more confidence in your answer. Also, you may clarify that constructing such a graph from arbitrary sets is possible, but then there must be multiple edges representing the same element. The construction of a graph fails for another reason: there may be at most one edge for every pair of nodes, which need not be the case for arbitrary sets. $\endgroup$ – Discrete lizard Jan 30 '18 at 20:01
  • $\begingroup$ Thanks for the addition, I will edit and add it up there :) $\endgroup$ – U. Muneeb Jan 30 '18 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.