![[-]](/~ygleyzer/course.wiki/images/button-minus.gif)
Question 2: Si's inside Si's.
by guyrap - Saturday, 11 July 2009 17:49:09
Oh hai!
Say I've a set of 2 elements: "a" and "b".
I can has three setz over this set: {a} , {b}, {a,b}.
Does this mean I can say, that for k = 1,2,3, Set-Cover[{a},{b},{a,b}] = True? Since:
- For k=1: {a,b}
- For k=2: {a}U{a,b} or {b}U{a,b} or {a}U{b}
- For k=3: {a}U {b}U {a,b}.
In other words - is a set-cover legal if it has redundant sets? For a set-cover SC, we'll define elemnt S to be redundant if SC contains another element R, such that S is itself a subset of R, and is thus redundant (we can remove it and still cover the set since R covers everything S covers).
Say I've a set of 2 elements: "a" and "b".
I can has three setz over this set: {a} , {b}, {a,b}.
Does this mean I can say, that for k = 1,2,3, Set-Cover[{a},{b},{a,b}] = True? Since:
- For k=1: {a,b}
- For k=2: {a}U{a,b} or {b}U{a,b} or {a}U{b}
- For k=3: {a}U {b}U {a,b}.
In other words - is a set-cover legal if it has redundant sets? For a set-cover SC, we'll define elemnt S to be redundant if SC contains another element R, such that S is itself a subset of R, and is thus redundant (we can remove it and still cover the set since R covers everything S covers).
Re: Question 2: Si's inside Si's.
by guyrap - Monday, 13 July 2009 08:40:02
A short answer for a long question, I'd say!
If I've understood this "yes" - then for k=3, {a} U {b} U {a,b} is a legal set cover.
But in this case, we cannot find a base group of size k=3 , because we only have 2 vertices!
So the reduction won't work :,,,,((
For k=3: a set-cover of size 3 exists.
For k=3: a base set of size 3 doesn't exist.
Re: Question 2: Si's inside Si's.
by golansha - Monday, 13 July 2009 09:27:50
You understood well. Indeed the reduction (that you didn't fully describe) doesn't work...
If at first you don't succeed, try, try again.
If at first you don't succeed, try, try again.
Re: Question 2: Si's inside Si's.
by guyrap - Tuesday, 14 July 2009 10:48:20
OK, here we go again, trying:
For U={a}, can a set cover of size 2 be {a},{a} ?
That is - can I at least assume, that in my collection of subsets, no two subsets are equal?
This matters to me because sets can have 4 different relations between them:
1) They are strange (imagine a Venn diagram with two circles apart from each other).
2) They are the same (imagine a circle on top of a circle).
3) They share some elements, and don't share other elements (intersection is nonempty: two circles in love).
4) One contains the other (little circle inside BIG circle).
I need to know if the 2nd option is relevant to a collection I might receive in the Set-Cover definition.
For U={a}, can a set cover of size 2 be {a},{a} ?
That is - can I at least assume, that in my collection of subsets, no two subsets are equal?
This matters to me because sets can have 4 different relations between them:
1) They are strange (imagine a Venn diagram with two circles apart from each other).
2) They are the same (imagine a circle on top of a circle).
3) They share some elements, and don't share other elements (intersection is nonempty: two circles in love).
4) One contains the other (little circle inside BIG circle).
I need to know if the 2nd option is relevant to a collection I might receive in the Set-Cover definition.