Numerical Methods and Optimization

Basic Concepts 181

V is a finite set of vertices and E is a set of edges given by unordered

pairs of vertices, E ⊆{{i, j} : i, j ∈ V }. Given a simple undirected

graph G =(V, E)withn = |V | vertices, the maximum independent set

problem is to find a maximum-size subset I of V such that {i, j} /∈ E

for any i, j ∈ I.Letα(G)denotetheindependence number of G,which

is the cardinality of a maximum independent set of G. Show that

α(G)= max

x∈[0,1]

n



e

T

x −

1

2

x

T

A

G

x



,

where e =[1,...,1]

T

∈ IR

n

,andA

G

=[a

ij

]

n×n

with a

ij

=1if{i, j}∈E

and a

ij

= 0 otherwise. Hint: observe that the objective function of the

above problem is linear with respect to each variable.

8.4. Solve the