8.lS. Let A(G) denote the number of vertices that an arbitrary approximation algorithm A assigns to a maximum independent set for the graph G. We denote by OPT(G) the exact number in this set. Show...

8.lS. Let

A(G)



denote the number of vertices that an arbitrary approximation algorithm

A



assigns to a maximum independent set for the graph

G.

We denote by

OPT(G)



the exact number in this set. Show that if

NP




¢




P,



then the proposition that for all instances

G



that:

IA(G)-OPT(G)I ...

K

for some integer constant

K,

is false.

(Suppose that the proposition is true. Given

G



we can apply

A



to the (disconnected) graph

G'



which consists of

(K

+1) copies of

G.



Then

IA(G')-OPT(G')I :!lo

K

and clearly

OPT(G')



=

(K

+1)

OPT(G').

This also defines an algorithm

B





which assigns at least f

A


(


G


'


)


/




(


K

+1)1 vertices to the maximum independent set of

G



-obtained by finding the largest set of vertices

that

A



assigns to any of the components of

G'.



It follows that:

IB(G)-OPT(G)I .s. K/(K+1)

In other words,

B(G)



must be equal to

OPT(G)



so that

B



would 11e an exact algorithm. With theorem 8.4 this provides a contradiction.)