# Valid inequalities for max-cut

## Contents |

### Introduction

In this article we explain relevant concepts for understanding the geometry of the cut polytope. The latter is important for the development of an effective branch-and-cut algorithm for determining optimum solutions for max-cut and for exact ground states of Ising spin glasses, cf. the article about computing exact ground states of Ising spin glasses.

### Valid inequalities for max-cut

Next we introduce classes of inequalities that are valid or facet defining for the cut polytope. Optimizing over the corresponding relaxations yields bounds that can be used within a branch-and-cut procedure. Given a graph *G* = (*V*,*E*), an incidence vector χ of a cut obviously has to satisfy

Barahona and Mahjoub proved that these 'trivial' inequalities define a facet of the cut polytope *P*_{C}(*G*) if and only if *e* does not belong to a triangle.

A class that is more interesting than the trivial inequalities are the cycle inequalities. An edge set *C* = {(*v*_{0},*v*_{1}),(*v*_{1},*v*_{2}),...,(*v*_{k − 1},*v*_{0})} ⊆ *E* is called a *cycle* (of length *k*) in the graph *G* = (*V*,*E*).

Let *C* ⊆ *E* be a cycle and *e* be an edge that does not belong to *C*.

We say *e* is a *chord* of *C* if it joins two nodes of *C*.

A cycle *C* is called *chordless* if it does not contain a chord.

The cycle inequalities are drawn from the observation that a cut and a cycle can only have an even number of common edges.

Let *C* ⊆ *E* be a cycle in *G* = (*V*,*E*) and *F* ⊆ *C* a subset of cycle edges of odd cardinality. Then the *cycle inequality*

is valid for the cut polytope *P*_{C}(*G*). Barahona and Mahjoub proved that the cycle inequalities are facets in case *C* is chordless.

The *triangle inequalities*

for triangle *i*, *j*, *k* in *G* are a special case of the cycle inequalities for | *C* | = 3 and define facets of *P*_{C}(*G*).

#### Example

We consider the graph consisting of a triangle.

The cycle inequalities read

Indeed, for the four incidence vectors of cuts shown in the example these inequalities are satisfied. Furthermore, zero - one vectors that do not correspond to cuts violate the cycle inequalities. For example the vector which does not define a cut does not satisfy the first triangle inequality.

The cycle polytope of *K*_{p}, where *K*_{p} is the complete graph on *p* nodes, consists of all triangle inequalities.

### Separation of the cycle inequalities

For making use of the cycle inequalities within branch-and-cut we have to solve the *separation problem for the cycle inequalities*. We formulate it as follows.

Given with 0 ≤ *x*_{e}^{ * } ≤ 1 for all edges *e* in *E*, decide wether *x*^{ * } satisfies all cycle inequalities. If not, return a cycle inequality

violated by *x*^{ * }.

Barahona and Mahjoub also proved that this separation problem can be solved in polynomial time for cycle inequalities.