English subtitles

← 11-31 One Vertex In Solution

Get Embed Code
1 Language

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

  1. The correct answer here is, similar to vertex cover, those cases are actually the easy ones.
  2. And I'll show you why.
  3. Either v or u already has an assignment, and we can just consider 1 of those cases.
  4. So let's say v already has an assignment, here is u, and there's 2 cases.
  5. Either we said yes, v is in the independent set
  6. or we say no, v is not in the independent set.
  7. This case up here, that's very easy to see because if v is in the independent set
  8. and there's an edge here between those vertices,
  9. then you cannot be in the independent set.
  10. So that one is very clear. What about the case down here?
  11. That's a case that requires a little more thought.
  12. By itself right now, it could either be that u is in the independent set or it's not.
  13. And we don't know, so you might have been inclined to think
  14. that we need to modify the search tree or initiate some other form of brute force search,
  15. but actually, that's not necessary and I will show you why.
  16. This vertex u here, there are 2 possibilities.
  17. If u is not connected to any other vertices--
  18. so let's say all other vertices in the network are independent of u--
  19. then we can put u into the independent set without having to think
  20. because we're looking for a maximum size independent set.
  21. This is the only connection that u has to other vertices. Why not just take it?
  22. It doesn't really cause any other conflicts.
  23. Now, what if u is connected to other vertices?
  24. Here there's 3 different possibilities.
  25. The first possibility is that u has some neighboring vertex--
  26. so one that is connected by an edge--
  27. where we already have assigned it to be in the independent set.
  28. And in that case we can immediately say no, you cannot be in the independent set.
  29. We must assume that none of these vertices here is already in the independent set.
  30. So now there is 2 different cases.
  31. One is that 1 of these vertices here has not yet received an assignment.
  32. And in that case we don't have to worry about modifying the search tree
  33. because now we're looking at a case like this here again.
  34. So we can use our standard search tree to search through assignments
  35. for these 2 vertices here.
  36. If every vertex here, on the other hand, already has an assignment,
  37. then we just discussed, because we've just dealt with the other case,
  38. that all of these assignments here must be a 0.
  39. So all of these vertices here--and there can be more, of course--
  40. are not part of the independent set,
  41. and that means that we can take u into the independent set again.
  42. It might not have been obvious in terms of thinking it through what to do in this case,
  43. but for an algorithm we can design it in a way
  44. so that the algorithm always knows what it is to do.
  45. First of all, it looks for edges where both vertices do not have an assignment.
  46. And once it cannot find those edges anymore,
  47. then it will know how to deal with the remaining vertices.
  48. And this of course means that for independent set we can use a search tree that,
  49. just like vertex cover, always finds an assignment for at least 2 vertices.
  50. So its height, so to say, of the search tree is N/2.
  51. The size of the layers multiplies by factor 3.
  52. So the size of the overall tree is 3 to the power of N/2.
  53. For independent set we have a search tree of size 1.733 to the power of N.
  54. Just like vertex cover, the calculation here is the same.
  55. And because independent set and clique are so similar,
  56. we just have to transform the network to the inverse network,
  57. as you remember, hopefully, from the first unit.
  58. We also have a search tree of size 1.733 to the power of N for clique.
  59. Just like Alice, no reason to be super happy,
  60. but Bob and Carol can be a little happier now.
  61. And of course we're going to go on investigating.