An O (|E|)-linear model for the maxcut problem

Abstract

A polytope P is a model for a combinatorial problem on finite graphs G whose variables are indexed by the edge set E of G if the points of P with (0,1)-coordinates are precisely the characteristic vectors of the subset of edges inducing the feasible configurations for the problem. In the case of the (simple) Max Cut problem, which is the one that concern us here, the feasible subsets of edges are the ones inducing the bipartite subgraphs of G. This work we introduce a new polytope P₁₂ _ R|E given by at most 11|E| inequalities, which is a model for the Max Cut problem on G. Moreover, the left side of each inequality is the sum of at most 4 edge variables with coefficients ±1 and right side 0, 1 or 2. We restrict our analysis to the case of G = Kz, the complete graph in z vertices, where z is an even positive integer z _ 4. This case is sufficient to study because the simple Max Cut problem for general graphs G can be reduced to the complete graph| K z by considering the objective function of the associated integer programming as the characteristic vector of the edges in G _ Kz. This is a polynomial algorithmic transformation. An extension to the linear model into a more complete symmetric model which contains all the permutations for triangular and quadrilateral inequalities, equivalent to other formulations present in the literature is presented as well as the 01-cliques.