In one of fundamental work in combinatorial optimization Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs are a subclass of claw-free graphs, and as for claw-free graphs, there exists a polynomial algorithm for finding a maximum weighted stable set on such graphs, but we do not have a complete characterization of their stable set polytope ({\sc ssp}). In the paper we introduce a class of inequalities, called clique-family inequalities, which are valid for the {\sc ssp} of any graph and match the odd set inequalities defined by Edmonds for the matching polytope. This class of inequalities unifies all the known (non-trivial) facet inducing inequalities for the {\sc ssp} of a quasi-line graph. We therefore conjecture that all the non-trivial facets of the {\sc ssp} of a quasi-line graph belong to this class. We show that the conjecture is indeed correct for the classes of quasi-line graphs for which we have a complete description of the {\sc ssp}. We discuss some approaches for solving the conjecture and a related problem.
Citation
Centro Vito Volterra, Universita' di Roma Tor Vergata
Article
View Clique Family Inequalities for the Stable Set Polytope of Quasi-Line Graphs