English subtitles

← 11-29 Search Tree For Independent Set Solution

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. The first answer I hope wasn't that difficult to find. This one is true.
  2. The rules of an independent set are that 2 vertices cannot be connected by an edge
  3. if they are part of the independent set, and that means if we were to put this one
  4. into the independent set as well as this one here, then we would have an error here,
  5. which automatically also answers the second question.
  6. It's not the case that both vertices can be in the independent set
  7. because they are connected to each other.
  8. This one here might have been a little bit more tricky.
  9. So at least 1 of the 2 vertices must be in the independent set.
  10. You might be inclined to think that
  11. because we are looking for a maximum size independent set.
  12. But actually, that is not the case, and I will give you a little example for that.
  13. Say we have a very small network like this one here,
  14. and here you have v, here you have u.
  15. Then this network here has an independent set of size 2.
  16. Actually, it has a number of independent sets of size 2,
  17. but there is also 1 independent set of size 2 where v and u are both excluded.
  18. This is a bit different from vertex cover because you can actually have the case
  19. that both vertices are not part of the set even though they are connected by an edge.
  20. So this is false.
  21. Both v and u could be 0.
  22. Yes, this is exactly what is also shown by this example.
  23. You can have the case that both are not part of the independent set,
  24. so this is definitely a yes here.
  25. Do we have to set both vertices to 0? No.
  26. This is also not the case because, for example, you could also have an independent set here
  27. that you construct in this way.
  28. You put u in and this one out.
  29. So now we have also found a maximum size independent set,
  30. but we have included 1 of the 2 vertices.
  31. So this one here is clearly also not true.
  32. If you take all of those observations together, it's pretty cool
  33. because this now gives us a new search tree strategy
  34. that is actually quite similar to vertex cover.
  35. So we have our 2 vertices, v and u, here.
  36. Just as we did with vertex cover, we can spread into 3 different possibilities.
  37. The first one is we take v into the independent set but not u.
  38. The second one is exactly the other way around.
  39. We do not take v but we take u.
  40. And finally, it is possible that both are excluded.
  41. As long as we find an edge between 2 vertices, v and u,
  42. for which v has no assignment yet and u has no assignment yet,
  43. then we can branch into exactly 3 possibilities.
  44. Now, what happens if either v or u already has an assignment?
  45. For vertex cover I told you what would happen then.
  46. This time I will let you figure this out.