2. (10 pts) Consider the graph in the figure below on the vertex set V =...

Transcribed Image Text:

2. (10 pts) Consider the graph in the figure below on the vertex set V = {1, 2, ..., 7} and the integer program for the independent set/stable set problem in that graph: max subject to i=1 xi Xj+xj 1 Vi, j V such that ij E (1) Xi 0 Vi V Xi Z Vi V 2 7 3 6 Find a cutting plane proof of the inequality 11 x; 2 using sequences of C-G cuts (starting from the system (1)). =1 Xi 2. (10 pts) Consider the graph in the figure below on the vertex set V = {1, 2, ..., 7} and the integer program for the independent set/stable set problem in that graph: max subject to i=1 xi Xj+xj 1 Vi, j V such that ij E (1) Xi 0 Vi V Xi Z Vi V 2 7 3 6 Find a cutting plane proof of the inequality 11 x; 2 using sequences of C-G cuts (starting from the system (1)). =1 Xi