
Title:
Find the Strangers  Intro to Algorithms

Description:

We can illustrate this idea of reducibility by introducing another problem on social networks

that we'll call the S independent set problem and the problem goes like this.

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,

in H such that node to node in the set are connected in the original graph H.

In some sense, they're independent of each other.

You can think of this as the find the strangers problem.

So they need to be in the social network together but none of them know each other.

So for example, if we look in this graph H for an independent set size of three,

We noticed that there is at least this triple, this set of nodes where none of the pairs know each other.

We can't make it any bigger than this at least including those three nodes

because every other nodes that we didn't include is connected to at least one of these guys.

I think this is probably the biggest independent set in this graph.

All right, so now what we're going to try to do is reduce this problem to Kclique

or more concretely show how a polynomial time solution

to Kclique solves the Sindependent set problem.

So here's four approaches that we might be able to use to solve this problem.

One is first note that the Sindependent set problem can be solved by guessing a set of nodes,

and then making sure that none of the pairs of nodes in that set are connected.

All you have to do is check SÂ˛ edges or big Î of SÂ˛ edges so this runs in polynomial time.

Here's another possibility. Let's actually take the graph H and run the Sclique algorithm on it.

That is to say the Kclique algorithm that we use when looking for a clique of size S,

and whatever it returns, return the opposite of the answer.

The idea being that if a graph has a very big clique in it, there's lot of nodes

that are densely connected, then it's unlikely to have a large independent set.

All right, here's another approach.

Let's take the graph H and build a new graph G that is the complement of H.

That is to say every place there's an edge in H.

There's no edge in G. Every place there's no edge in H. There is an edge in G.

Then we run the Sclique algorithm that the Kclique algorithm looking for a clique of size S

on this new graph G and whatever answer it gives just return the opposite.

So if it says that there's an Sclique in G return false

and if it says there's no Sclique in G then return true.

And this last option is the reverse of that, so you build the complement graph.

You look for a size Sclique in that graph and if there is one say yes and if there isn't one say no.

So think about these a little bit.

Maybe even sketch an example problem for yourself to see which of these makes sense.