English subtitles

← Find the Strangers - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. We can illustrate this idea of reducibility by introducing another problem on social networks
  2. that we'll call the S independent set problem and the problem goes like this.
  3. Given the graph H and a number S, is there a set of nodes of size S, the set is a size S not the nodes,
  4. in H such that node to node in the set are connected in the original graph H.
  5. In some sense, they're independent of each other.
  6. You can think of this as the find the strangers problem.
  7. So they need to be in the social network together but none of them know each other.
  8. So for example, if we look in this graph H for an independent set size of three,
  9. We noticed that there is at least this triple, this set of nodes where none of the pairs know each other.
  10. We can't make it any bigger than this at least including those three nodes
  11. because every other nodes that we didn't include is connected to at least one of these guys.
  12. I think this is probably the biggest independent set in this graph.
  13. All right, so now what we're going to try to do is reduce this problem to K-clique
  14. or more concretely show how a polynomial time solution
  15. to K-clique solves the S-independent set problem.
  16. So here's four approaches that we might be able to use to solve this problem.
  17. One is first note that the S-independent set problem can be solved by guessing a set of nodes,
  18. and then making sure that none of the pairs of nodes in that set are connected.
  19. All you have to do is check S² edges or big Πof S² edges so this runs in polynomial time.
  20. Here's another possibility. Let's actually take the graph H and run the S-clique algorithm on it.
  21. That is to say the K-clique algorithm that we use when looking for a clique of size S,
  22. and whatever it returns, return the opposite of the answer.
  23. The idea being that if a graph has a very big clique in it, there's lot of nodes
  24. that are densely connected, then it's unlikely to have a large independent set.
  25. All right, here's another approach.
  26. Let's take the graph H and build a new graph G that is the complement of H.
  27. That is to say every place there's an edge in H.
  28. There's no edge in G. Every place there's no edge in H. There is an edge in G.
  29. Then we run the S-clique algorithm that the K-clique algorithm looking for a clique of size S
  30. on this new graph G and whatever answer it gives just return the opposite.
  31. So if it says that there's an S-clique in G return false
  32. and if it says there's no S-clique in G then return true.
  33. And this last option is the reverse of that, so you build the complement graph.
  34. You look for a size S-clique in that graph and if there is one say yes and if there isn't one say no.
  35. So think about these a little bit.
  36. Maybe even sketch an example problem for yourself to see which of these makes sense.