In 1996, Laurent and Poljak introduced an extremely general class of cutting planes for the max-cut problem, called gap inequalities. We prove several results about them, including the following: (i) there must exist non-dominated gap inequalities with gap larger than 1, unless NP = co-NP; (ii) there must exist non-dominated gap inequalities with exponentially large coefficients, unless NP = co-NP; (iii) the separation problem for gap inequalities can be solved in finite time (specifically, doubly exponential time).
Citation
L. Galli, K. Kaparis & A.N. Letchford (2012) Complexity results for the gap inequalities for the max-cut problem. Oper. Res. Lett., 40(3), 149-152.