A Family of Spanning-Tree Formulations for the Maximum Cut Problem

We present a family of integer programming formulations for the maximum cut problem. These formulations encode the incidence vectors of the cuts of a connected graph by employing a subset of the odd-cycle inequalities that relate to a spanning tree, and they require only the corresponding edge variables to be integral explicitly. They so describe sufficient restrictions of the classic integer linear program by Barahona and Mahjoub. In addition, we characterize according formulations comprising facet-defining inequalities only. Trade-offs and comparisons to prevalent formulations concerning size and relaxation strength are subject to an experimental study.