Facets of the Bipartite Subgraph Polytope
Francisco Barahona, Martin Grötschel, Ali Ridha Mahjoub · Mathematics of Operations Research · 1985
The bipartite subgraph polytope P B (G) of a graph G = [V, E] is the convex hull of the incidence vectors of all edge sets of bipartite subgraphs of G. We show that all complete subgraphs of G of odd order and all so-called odd bicycle wheels contained in G induce facets of P B (G). Moreover, we describe several methods with which new facet defining inequalities of P B (G) can be constructed from known ones. Examples of these methods are contraction of node sets in odd complete subgraphs, odd subdivision of edges, certain splittings of nodes, and subdivision of all edges of a cut. Using these methods we can construct facet defining inequalities of P B (G) having coefficients of order |V| 2 .