Article ID: | iaor20084663 |
Country: | Brazil |
Volume: | 23 |
Issue: | 1 |
Start Page Number: | 99 |
End Page Number: | 109 |
Publication Date: | Jan 2003 |
Journal: | Pesquisa Operacional |
Authors: | Kovalev M., Maurras J.-F., Vaxes Y. |
Let Kn be the complete undirected graph with n vertices. A 3-cycle is a cycle consisting of 3 edges. The 3-cycle polytope is defined as the convex hull of the incidence vectors of all 3-cycles in Kn. In this paper, we present a polyhedral analysis of the 3-cycle polytope. In particular, we give several classes of facet defining inequalities of this polytope and we prove that the separation problem associated to one of these classes of inequalities is NP-complete. Finally, it is proved that the 3-cycle polytope is a 2-neighborly polytope.