2016/04/08 by Sóstenes Lins, Lins, Sostenes L., Carlos Henriques +1
Computer Science · Engineering · #05C85 (secondary) #68Q25 (primary) #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1604.02325
openalex publication_date 2016/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A polytope P is a \em 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) MaxCut Problem, which is the one that concern us here, the feasible subsets of edges are the ones inducing the bipartite subgraphs of G. In this paper we introduce a new polytope ℙ12 ⊂ ℝ|E| given by at most 11|E| inequalities, which is a model for the MaxCut 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 MaxCut problem for general graphs G can be reduced to the complete graph Kz by considering the obective function of the associated integer programming as the characteristic vector of the edges in G ⊆ Kz. This is a polynomial algorithmic transformation.