Konrad-Zuse-Zentrum für Informationstechnik Berlin ZIB PaperWeb

02-03

Annegret Wagler Relaxing Perfectness: Which Graphs are Almost Perfect?

Abstract: For all perfect graphs, the stable set polytope STAB$(G)$ coincides with the fractional stable set polytope QSTAB$(G)$, whereas STAB$(G) \subset$ QSTAB$(G)$ holds iff $G$ is imperfect. Padberg asked in the early seventies for ``almost perfect graphs. He characterized those graphs for which the difference between STAB$(G)$ and QSTAB$(G)$ is smallest possible. We develop this idea further and define three polytopes between STAB$(G)$ and QSTAB$(G)$ by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB$(G)$. The difference between QSTAB$(G)$ and the largest of the three polytopes coinciding with STAB$(G)$ gives some information on the stage of imperfectness of the graph $G$. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question: which graphs are ``almost perfect?
(only electronic version available)
Keywords: perfect graph, stable set polytope, relaxations
MSC: 05C17, 90C10