Tightness of the Cycle-Based Relaxation for Completed Length-Three Alpha-Cycles

Abstract

Del Pia and Khajavirad introduced the complete edge relaxation for binary polynomial optimization and generalized triangle inequalities for length-three α-cycles. We study the relaxation obtained by adding all switchings of these inequalities to the complete edge relaxation on the completed support of a single length-three α-cycle. If H = cl({e1, e2, e3}) and A = (e1 ∩ e2) \ e3, B = (e2 ∩ e3) \ e1, C = (e1 ∩ e3) \ e2, then the cycle-based relaxation is equal to the multilinear polytope if and only if |A| = |B| = |C| = 1. The same characterization remains true for the stronger relaxation obtained by imposing the switched generalized triangle inequalities for every no-private length-three α-cycle contained in H. No restriction is needed on the common intersection or on the private vertices of the three maximal edges. The positive direction is proved by a slice-wise gluing argument, while the negative direction lifts a four-variable parity obstruction and shows that it survives every applicable switched triangle inequality. We remark on the use of AI in this research, see Statement of AI Use.