In one of fundamental works in combinatorial optimization, Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets in 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 in such graphs, but we do not have a complete characterization of their stable set polytope (SSP). In the paper, we introduce a class of inequalities, called clique-family inequalities, which are valid for the 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 SSP of a quasi-line graph. We, therefore, conjecture that all the non-trivial facets of the SSP of a quasi-line graph belong to this class. We show that the conjecture is indeed correct for the subclasses of quasi-line graphs for which we have a complete description of the SSP. We discuss some approaches for solving the conjecture and a related problem. (C) 2003 Elsevier B.V. All rights reserved.

Oriolo, G. (2004). Clique family inequalities for the stable set polytope of quasi-line graphs. DISCRETE APPLIED MATHEMATICS, 132(2009/03/01 00:00:00.000), 185-201 [10.1016/S0166-218X(03)00400-1].

Clique family inequalities for the stable set polytope of quasi-line graphs

ORIOLO, GIANPAOLO
2004-01-01

Abstract

In one of fundamental works in combinatorial optimization, Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets in 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 in such graphs, but we do not have a complete characterization of their stable set polytope (SSP). In the paper, we introduce a class of inequalities, called clique-family inequalities, which are valid for the 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 SSP of a quasi-line graph. We, therefore, conjecture that all the non-trivial facets of the SSP of a quasi-line graph belong to this class. We show that the conjecture is indeed correct for the subclasses of quasi-line graphs for which we have a complete description of the SSP. We discuss some approaches for solving the conjecture and a related problem. (C) 2003 Elsevier B.V. All rights reserved.
2004
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Claw-free graphs; Matching polytope; Polyhedral combinatorics; Quasi-line graphs
Oriolo, G. (2004). Clique family inequalities for the stable set polytope of quasi-line graphs. DISCRETE APPLIED MATHEMATICS, 132(2009/03/01 00:00:00.000), 185-201 [10.1016/S0166-218X(03)00400-1].
Oriolo, G
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/39094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 27
social impact