# 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 , 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 if and only if does not belong to a triangle.

A class that is more interesting than the trivial inequalities are the cycle inequalities. An edge set is called a *cycle* (of length *k*) in the graph .

Let be a cycle and be an edge that does not belong to .

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

A cycle 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 be a cycle in and a subset of cycle edges of odd cardinality. Then the *cycle inequality*

is valid for the cut polytope . Barahona and Mahjoub proved that the cycle inequalities are facets in case is chordless.

The *triangle inequalities*

for triangle in are a special case of the cycle inequalities for and define facets of .

#### 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 , where is the complete graph on 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 for all edges in , decide wether satisfies all cycle inequalities. If not, return a cycle inequality

violated by .

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