
Title:
Reducing to Clique  Intro to Algorithms

Description:

Just to illustrate this example, imagine we'd start up with some graph H. It's a little bit of a mess.

There's a lot of edges in here but we're going to do is convert this to a new graph G,

which is the complement of H, and so every place in H where there is an edge we leave the edge out,

and every place where there is not an edge, we add an edge.

For example, this node is not connected to this one or this one.

So in the complement graph, we connect it that one and that one.

This node is connected to three on the top, one on the bottom.

So we connect it to this one on the top and these two on the bottom.

This one on the top and these two in bottom.

So we carefully constructed this complement graph G and the thing that you need to realize now is that

G, this new graph, which is the complement of H has an Sclique

if and only if H has an S independent set.

In fact, it's the same set of nodes. So here's our four clique for example.

This is similar to the graph that we looked at before.

This is our four clique in G and if we look that corresponds exactly to a four independent set in H

because it has all the pairwise edges in G and then it has to fail to have all those pairwise edges in H.

So that's how can use the solution into the clique problem to solve the independent set problem.

Now in this particular example, well it illustrates a general idea

which is we take instances of one problem and we transform them into instance of another.

In this case the transformation is really very straightforward.

Maybe it wasn't obvious to you at first. Now that I putted that, it's probably pretty straightforward.

Some of these reduction actually can be much more involved.

This one actually is also really easily reversed.

So if we have an algorithm for independent set.

We can use that to solve the clique problem the same way.

Invert the graph where I complement the graph, look for the independent set and that tells us

what the clique is in the original graph,

but sometimes again the connection is not always so straightforward.