Clique Family Inequalities for the Stable Set Polytope of Quasi-Line Graphs

gianpaolo oriolo (oriolodisp.uniroma2.it)

Abstract: 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.

Keywords: polyhedral combinatorics, matching polytope, claw-free graphs, quasi-line graphs

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Integer Programming (0-1 Programming )

Citation: Centro Vito Volterra, Universita' di Roma ``Tor Vergata

Download: [PDF]

Entry Submitted: 05/10/2002
Entry Accepted: 05/10/2002
Entry Last Modified: 05/10/2002

Modify/Update this entry