The maximum independent set (MIS) of a graph G = (V,E) is the largest set of vertices S ⊆ V such that for any two vertices u, v ∈ S, (u, v) ∈/ E; that is, no pair of vertices in S are neighbors. We want to create a linear program to solve the MIS problem. We create an indicator variable iv for each vertex v ∈ V , and the sum of the iv should denote the size of the MIS. Consider the following linear program formulation of the MIS problem: 

What’s wrong with this formulation? Give a small example graph for which the linear program does not give a reasonable answer for the size of the maximum independent set. Why doesn’t the program give a reasonable answer in this case?

Transcribed Image Text:

maximize: in subject to: i, 20 in <1 in + i <1 for (v, v') E E