in a graph G = (V,E): max subject to Zv Consider the integer program for the...

 

Transcribed Image Text:

in a graph G = (V,E): max subject to Zv Consider the integer program for the stable set problem +1 Vu, w EV such that vw E 0 VvE V Zv Z VU EV Find cutting plane proofs using sequences of C-G cuts (starting from the above system) for the following "combinatorial" family of cutting planes: (i) Let C be an odd cycle. It is easy to see that the maximum number of vertices from C in a stable set is at most . Thus, we have the family of "odd cycle inequalities": vec for all odd cycles C. (ii) The following graph is known as a 5-wheel. We have the "wheel inequalities" Let W be the node set of a 5-wheel with r as the center node. Then the following is a valid inequality for the integer points 2% + EW\{r} <2. (Convince yourself of the validity of the inequality using combinatorial arguments first) (iii) A set of vertices K CV forms a clique if there is an edge between every pair of vertices in K. Clearly, we can have at most one vertex from any clique; thus, we have the family of clique inequalities vek 1 for all cliques K. in a graph G = (V,E): max subject to Zv Consider the integer program for the stable set problem +1 Vu, w EV such that vw E 0 VvE V Zv Z VU EV Find cutting plane proofs using sequences of C-G cuts (starting from the above system) for the following "combinatorial" family of cutting planes: (i) Let C be an odd cycle. It is easy to see that the maximum number of vertices from C in a stable set is at most . Thus, we have the family of "odd cycle inequalities": vec for all odd cycles C. (ii) The following graph is known as a 5-wheel. We have the "wheel inequalities" Let W be the node set of a 5-wheel with r as the center node. Then the following is a valid inequality for the integer points 2% + EW\{r} <2. (Convince yourself of the validity of the inequality using combinatorial arguments first) (iii) A set of vertices K CV forms a clique if there is an edge between every pair of vertices in K. Clearly, we can have at most one vertex from any clique; thus, we have the family of clique inequalities vek 1 for all cliques K.