Small bipartite subgraph polytopes

We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes.


L. Galli & A.N. Letchford (2010) Small bipartite subgraph polytopes. Oper. Res. Lett., 38(5), 337-340.