  


Clique Family Inequalities for the Stable Set Polytope of QuasiLine 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 quasiline graphs. Quasiline graphs are a subclass of clawfree graphs, and as for clawfree 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 cliquefamily 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 (nontrivial) facet inducing inequalities for the {\sc ssp} of a quasiline graph. We therefore conjecture that all the nontrivial facets of the {\sc ssp} of a quasiline graph belong to this class. We show that the conjecture is indeed correct for the classes of quasiline 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, clawfree graphs, quasiline graphs Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Integer Programming (01 Programming ) Citation: Centro Vito Volterra, Universita' di Roma ``Tor Vergata Download: [PDF] Entry Submitted: 05/10/2002 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  