As is well known, the strong perfect graph conjecture has been of interest to the integer programming community as well as the combinatorics community. Now that the SPGC has been established I wanted to mention another problem which may shed light on cutting plane approaches to packing problems. Sewell (and later Bram Verweij and Aardel) gave successful cutting plane codes for solving maximum stable set problems in sparse graphs by adding odd hole inequalities as they are violated by fractional solutions. Moura studied this approach for some problems arising in design theory, but met with much less success since the graph instances were much more dense (and hence odd hole inequalities were unlikely to be violated).
Can we extend the class of odd cycle inequalities to the class of partitionable graph inequalities
for each partitionable subgraph. I.e., can we develop algorithms to solve the separation problem for this class of inequalities. One positive result is that partitionable graphs themselves can be recognized in polynomial time (another problem is to find a combinatorial algorithm to recognize partitionable graphs).
Contributed by Bruce Shepherd.
Back to the
main index
for Perfect Graphs.