|
Not all reductions are as difficult as the ones that we have done so far. Some are very simple.
Suppose G is an undirected graph. Two vertices are adjacent if there is an edge that connects them.
Two vertices u and v in G are independent they are not adjacent.
An independent set is a set of vertices that are pairwise independent. That is, no two vertices in the set are adjacent.
Let's look at the same example graph that was used earlier for the vertex cover problem, where G has vertices
and its edges are
| {1, 2}, | {1, 4}, |
| {1, 6}, | {1, 8}, |
| {2, 3}, | {3, 4}, |
| {4, 5}, | {5, 6}, |
| {6, 7}, | {7, 8}, |
| {8, 9}, | {2, 9}. |
We saw that a Vertex Cover of G is
An independent set of G is
Notice that no two vertices in set {2, 4, 6, 8} have an edge between them.
It was no accident in the example above that the odd-numbered vertices form a vertex cover and the even-numbered vertices form an independent set.
Theorem. S is a vertex cover of G ⇔ S is an independent set of G.
Suppose that S is a vertex cover. Then every edge contains at least one member of S (by the definition of a vertex cover). But that means there are no edges {u,v} where u and v are both not in S. So S is a independent set.
The other direction (S is an independent set implies S is a vertex cover) is left as an exercise.
The Independent Set problem is as follows.
Input. An undirected graph G and a positive integer K.
Question. Does G have an independent set of size at least K?
Let's use abbreviations IS for the Independent Set problem and VC for the Vertex Cover problem.
Theorem. IS is NP-complete.
Proof. It suffices to show that (a) IS ∈ NP and (b) VC ≤p IS.
Part (a) is easy. The evidence is the set S of vertices. S is accepted as good evidence if it is a set of at least K different vertices of G and no two members of S have an edge between them in G.
Part (b) is also easy. Let's write N(G) for the number of vertices in graph G. Then
is a reduction from VC to IS.
f is clearly computable in polynomial time. And
| (G,K) ∈ VC | ⇒ | G has a vertex cover (say, S) of size at most K |
| ⇒ | G has an independent set (namely, S) of size at least N(G) − K | |
| ⇒ | (G, N(G) − K) ∈ IS |
The opposite direction ((G, N(G) − K) ∈ IS ⇒ (G, K) ∈ VC) is nearly identical in form.
Notice how simple the reduction is between these two closely related problems.
|