Proofs for the MaxCut Polyhedron

John Mitchell

Given a graph G = (V,E), a cut partitions V into two sets V _{1} and V _{2}. An edge e = (u,v) is in the
cut if exactly one of its endpoints is in V _{1}. We represent this cut using the binary vector x ∈ ℝ^{n},
where n = |E|, with

Let S ⊆ ℝ^{n} denote the set of incidence vectors of feasible solutions and let conv(S) denote its
convex hull.

The proofs below are adapted from Deza and Laurent (Mathematical Programming 56:121–160, 1992).

Theorem 1 The MaxCut polyhedron conv(S) is full-dimensional.

Proof. If the polyhedron is not full-dimensional then there exists a nontrivial constraint

| (1) |

that is satisfied by all x ∈ S. We show that any such equality must actually be trivial with b = 0
and a_{e} = 0 for all e ∈ E.

b = 0 : One valid partition is to take V _{1} = V and V _{2} = ∅, which results in x_{e} = 0 for all e ∈ E.
Hence the left hand side of (1) evaluates to zero, so we must have b = 0.

a_{e} = 0∀e ∈ E : Pick an arbitrary edge = (r,s) and show a_{e} = 0 by considering three
cuts.

- V
_{1}= {r}, V_{2}= V \ r. Then (1) becomes(2) - V
_{1}= {s}, V_{2}= V \ s. Then (1) becomes(3) - V
_{1}= {r,s}, V_{2}= V \{r,s}. Then (1) becomes(4)

This holds for all ∈ E, as required. □

Let C ⊆ E denote a cycle in the graph. Let F ⊆ C with |F| odd. We have the valid constraint

| (5) |

This is facet-defining provided the cycle contains no chords; that is, there are no edges of the form (u,v) ∈ E where u and v are nonconsecutive nodes in the cycle.

One way to prove a valid constraint is facet-defining is to show that it is not implied by another valid constraint. This lets us state the general proof-by-contradiction procedure as follows:

- Let π
^{T }x ≤π_{ 0}denote the given inequality, and we want to prove this defines a facet of conv(S). Assume there exists ∈ S satisfying π^{T }< π_{ 0}, so the face defined by the inequality is not equal to S. - We need to show there is no other inequality g
^{T }x ≤h satisfying all of the following:- 1.
- g
^{T }≤ h for all ∈ S, so the constraint is valid. - 2.
- g
^{T }= h for all ∈ S satisfying π^{T }= π_{ 0}(so it includes the same face). - 3.
- There is a point ∈ S with g
^{T }= h, π^{T }< π_{ 0}(so the face defined by g^{T }x = h strictly contains the face implied by the original inequality). - 4.
- There is a point ∈ S with g
^{T }< h (so the face defined by g^{T }x = h is not the whole of S).

- When S is full-dimensional, one way to show there is no other inequality satisfying all four
conditions is to assume we have an inequality that satisfies the first two conditions and then
show this inequality must just be a positive rescaling of π
^{T }x ≤ π_{ 0}.

We show that one particular odd-subset constraint is facet defining. The proof can be extended to show that any inequality of the form (5) is facet defining for |F| odd and C chordless.

In particular, consider the inequality

| (6) |

for three vertices i,j,k ∈ V and three edges (i,j), (i,k), (j,k) ∈ E. This constraint is satisfied at equality by three types of cuts:

- 1.
- {i,j,k}⊆ V
_{1}. - 2.
- {i,k}⊆ V
_{1}, j ∈ V_{2}. - 3.
- {j,k}⊆ V
_{1}, i ∈ V_{2}.

The remaining vertices can be placed in either V _{1} or V _{2}. The roles of V _{1} and V _{2} can be
reversed.

Assume inequality (6) is implied by g^{T }x ≤ h, and look at possible choices for g
and h.

First, determine h. The cut V _{1} = V , V _{2} = ∅ satisfies (6) at equality, so it must also satisfy
g^{T }x = h from the second requirement in the general procedure on the previous page. For this cut,
x = 0, so we must have h = 0, the same right hand side as in (6). So g^{T }x = 0 for any x ∈ S that
satisfies (6) at equality.

Now determine the values of g by looking at various cuts. In this way, we can set up multiple equalities that must be satisfied by the components of g, and then these can be combined to show g is a multiple of the original coefficients in (6). In particular, we want to show that

- Let l ∈ V \{k} and set V
_{1}= V \{l}, V_{2}= {l}. We have(7) - Consider edges where neither endpoint is in {i,j,k}. In particular, let l,m ⁄∈{i,j,k} with
(l,m) ∈ E and take V
_{1}= V \{l,m}, V_{2}= {l,m}. We have(8) It follows from (7) that

(9) - Now look at edges (j,l) where l ⁄∈{i,j,k}. Take V
_{1}= V \{j,l}, V_{2}= {j,l}. We have(10) It follows from (7) that

(11) - In an analogous manner, we obtain
(12) for l ⁄∈{i,j,k}.

We still need to determine g_{ij}, g_{ik}, and g_{jk}, and also g_{kl} for l ⁄∈{i,j}.

- Next, we show that g
_{ij}, g_{ik}, g_{jk}have the same relationship as in (6). Take V_{1}= V \{i}, V_{2}= {i}. We obtain(13) Similarly, taking V

_{1}= V \ j, V_{2}= j and using (11), we obtain(14) (15) agreeing with the relationship between these coefficients in (6).

- Finally, look at g
_{kl}for l ⁄∈{i,j,k}. Set V_{1}= {i,k}, V_{2}= V \{i,k}. We have Now with V_{1}= {i,k,l} and V_{2}= V \{i,k,l}, we get

So all coefficients are positive multiples of those in (6).