A cut in a graph G = (V, E), which corresponds to a set of vertices W ⊆ V, is the set of edges that has one extremity in W and the other in V \ W. The maximum cut problem (MAX-CUT) is one of the fundamental problems in combinatorial optimization. This problem can be presented in the following way: given a graph G = (V, E) and weights , find a cut δ(W), W ⊂ V, such that is maximum. For the last 20 years, this problem has been the subject of intensive research [DEZ 97]. It is one of the first problems shown to be NP-complete [GAR 79]. It has applications in several domains such as statistical physics, VLSI circuits, and flows in networks. It has been studied using different approaches such as the polyhedral approach, which is based on the polyhedron of the solutions of the problem, semi-definite programming, and approximation algorithms with or without guarantees. The MAX-CUT problem is therefore one of the most motivating and most studied subjects in combinatorial optimization. In this chapter, we discuss this problem, with an emphasis on the algorithmic aspects.

The MAX-CUT problem is closely linked to the maximum bipartite subgraph problem. A graph G = (V, E) is said to be bipartite if V can be partitioned into two subsets V₁ and V₂ in such a way that all the edges are between V₁ and V₂. If G = (V, E) is a weighted graph, the maximum bipartite subgraph problem in G consists of finding a bipartite subgraph of G for which the total weight of the edges is maximum. If B ⊆ E is a subset of edges that induces a bipartite subgraph of G then it is clear that B is contained within a cut of G. If the weights are positive, the maximum bipartite subgraph problem and the MAX-CUT problem are equivalent. The bipartite subgraph problem has also been the subject of several studies in the literature [BAR 85, GUE 01, SCH 03].

This chapter is organized as follows. In the following section, we discuss the complexity of the MAX-CUT problem and of certain cases where the problem can be solved in polynomial time. In section 6.3, we present some applications of the MAX-CUT problem. In section 6.4, we discuss the cut polytope. In particular, we introduce certain classes of facets of this polyhedron and we study their separation problems. We also describe some branch-and-cut algorithms for solving the MAX-CUT problem. Section 6.5 is devoted to studying the MAX-CUT problem using semi-definite programming. In section 6.6, we introduce certain applications of the cuts cone. Some approximation methods for the MAX-CUT problem, both with and without guarantees, are introduced in section 6.7. In section 6.8, we discuss the polyhedral aspect of some problems that are related to the MAX-CUT problem.

The rest of this section is devoted to some definitions and notations. We consider non-directed graphs. A graph will be denoted by G = (V, E), where V is the set of vertices and E is that of its edges. If e is an edge between two vertices u and v then we write e = uv. A chain between two vertices u and v in G is a sequence of vertices and edges (ν₀,e₁, ν₁,e₂, ν₂,…, ν_l−₁,e_l, ν_l), where u = ν₀, ν = ν_l and e_i = ν_i−₁ν_i for i = 1,…, l, and ν₀,…, ν_l are distinct vertices of V . The vertices u and ν are called the extremities of the chain. A chain will be denoted by its set of edges (e₁,…, e_l). A cycle is a chain whose extremities coincide. If F ⊆ E then V (F) denotes the set of vertices of the edges of F. If S ⊆ V, we will express by E(S) the set of edges that have their extremities in S.

Let E = {e₁,…, e_n} be a finite set. If F ⊆ E and then we express by x(F) the sum . If a and x are vectors of , we denote by ax the sum . Thus the inequality is expressed by ax ≤ α.

A polyhedron is the set of solutions of a finite system of linear inequalities. A bounded polyhedron is called a polytope. The dimension of a polyhedron P is the maximum number of affinely independent points in P minus 1. Given a polyhedron P, an inequality ax ≤ α is said to be valid for P if ax ≤ α is satisfied by every solution of P. A face of P, associated with a valid inequality ax ≤ α, is the polyhedron given by {x ∈ P : ax = α}. A facet of P is a face of maximum dimension (that is of dimension d − 1, where d is the dimension of P). For further explanations on graphs and combinatorial polyhedra, see [BER 83] and Volume 1, Chapter 10 of this series, respectively.

6.2. Complexity and polynomial cases

As mentioned above, the MAX-CUT problem is in general NP-complete. Karp [KAR 72] showed that the minimum cardinality transversal problem, which is NP-complete, can be reduced to this problem. (A transversal is a subset of vertices that covers all the edges of the graph.) Yannakakis [YAN 78] showed that the MAX-CUT problem stays NP-complete in graphs whose maximum degree does not exceed 3. Barahona [BAR 83] showed that the MAX-CUT problem is NP-complete in nearly planar graphs, that is graphs G that have a vertex ν such that G – ν is planar.

Nonetheless this problem may be solved in polynomial time for some instances with a particular objective function and/or graph topology.

If the weights are all negative, the MAX-CUT problem reduces to the minimum cut problem with positive weights, and can therefore be solved in polynomial time using flows. McCormick et al. [MCC 03] studied the complexity of the problem depending on the signs of the coefficients of the objective function. Let E⁺ be the set of the edges of the graph G = (V, E) associated with a strictly positive cost, and c(V, E⁺) the minimal cardinality of a subset of vertices X ⊆ V such that every edge in E⁺ has one extremity in X. The authors show that the MAX-CUT problem can be solved in polynomial time on instances for which c(V, E⁺) = O(log(n^k)), for fixed k, k > 0. However, this problem is NP-complete for instances such that , for a fixed constant k.

The MAX-CUT problem can also be solved in polynomial time for certain classes of graphs. Orlova and Dorfman [ORL 72], and Hadlock [HAD 75] independently showed that the MAX-CUT problem can be solved in polynomial time if the graph is planar. Their approach is based on the duality of planar graphs and consists of reducing the calculation of a maximum cut to the search for a maximum weight matching. Barahona [BAR 83] extended this result by showing that the MAX-CUT problem remains polynomial in graphs that are not contractible to K₅. (A graph G is contractible to a graph H if H can be obtained from G by a sequence of edge suppressions and contractions. The graph H is then said to be a minor of G.) Barahona [BAR 81a] also showed that the MAX-CUT problem can be solved in polynomial time if the graph can be embedded in a torus and the weights are equal to ±1. Grötschel and Pulleyblanck [GRÖ 81b] introduced the class of graphs said to be weakly bipartite, and showed that the MAX-CUT problem can be solved in polynomial time in this class of graphs using the ellipsoid method. The class of weakly bipartite graphs contains the graphs that are not contractible to K₅ as a subclass [FON 92]. A characterization of this class of graphs was recently given by Guenin [GUE 01]. Grötschel and Nemhauser [GRÖ 84] showed that when edge weights are positive, for every fixed integer k, there is a polynomial algorithm for solving the MAX-CUT problem on graphs for which the length of the odd cycles does not exceed 2k + 1. Also, depending on the objective function and the topology of the graph being studied, Gallucio et al. [GAL 01] showed that under the following hypotheses the MAX-CUT problem can be solved in polynomial time:

– the edge weights are integers that are upper bounded by a polynomial in |V |;

– the graph under consideration has a fixed genus value g.

(The proposed solution procedure has a complexity that increases exponentially with g.)

6.3. Applications

The MAX-CUT problem has many applications in several domains. In this section, we present certain applications of this problem to spin glass models in statistical physics, to unconstrained 0 − −1 quadratic programming without constraints, and to the design of VLSI circuits.

6.3.1. Spin glass models

A spin glass is a system obtained by a weak (1%) dilution of a magnetic material (iron) in a non-magnetic material (gold). Physicists’ interest in this material comes from observing a peak in the curve of what we call the magnetic susceptibility according to temperature. Such a peak generally indicates a transition phase in the state of the system. Hence the need for models that may explain this phenomenon.

In a spin glass, the magnetic atoms are randomly dispersed in space. Between two atoms i, j, there is an interaction energy:

where S_i (S_j) is the magnetic moment (spin) of the atom i (j), and J(R) is a function that depends on the distance R between the two atoms. In order to model these systems, physicists have constructed a simplified model: they assume that the spins are located at the nodes of a regular mesh (instead of being randomly distributed) and are defined by one-dimensional (instead of three-dimensional) vectors S_i that take the values +1 and −1. These meshes are generally square or cubic. They assume furthermore that the interactions between the spins only occur between the closest neighbors, and that their energies ₍J_ij₎ are random variables that can take positive or negative values. The interactions then correspond to the links of the mesh.

A configuration S of spins (that is an assignment of +1 and −1 to the spins) has a corresponding system energy given by:

[6.1] Equation 6.1

where L is the set of connections and J_ij the interaction between the spins i and j. The problem given by physicists is that of establishing a configuration S that minimizes the system energy [6.1]. Such a configuration is said to be the ground state of the system and the problem is called the ground state problem. Physicists traditionally use Monte-Carlo type heuristics to establish approximate solutions for this problem, even in the case where the mesh is square (planar). As is shown in what follows, this problem can be reduced to the MAX-CUT problem.

We can associate a graph G = (V, E) with a spin glass system, where the vertices correspond to the spins, and two vertices are connected by an edge if there is an intersection between the corresponding spins. We associate the weight ω_ij = −J_ij with each connection ij. Consequently, the ground state problem is equivalent to the program:

[6.2] Equation 6.2

Thus the problem is to establish an assignment of +1 and −1 to the vertices of the graph in such a way that is minimum. Let S be an assignment of +1 and −1 to the vertices of V . Let V₊ = {i ∈ V : S_i = +1} and V₋ = {i ∈ V : S_i = −1}. So:

Since is a constant, minimizing H(S) is equivalent to maximizing the weight of the cut induced by . Hence the ground state problem is reduced to the MAX-CUT problem in G.

6.3.2. Unconstrained 0–1 quadratic programming

Let us consider the quadratic 0 − −1 program:

[6.3] Equation 6.3

Problem [6.3] does not contain any terms of the type given that . Problem [6.3] is generally NP-hard [GAR 79]. As will be shown below, problem [6.3] can be reduced to the MAX-CUT problem [HAM 65]. Let s_i = 2x_i − 1. So the function f(x) can be expressed as:

where s_i ∈ {−1, +1} for i = 1,…,n and . By adding a variable s₀ and setting:

we obtain the following equivalent problem:

[6.4] Equation 6.4

Problem [6.4] is of the same type as the spin glass problem [6.2], and can therefore be reduced to the MAX-CUT problem in an appropriate graph.

6.3.3. The via minimization problem

The second application of the MAX-CUT problem concerns the design of VLSI circuits [PIN 84]. A VLSI circuit is made up of a set of networks where each network consists of a set of terminal points that must be electrically connected by conducting paths. Once a network is positioned on the circuit medium, it forms a set of straight lines that are either horizontal or vertical. The intersection points of the segments are called junctions. The number of segments that are incident to the same junction is called the junction degree. Each network transports particular data and, in consequence, must not be connected to another network. To achieve this, the circuit medium may have several layers. It is often impossible to position the networks on a single layer without overlapping. Several real-life applications (such as electronic chips) only need two-layer circuits.

The production of a VLSI circuit is generally decomposed into several phases. The last phase, called network layer assignment, consists of assigning the network paths (that is the segments) to the different layers of the circuit in such a way that no two different network paths are connected. In other words, no two paths from the same network must cross each other. To do this, we sometimes need to drill a via (a hole) in the physical medium to allow us to connect the various paths from a particular network between the different layers. Since vias generate an additional cost and limit the space in the circuit medium, we need to establish an assignment of the circuit paths to the layers in such a way that there is a minimum number of vias. This problem is called the constrained via minimization problem. In the two layer case, Pinter [PIN 84] showed that this problem can be reduced to the MAX-CUT problem if the junction degree does not exceed three. In fact, Pinter’s model constructs a graph where the edges correspond to the segments that may contain vias. In that graph, a maximum cut, relative to an appropriate system of weights, will indicate which paths may contain vias in an optimal assignment of the networks. For more details on this problem see [BAR 88, FOU 05, GRÖ 89a, PIN 84].

6.4. The cut polytope

In this section, we introduce the cut polytope. We present certain families of valid inequalities and we study their associated separation problems. We also discuss branch-and-cut algorithms for the MAX-CUT problem and related problems based on these inequalities.

Let G = (V, E) be a graph. If F ⊆ E is a subset of edges of E then the vector x^F ∈ {0, 1}^E such that x^F (e) = 1 if e ∈ F and 0 if not is called the incidence vector of F. Let P_c(G) be the convex hull of the incidence vectors of the cuts of G, that is:

P_c(G) is called the cut polytope of G. The MAX-CUT problem in G is therefore equivalent to the linear program max{ωx : x ∈ P_c(G)}. The polytope P_c(G) is full dimensional [BAR 85].

6.4.1. Valid inequalities and separation

Let G = (V,E) be a graph. Let C be a cycle of G and F ⊆ C such that |F| is odd. Let δ(W) be a cut of G. Since δ(W) intersects C in an even number of edges, if F ⊂ δ(W) then δ(W) ∩ (C \ F) ≠ ∅. Consequently, the following constraints, introduced in [BAR 86], are valid for the polytope P_c(G):

[6.5] Equation 6.5

[6.6] Equation 6.6

It is not hard to see that every integer solution of the above system represents a cut of G. Consequently, these constraints induce an integer programming formulation for the MAX-CUT problem. Constraints [6.5] are called cycle inequalities, and inequalities [6.6] are called trivial inequalities. If the graph is complete, we can easily verify that the following cycle constraints (and the integrality constraints) are sufficient to formulate the problem as an integer program:

[6.7] Equation 6.7

[6.8] Equation 6.8

Note that constraints [6.7] and [6.8] are none other than inequalities [6.5] where the cycle C is a triangle. Constraints [6.7] and [6.8] are called triangular inequalities. Note also that these inequalities imply trivial inequalities [6.6]. The polytope given by inequalities [6.5] and [6.6] is called the semi-metric polytope, and the polytope given by the triangular inequalities is called the metric polytope. Note that the variables of the metric polytope correspond to the different pairs of nodes of the graph, and, consequently, its dimension is . We can verify that the semi-metric polytope is none other than the projection of the metric polytope on the edges space.

Given a cycle C, a chord of C is an edge whose two extremities are in C and are not consecutive when going through C. Theorem 6.1, given by Barahona and Mahjoub [BAR 86], establishes necessary and sufficient conditions for constraints [6.5] and [6.6] to define facets of P_c(G).

THEOREM 6.1.–

1) An inequality [6.5] defines a facet of P_c(G) if and only if C does not have a chord.

2) An inequality x(e) ≥ 0 (x(e) ≤ 1) defines a facet of P_c(G) if and only if e does not belong to a triangle.

The separation problem associated with a system of inequalities of , given a solution , consists of establishing whether satisfies Ax ≤ b, and, if not, finding an inequality ax ≤ α of Ax ≤ b that is violated by . An algorithm that solves a separation problem is called a separation algorithm. Grötschel et al. [GRÖ 81a] showed that the optimization problem is polynomial over a polyhedron {x ∈ ⁿ : Ax b} if and only if the separation problem associated with Ax b is polynomial. This equivalence between optimization and separation yielded a large evolution in polyhedral approaches in combinatorial optimization. Indeed, in the light of this equivalence, an efficient separation algorithm for a family of valid constraints for a combinatorial optimization problem would be a central element in any cutting plane algorithm for the problem.

Since constraints [6.5] and [6.6] formulate the maximum cut problem as an integer program, and, from theorem 6.1, can define facets, it would be useful to have a polynomial time separation algorithm for these constraints. This would allow their efficient use in the context of a cutting plane method for the problem. It is clear that constraints [6.6] can be separated in polynomial time. In what follows, we show that constraints [6.5] can also be separated in polynomial time. This algorithm is given by Barahona and Mahjoub [BAR 86].

By making a change from variables x(e) to 1 − x(e), constraints [6.5] can be written:

[6.9] Equation 6.9

If , the problem of separating constraints [6.5] relative to reduces to verifying whether for every C, by associating a weight 1 − (e) with an odd number of edges of C and a weight (e) with the other edges of C, the total weight of C is greater than or equal to 1. To solve this problem, we will consider an auxiliary graph.

Let G′= (V′, E′) be the graph obtained from G in the following way. For every vertex i of G, we consider two vertices i′ and i″ in G′, and for every edge ij of G, we consider the edges i′j′ and i″j″ with a weight (ij), and the edges i″j′ and i″j′ with a weight 1 – (ij). As we will see later, the problem of separating constraints [6.9] reduces to determining a shortest path in G′ between two vertices i′ and i″. Let us denote by E_ij the set of edges {i′j′, i′j″, i″j′, i″j″} for ij ∈ E. Note that every chain in G′ between two vertices i′ and i″, which uses at most one edge from each set E_ij, corresponds to a cycle in G that goes through the vertex i. Let us now use ( respectively) to refer to the set of nodes i′ (i″ respectively) for i in V. Let us note that an edge e in G′ has a weight 1 − if and only if e is between and . Let Λ_i be a shortest path in G′ between a vertex i′ and a vertex i″. Λ_i then uses an odd number of edges e with a weight . If Λ_i goes through two edges of type i′j′ and i″j″ or i′j″ and j′i″, there must be a path _i that links the vertices j′ and j″, of weight less than or equal to that of Λ_i. This implies that if Λ* is a shortest path among the paths Λ_i then Λ* can be chosen in such a way that it intersects each E_ij in at most one edge and, consequently, it corresponds to a cycle C in G. If the weight of Λ* is 1 then no constraint of type [6.9] is violated. If not, then by considering F as the set of edges e of Λ* that have a weight , C and F induce a constraint of type [6.9] that is violated by .

Furthermore, it is easy to see that every pair C, F, where C is a cycle of G and F is an odd subset of C, which induces a violated constraint of type [6.9], corresponds to a path between two vertices i′ and i″of G′ that uses at most one edge from each E_ij and has a weight strictly less than 1.

Consequently, to separate constraints [6.5], we calculate a shortest path in G′ between each pair of vertices i′, i″, and we consider the shortest among all these paths. If the weight of this latter is 1 then all constraints [6.5] are satisfied by . Otherwise, a violated constraint is then found. Since all the weights in G′ are positive, calculating a shortest path between two vertices can be carried out in O(n²) (where n = |V|). The separation of constraints [6.5] can therefore be carried out in O(n³).

Since constraints [6.5] and [6.6] can be separated in polynomial time, the MAX-CUT problem can therefore be solved in polynomial time in graphs whose cut poly-tope is given by these constraints. Theorem 6.2, given by Barahona and Mahjoub in [BAR 86], characterizes these graphs.

THEOREM 6.2.– Constraints [6.5] and [6.6] completely describe the polytope P_c(G) if and only if G is not contractible to K₅.

From theorem 6.2, the maximum cut problem can be solved in polynomial time using a cuts algorithm in graphs that are not contractible to K₅. Since planar graphs belong to this class, this theorem also implies that the maximum cut problem can be solved in polynomial time using a cutting plane algorithm in these graphs.

A graph is called a p-wheel bicycle if it consists of a cycle of length p and two nodes u, v adjacent to each other and adjacent to every node of the cycle. The edge uv is called the bicycle axis. Barahona and Mahjoub [BAR 86] showed that if (W, T) is a (2k + 1)-wheel bicycle, then the constraint:

[6.10] Equation 6.10

is valid for P_c(G). Furthermore, they showed the following result.

THEOREM 6.3.– Inequality [6.10] defines a facet of P_c(G). In [GER 85], Gerards showed that inequalities of type [6.10] can be separated in polynomial time. The separation algorithm is as follows. Let us consider a solution . We may assume that trivial inequalities [6.6] and inequalities:

[6.11] Equation 6.11

are satisfied by . This is clear for inequalities [6.6]. Constraints [6.11] can also be easily verified (through enumeration). Notice also that constraints [6.11] are none other than the cycle inequalities when F = C. They can therefore be verified with the help of the algorithm given above. Now, for every edge uv ∈ E, let us consider the sets V_uv = {w ∈ V : uw, vw ∈ E}, E_uv = {ww′ ∈ E : w, w′ ∈ V_uv}, and for every edge ww′ ∈ E_uv, let us state . It is easy to see that a bicycle of axis uv exists for which the associated constraint [6.10] is violated by if and only if an odd cycle in the graph (V_uv, E_uv) exists whose weight with respect to y is less than (uv). Furthermore, we have 2y(ww″) = 4 − x({ww″, wu, w″u}) − x({ww″, wv, w′ v}). Since satisfies constraints [6.11], it follows that y ≥ 0. Since the problem of finding an odd cycle of minimum weight in a graph with non-negative weights is polynomial [GRÖ 81b], the problem of separating constraints [6.10] can also be solved in polynomial time.

To separate constraints [6.10], it suffices to consider the graph (V_uv, E_uv), the weight vector y, and to calculate an odd cycle of minimum length in that graph. If the weight of this cycle is ≥ (uv) then no constraint of type [6.10], induced by a bicycle whose axis is uv, is violated by . Otherwise, this cycle forms a bicycle with the edge uv, and the edges that link it to uv, whose associated constraint [6.10] is violated by .

Theorem 6.4, given in [BAR 86], describes a third family of facets of the polytope P_c(G).

THEOREM 6.4.– Let K_p = (W, T) be a complete subgraph of G of order p. Then the inequality:

[6.12] Equation 6.12

is valid for P_c(G). Furthermore, it defines a facet of P_c(G) if and only if p is odd.

Inequalities [6.12] can be separated in polynomial time if p is fixed.

Lifting is a technique that is often used in the context of polyhedral approaches to generate facets of a polyhedron in ⁿ from the facets of a polyhedron in , with n′ < n. Several lifting operations have been introduced for the cut polytope [BAR 86, DES 90, DES 94b, DEZ 97]. Among these operations, the one described below, called switching, is of particular interest.

THEOREM 6.5.– (Barahona and Mahjoub [BAR 86]). Let G = (V, E) be a graph and ax ≤ α an inequality that defines a facet of P_c(G). Let W ⊆ V . Set:

Then defines a facet of P_c(G).

Note that the switching operation, described below, was independently introduced by several researchers. As will be mentioned in section 6.6, this operation allows us to establish the polytope P_c(G) from the cuts cone.

The symmetric difference between two sets I and J, denoted by IΔJ, is the set (I\J)∪(J\I). If I and J are cuts then IΔJ is also a cut. Let C and D be two cuts of G, and let ax ≤ α be an inequality that defines a facet of P_c(G) such that ax^C = α. By applying theorem 6.5 to the constraint ax ≤ α related to the cut δ(W) = CΔD, we obtain an inequality bx ≤ β that defines a facet of P_c(G) and such that bx^D = β. We then have the following.

COROLLARY 6.1.– (Barahona and Mahjoub [BAR 86]). For every pair of cuts C and D, there is a biunivocal correspondence between the facets of P_c(G) containing x^C and those containing x^D.

6.4.2. Branch-and-cut algorithms

Cutting plane techniques have proved to be very efficient for solving hard combinatorial optimization problems ([APP 98, PAD 91, SCH 03], and Volume 1, Chapter 10). These are based on a complete or partial description of the solutions polyhedron by a system of linear inequalities. A cutting plane algorithm for a combinatorial optimization problem starts by solving a linear relaxation that contains a reasonable number of constraints. If the optimal solution found is feasible for the problem, it is therefore optimal. Otherwise, the algorithm generates constraints that are violated by the optimal solution, and solves the new linear relaxation. This procedure continues until either an integer solution feasible for the problem, and therefore optimal, is found, or it is no longer possible to generate further violated constraints. In this case, we use a branch-and-bound algorithm to obtain an optimal solution for the problem. We can apply the cutting plane algorithm again in order to calculate a bound of each subproblem in the branch-and-bound tree. This allows us to obtain better bounds and to further accelerate the resolution of the problem. Such an algorithm is called a branch-and-cut algorithm. Initially introduced by Padberg and Rinaldi [PAD 91] for the traveling salesman problem, this method is now widely used to solve combinatorial optimization problems exactly.

In the remainder of this section, we present certain branch-and-cut algorithms, based on the classes of constraints given above (and other families of valid inequalities), for solving problems related to the MAX-CUT problem.

In [BAR 89], Barahona et al. propose a branch-and-cut algorithm based on constraints [6.5] and [6.6] for solving program [6.3]. They develop a heuristic for generating violated cycles constraints. When this heuristic fails, they apply the exact separation algorithm given above. The experimental results presented in [BAR 89] show the superiority of the cutting plane approach with respect to other solving techniques. De Simone and Rinaldi [DES 94a] develop a branch-and-cut algorithm for the MAX-CUT problem that uses constraints [6.5] and [6.6] and the so-called hyper-metric constraints [DEZ 97]. (Hypermetric constraints will be discussed in detail in section 6.6.3). The approach used by De Simone and Rinaldi consists of establishing a feasible solution for the MAX-CUT problem (using a heuristic) and then proving that it is optimal. They show that the problem that consists of establishing whether a given cut is optimal reduces to the MAX-CUT problem. This result was independently obtained by [BAR 81b]. De Simone and Rinaldi also propose a heuristic for separating the hypermetric constraints. This is based on a reduction of the separation problem to the problem which consists of finding a cut whose weight satisfies a certain property in a particular complete graph. The algorithm proposed by De Simone and Rinaldi consists of just checking whether the initial feasible solution is optimal. In the opposite case, the algorithm provides an upper bound for the problem. The procedure may be used within the framework of a branch-and-cut algorithm for the MAX-CUT problem.

The first significant application of the cut polyhedron was proposed by Barahona et al. [BAR 88] for the basic spin glass problem presented in section 6.3. This problem has been particularly studied in the two-dimensional case with an exterior magnetic field and periodic boundary conditions. In terms of graphs, this corresponds to a square grid where the extremities of each line of the grid are merged (i.e. a torus) with a vertex that is adjacent to all the vertices of the grid representing the magnetic field. This type of model is very common in practice. It represents a simplification of an infinite square grid with a magnetic field. As has been highlighted in section 6.2, the MAX-CUT problem and therefore the underlying problem are NP-hard for this model. Two variants of this model have been intensively studied in the literature: the Gaussian model, where the interactions are established using a Gauss distribution, and the ±J model, where the interactions may only take the values +J and −J, where J is a positive value obtained from a particular distribution.

In [BAR 88], Barahona et al. develop a branch-and-cut algorithm for the Gaussian spin glass model, based on cycle and trivial constraints. They discuss separation heuristics for the cycle constraints. These latter are considered in the first phase before using exact separation. They present experimental results for grids of size up to 40 × 40. In [DES 95, DES 96], De Simone et al. study the same spin glass model, in both the Gaussian and ±J cases. They present results based on more than 20,000 instances solved using a branch-and-cut algorithm that only uses cycle and trivial constraints. Their algorithm allows us to solve instances on grids of a size that can be up to 100×100 without a magnetic field, and grids of a size that can be up to 50×50 with a magnetic field. Liers et al. [LIE 03b] consider the spin glass problem in k-regular graphs. (A graph is k-regular if each vertex is of degree k.) They discuss experimental results for 4-regular and 6-regular graphs with up to 1280 vertices.

Several studies in the literature present branch-and-cut algorithms for other variants of the spin glass model [BAR 88, DES 95, DES 96, JUN 98, LIE 03a, LIE 03b, PAL 03].

In [FRA 05], Frangioni et al. discuss optimization methods on the semi-metric polytope. In particular, they consider approaches based on Lagrangian relaxation and non-differentiable optimization.

6.4.3. The cut polyhedron

Given a graph G = (V, E), the cut polyhedron of G, denoted by Dom_c(G), is the dominant of the convex hull of the incidence vectors of the non-empty cuts of G, that is:

If a system of (non-negative) capacities is given with G then the minimum cut problem consists of finding a cut whose capacity is minimum. This problem can be solved in polynomial time by using the Gomory and Hu’s algorithm [GOM 61].

Other more recent effective algorithms have been developed for this problem [NAG 92, NAG 94, PAD 90]. The minimum cut problem is equivalent to the linear program min{cx : x ∈ Dom_c(G)}, where c is the vector of the capacities.

According to the equivalence between optimization and separation on a polyhedron [GRÖ 81a], it follows that the separation problem on the polyhedron Dom_c(G) can be solved in polynomial time.

Although the optimization problem (with non-negative weights) on Dom_c(G) is polynomial, Dom_c(G) is only known for small graphs. Alevras [ALE 99] gives complete descriptions of Dom_c(G) for complete graphs that have up to seven vertices. He also studies the directed version of the problem and characterizes Dom_c(G) in graphs that have up to five vertices. Alevras also presents valid inequalities that define facets of the cut polyhedron for both directed and non-directed variants in [ALE 99].

In [CON 04], Conforti et al. study the facial structure of the polyhedron Dom_c(G). They establish certain properties of the facets of Dom_c(G) and characterize the inequalities ax b that define facets of Dom_c(G) such that b ≤ 2 and the coefficients of the vector (a, b) are prime.

In [NGU 05], Nguyen shows that for every graph G = (V, E), the right-hand side b of a constraint that defines a facet of Dom_c(G) may be as large as possible, which answers a question given in [CON 04].

For a graph G = (V, E), let us consider the polyhedron:

known as the network synthesis polyhedron.

The polyhedron Syn(G) is studied in [COR 85, TAM 91]. Polyhedra Dom_c(G) and Syn(G) form what is called a blocking pair [FUL 71] (see Volume 1, Chapter 10), that is the facets of the polyhedron Syn(G) are given by the extreme points of the polyhedron Dom_c(G) and vice versa. The relationship between the two polyhedra Dom_c(G) and Syn(G) is discussed and compact formulations are proposed in [CON 00, CON 04].

6.5. Semi-definite programming (SDP) and the maximum cut problem

Having tackled the linear programming approach to solving the maximum cut problem, we examine another approach using semi-definite programming. Semi-definite programming is a generalization of linear programming and a special case of convex optimization, whose growth is fairly recent, for the most part since the 1980s–1990s. For notions on semi-definite programming, see, for example, [VAN 96]. We can summarize the attraction of semi-definite programming in three main points:

– since it is a generalization of linear programming, it allows us to model a wide variety of problems;

– it has interesting properties at the theoretical level (convexity, duality theory, etc.) and there are efficient algorithms for solving semi-definite programs;

– the quality of the approximation provided by algorithms based on semi-definite programming formulations.

More specifically, this section will deal with the advantages of such an approach when applied to the MAX-CUT problem. It is structured in the following way. A formulation of the problem using a semi-definite program is introduced in section 6.5.1. The quality of the approximation of this formulation is discussed in section 6.5.2. Finally, section 6.5.3 consists of a review of some works relying on semi-definite programming to solve the MAX-CUT problem.

6.5.1. Semi-definite formulation of the MAX-CUT problem

Without loss of generality, we consider a complete graph.

A formulation of the MAX-CUT problem in the form of a quadratic program is given by:

Note that the integrity constraints on the variables may be replaced by quadratic constraints of the form x_i(1 − x_i) = 0.

By the change of variables z = 1 − 2x, formulation (PQ1) is equivalent to the following formulation with variables with values in {−1,2}:

By introducing a variable Y_ij for every product z_iz_j, formulation (PQ2) is itself equivalent to the following formulation:

In formulation (PQ3), we note that the matrix Y is necessarily positive, semi-definite, and of order 1. By relaxing the (non-convex) constraint relating to its order, we obtain the following relaxation of the problem:

where Y 0 represents the constraint that forces the matrix Y to be positive semi-definite. In what follows, we denote by Z*_SDP₁ the optimal value of (SDP1). The positive semi-definite matrix Y can be expressed in the form Y = Q^TQ (Cholesky decomposition), with Q ∈ ^m×n, m n. In other words, in the last formulation, this comes down to associating a vector v_i in ^m located on the unit sphere (which corresponds to the constraint Y_jj = ||v_j||² = 1) with every vertex j of the graph in such a way that the scalar products optimize the objective. We will come back to such a geometric interpretation through the rounding procedure of Goemans and Williamson. Let us note that this formulation can be derived in different ways [TOD 01].

Poljak and Rendl [POL 95a] show that problem (SDP1) is equivalent to the following eigenvalue minimization problem (that is the optimal values of these two formulations are identical), introduced by Delorme and Poljak [DEL 93a, DEL 93b]:

[6.13] Equation 6.13

with:

[6.14] Equation 6.14

where L_G,w refers to the Laplacian of the weighted graph G, with coefficients l_ij = −w_ij if i ≠ j, and if not. For more details, see [POL 95b]. An overview of eigenvalue optimization methods can be found in [LEW 96, LEW 03].

It is worth noting that the SDP formulation can easily be obtained using the Lagrangian relaxation [LEM 99]. Indeed it is sufficient to replace the constraints z_j ∈ {−1, 1} with , which we can then dualize. Minimization of the dual problem leads to an SDP type condition guaranteeing that the bound is finite. This way of dualizing also gives the well-known Lovász’s bound for the maximum stable set problem (see [GRÖ 88]).

6.5.2. Quality of the semi-definite formulation

A particular advantage for such semi-definite relaxations of the MAX-CUT problem lies in their quality.

This has been clearly highlighted by Goemans and Williamson [GOE 94, GOE 95]. Using formulation (SDP1), they propose a random polynomial approximation algorithm for which they show a performance guarantee that is greater than α –∈ with ∈ > 0, a fixed value, and ) when all weights are positive. (By denoting by W(I) the cost of a feasible solution provided by this algorithm on an instance I of optimal value OPT(I), and by E[W(I)] the mathematical expectation of the cost of the solution found, the level of performance is given by inf E[W(I)]/OPT(I), where the infimum is taken on the set of the instances with OPT(I) strictly positive). Their method proceeds in the following way:

– solving formulation (SDP1) (which can be carried out in polynomial time within a fixed precision of ∈ > 0, for example by using the ellipsoid algorithm [GRÖ 81a]). In what follows, in order to simplify the presentation, we will assume its solution to be exact and we denote by X an optimal solution of (SDP1), by X = QQ^T a decomposition of X with Q ∈ ^n×m, by m n and q_i the i-th line vector of the matrix Q (such a decomposition exists for every positive semi-definite matrix, and can be calculated in polynomial time provided square roots can be computed);

– random uniform generation of a vector r on the unit sphere S_m = {x ∈ ^m | ||x|| = 1};

– return the cut δ(S) with S = {i | q_ir 0}.

Note that the constraint Y_jj = 1 imposes ||q_i|| = 1,∀i, that is all the vectors q_i are located on S_m. In this way, considering the hyperplane H_r of normal r that goes through the origin, the cut δ(S) is determined by the set of the vectors q_i located in a single half-space delimited by H_r.

By using the fact that the probability that an edge ij figures in the cut derived from this procedure is given by (with sgn(x) = 1 if x > 0, −1 if x < 0, and 0 otherwise), Goemans and Williamson show that , where represents the optimal value of MAX-CUT. From the above we deduce that , while rounding procedures based on linear relaxations give a performance guarantee of the order of .

More precisely, Karloff [KAR 96b] shows that the performance guarantee of the Goemans–Williamson algorithm is exactly equal to α, that is the level of approximation of the semi-definite relaxation used (i.e. the smallest value of the ratio ) as this has been determined by Feige and Schechtman [FEI 01b]. Karloff [KAR 96b] shows that this level cannot be improved by adding linear constraints in the semi-definite formulation. Consequently, other approaches must be developed with a view to obtaining potentially better levels of performance with regard to formulation (SDP1). Karloff’s results have been extended by Alon et al. [ALO 02], who establish that, denoting by t₀ the value of t that minimizes and :

– If , the level of performance guarantee equals α.

– If t₀ < A, the level of performance guarantee equals .

In other words, Goemans and Williamson’s level of performance guarantee is better when the proportion of the weight of the solution of (SDP1) is sufficiently large with respect to the sum of the weights taken over the set of the edges.

Delorme and Poljak [DEL 93a] establish analogies between the behavior of the optimal values of (SDP1) and of MAX-CUT when operations (for example switching, amalgam, vertex splitting, edge contraction) are carried out on the graph. More particularly, concerning the quality of the approximation provided by (SDP1), depending on the topology of the graph for the MAX-CUT case with costs all of value 1 on the edges, the authors show that:

– for every line-graph G^∗ of a graph G (that is G* is the graph with the edges of G as vertices and the pairs of vertices whose corresponding edges of G share a vertex, as edges), and where C₅ denotes a cycle with five vertices;

– p being fixed, 0 < p < 1; where G_n,p refers to a random graph over n vertices with the probability p for the existence of an edge.

where and refer to the maximum number of edges in a cut and the optimal value of the relaxation (SDP1), respectively.

Variants on the rounding procedure have been proposed with the aim of improving the performance guarantee level when it does not match the approximation ratio of the semi-definite relaxation. Thus, Zwick [ZWI 99] proposes carrying out a rotation of the vectors vi (corresponding to an optimal solution of the semi-definite relaxation) in a space of dimension 2n, before applying the rounding procedure using a random hyperplane, such as was described previously. This procedure is generalized by Feige and Langberg [FEI 01a]. These approaches allow us, in certain cases, to improve the level of performance guarantee of Goemans and Williamson’s original procedure. Other adaptations of this approach have allowed us to derive better levels of performance guarantee on instances that satisfy certain properties. For example, Halperin et al. [HAL 04] (using a reinforced semi-definite formulation of the problem) present a procedure with a performance level of the value of 0.9326 for graphs whose nodes have a degree of at most 3.

Mahajan and Ramesh [MAH 99] introduce a polynomial method which, when applied to an optimal solution of the semi-definite relaxation, allows us to establish deterministically a cut with an approximation ratio identical to that of Goemans and Williamson’s procedure.

Let us remember that the approximation ratio α of the latter was established under the hypothesis of all positive costs borne on the edges. Under the single condition L_G,w 0, Nesterov [NES 97] shows an approximation ratio of 2/π ≈ 0.63661 for Goemans and Williamson’s procedure.

Several authors have suggested a reinforcement of (SDP1) by adding the triangle inequalities to this formulation. Nevertheless, for this latter formulation, we do not know any better approximation ratio than 0.87856. In the general context of integer programming with Boolean variables, Lovász and Schrijver [LOV 91], as well as Lasserre [LAS 00], introduce operators to generate, recursively, semi-definite relaxations that represent better approximations of the integer problem. For a given polyhedron P = {x ∈ⁿ | Ax b,0 x 1}, by expressing as R^t⁺¹(P) = R(R^t(P)) the polytope obtained after t + 1 recursive applications of one of these two operators on P, the authors show that the convex hull of the integer solutions contained in P is obtained in at most n iterations, that is R(P) ⊇ R²(P)… ⊇ Rⁿ(P) = conv(P ∩ {0, 1}ⁿ). A fundamental property of these operators lies in the fact that, under certain conditions, if the optimization problem for P is polynomial then the same holds for R(P). For an illustration of the use of these operators, see [LAU 01, LAU 04]. The author also presents results on the smallest number of applications of these operators that is necessary for deriving the cut polytope (that is the smallest value oft such that the cut polytope corresponds to R^t(G)).

We should also mention that the decision problem that consists of determining whether the optimal value of the semi-definite relaxation is equal to the optimal value of the MAX-CUT problem is NP-complete [DEL 93a].

6.5.3. Existing works in the literature

At present, the interior point methods seem to be preferred for solving semi-definite relaxations. For an account of the use of these methods for semi-definite programming as well as elements on the use of semi-definite formulations in branchand-cut algorithms, see, for example [KRI 04b].

An alternative approach to interior point methods consists of using first- [KLE 96, KLE 98] or second-order [IYE 04] optimization methods to solve Lagrangian relaxations of such semi-definite formulations. In a general context (that is not specific to the MAX-CUT problem) Helmberg and Rendl [HEL 97] present a spectral bundle method for solving such semi-definite formulations. The authors aim is to take advantage of the special structure of matrices that appear in the formulation of various combinatorial optimization problems. Numerical experiments in relation to the MAX-CUT problem on instances of a large size are reported there, with emphasis on the advantage of the proposed approach compared to interior point methods. More recently, Helmberg [HEL 01] presented the application of this method with the generation of odd cycle inequalities in the formulation (SDP1). Nevertheless, for the instances under consideration (spin glass problems), the advantage of this approach is limited compared to classical linear programming approaches, with regard to the calculation times and the quality of the obtained bound. These limitations seem to be due to a slow convergence of the procedure on these instances.

In the general context, Krishnan and Mitchell [KRI 01] propose solving semi-definite programs under linear constraints in the following form:

using linear programming. More recently, the same authors presented an application of this approach [KRI 04a] in a branch-and-price method for solving the maximum cardinality cut problem.

Fischer et al. [FIS 06] propose the application of a “dynamic” spectral bundle method for solving semi-definite relaxations that have a large number of linear constraints. Their procedure is based on a Lagrangian relaxation of a set of linear constraints (generated dynamically). This approach is illustrated in particular for solving MAX-CUT (and the equipartition problem). In this case, the additional linear constraints considered in the semi-definite program are the triangular inequalities. Various results presented (on graphs of various densities, having between 100 and 2000 nodes) highlight the potential advantages of this approach in comparison with the application of interior point methods, especially on instances of large size.

Anjos and Wolkowicz [ANJ 01, ANJ 02] present two semi-definite formulations, “reinforced” relative to (SDP1), obtained by a lift and project type approach by carrying out two successive lifting operations on a formulation of MAX-CUT using Lagrangian relaxations. The quality of the bound provided by these relaxations compared with (SDP1) is demonstrated on a few instances (with 5 to 12 nodes). We can observe that one of these two relaxations leads to the optimal objective value in the majority of these cases. Some of their results have been extended by Laurent [LAU 04], who gives a comparison of different semi-definite relaxations of the MAX-CUT problem derived using Lovász/Schrijver and Lasserre’s operators.

Poljak and Rendl [POL 95b] propose solving the maximum cut problem by calculating eigenvalues based on formulation [6.13]. Calculation of φ(G, w) is carried out using a bundle method [SCH 88]. In addition to obtaining an upper bound, the authors propose a heuristic (rounding procedure) that uses the eigenvectors of λ_max(L_G,w + diag(u_opt)) associated with the three largest eigenvalues for calculating a lower bound, where u_opt refers to the optimal value of the correction vector u. Various numerical results on different types of graphs are given, which show particularly small relative differences between the two bounds calculated in this way. Experiments concerning the use of this formulation in a branch-and-bound type algorithm are mentioned, as well as certain elements of comparison with a bound that corresponds to the optimal objective value of a linear relaxation that includes the odd cycle inequalities.

6.6. The cut cone and applications

After dealing with different approaches to solving optimization problems on the cut polytope, we consider extensions related to the cut cone. In this section, we will first state the close links between the polyhedral structures of the cut polytope and the cut cone. Next we will deal with different applications of the cut cone related to semi-metrics and multiflow problems. For further details about the geometric and application aspects of the cut polytope and the cut cone such as, for example, in number geometry, functional analysis or quantum mechanics, see [DEZ 97].

6.6.1. The cut cone

The cut cone of a graph G = (V, E), denoted by C(G), is the cone generated by the incidence vectors of the cuts of G. In other words:

In the special case where G = K_n = (V, E_n) (a complete graph having n nodes), the associated cut cone will be denoted by C_n.

6.6.2. Relationship to the cut polytope

Although it constitutes a relaxation of the cut polytope, the facial structure of the cut cone C_n allows us to describe that of the cut polytope completely. Indeed, corollary 6.1 shows that the facets of P_c(G) may be obtained from the facets that go through an extreme point of P_c(G), that is from the facets that contain a given cut. Since the zero vector (which corresponds to the empty cut) belongs to P_c(G) (and C(G)), P_c(G) can be expressed in the form:

[6.15] Equation 6.15

with b < 0, A and E matrices, and b a column vector. From corollary 6.1, if P_c(G) is given by [6.15], it follows that:

[6.16] Equation 6.16

Reciprocally, if C(G) is given by [6.16] then P_c(G) can be obtained from C(G) by switching. This relationship between the cut polytope and the cut cone has been at the root of an extensive investigation of the cut cone during the last two decades [DEZ 92c, DEZ 92d, DEZ 97].

In the same way as for the cut polytope, the separation problem on the cut cone is NP-hard.

A relaxation of the cut cone is given by the following system of constraints:

In the case of weakly bipartite graphs, Seymour [SEY 81] established that these constraints completely describe C(G).

6.6.3. The semi-metric cone

The cut cone appears in various problems that use semi-metrics. Let us recall a few definitions here. Given a set S, an application d : S × S → ₊ that satisfies:

– d_ij = d_ji, ∀i, j ∈ S (symmetry);

– d_ii = 0,∀i ∈ S;

– dij d_ik + d_kj,∀i, j, k ∈ S (triangle inequalities)

is called semi-metric on S.

If, furthermore, d satisfies the property d_ij = 0 ==> i = j then d is qualified as being metric on S. In what follows, we denote by MET_n the cone generated by the semi-metrics on n points, called the semi-metric cone. By noting that every vector of C_n defines a semi-metric on V, we have C_n ⊆ MET_n.

Among these metrics, a special subset (hypermetrics) shows important connections with the cut cone. To introduce them, we give a few definitions.

Given a vector b ∈ ⁿ that satisfies , the inequality:

[6.17] Equation 6.17

is called a hypermetric inequality. The cone defined by the hypermetric inequalities HY P_n is called a hypermetric cone, that is:

satisfies [6.17] for every with }

Although the number of hypermetric inequalities is infinite, it has been shown that the cone HY P_n is polyhedral [DEZ 97], in other words the set of non-redundant hypermetric inequalities is finite.

Hypermetric inequalities constitute a generalization of triangle inequalities. Indeed, the inequality x_ij −x_ik −x_jk 0 corresponds to the hypermetric inequality obtained by setting b_i = b_j = 1, b_k = −1, and b_l = 0, ∀l ∈ V \ {i, j, k}. Moreover, hypermetric inequalities are valid for the cut cone. For this, we may consider the evaluation of the left-hand member of inequality [6.17] as an incidence vector of a cut defined by a set of vertices , where the last inequality stems from the conditions on the vector b. We therefore deduce C_n ⊆ HY P_n ⊆ MET_n.

In comparison with the semi-metric cone, the hypermetric cone therefore constitutes a better approximation of the cut cone. In fact, the family of hypermetric inequalities includes, triangular inequalities aside, other inequalities that define facets of the cut cone (see, for example, section 28.2 in [DEZ 97] for further details). We can nonetheless note that the state of complexity of the separation problem on the hyper-metric cone does not seem to be known at present (the complexity of certain related problems may suggest that it is NP-hard [AVI 93]).

With regard to formulation (SDP1) of MAX-CUT in the form of a semi-definite program, hypermetric inequalities can be interpreted as a reinforcement of constraints ensuring that the matrix Y is positive semi-definite. Denoting by X the matrix with entries x_ij, we have . In particular, for a vector with integer components ν ∈ ⁿ, we deduce that the following inequality is valid for the cut poly-tope: . Hypermetric inequalities therefore correspond to a special subclass of these inequalities: those for which the vector ν ∈ ⁿ satisfies . (Note that the preceding form of inequalities itself constitutes a subclass of inequalities valid for the cut polytope: the gap inequalities [DEZ 97, section 28.4]).

We mentioned earlier that every vector of C_n defines a semi-metric on V, but, conversely, every semi-metric does not necessarily belong to the cut cone. A characterization of the semi-metrics that belong to the cut cone is given by theorem 6.6.

THEOREM 6.6.– Let d ∈ ^E_n The following propositions are equivalent:

– d ∈ C_n;

– there exists n vectors u¹,…, uⁿ ∈ ^m (for a certain value of m) such that .

In other words, a semi-metric d belongs to the cut cone if and only if it is possible to associate with every vertex v_i a vector u_i in a space with the norm ||·||₁ such that the distance between the vertices v_i and v_j is given by d_ij.

In the case of a graph G = (V, E) weighted on the edges, the vector , with dij corresponding to the distance of a shortest chain linking the vertices v_i and v_j, is called the chain metric associated with the graph G. Embeddings into normed spaces such as those mentioned in theorem 6.6 may be used to establish correspondences between certain graphs. Let us consider, for example, the case where each component d_ij corresponds to the length of a shortest chain in the number of edges linking the vertices v_i and v_j. If an embedding of this metric exists with uⁱ ∈ {0, 1}^m, ∀i ∈ {1,…, n} then G can be interpreted as a subgraph of the one corresponding to a hypercube (whose vertices correspond to the set {0, 1}^m and whose edges link two vertices for which exactly one coordinate is different). So we can observe here that the distance d_ij corresponds to the Hamming distance between the vectors uⁱ and u^j. An advantage of such embeddings is to give a more simple representation for a given graph, which can be used in various applications (like message routing in telecommunications networks, for example) [DEZ 97, part III]. Thus semi-metrics for which there exist embeddings in a normed space (with norm ||·||₁) play a special role in relation to the existence of multiflows; a role that we briefly present here.

6.6.4. Applications to the multiflow problem

We can define a multiflow problem in the following way. Let us consider a telecommunications network represented by a graph G = (V, E), where V refers to the set of the nodes, |V | = n, and E refers to the set of the links that transmit data between two nodes. A capacity c_e, which limits the amount of data that can be transmitted simultaneously, is defined for each edge e ∈ E. Moreover, we consider a set of simultaneous communications demands to be satisfied between pairs of vertices. The latter is represented by the demand graph H = (T, R), with T ⊆ V, and whose set of edges R corresponds to the pairs of nodes between which a demand must be satisfied. A valuation g_r is associated with each edge r ∈ R and corresponds to the quantity demanded between its extremities. For a given capacity vector c and a demand vector g (in what follows, we consider the extension of these vectors in ^E_n with zero coefficients), we then need to establish for each demand a flow on G to satisfy it while respecting the capacity constraints. A multiflow is said to be integer if for every demand r ∈ R, all components of the flow f_r are integral; otherwise it is said to be fractional.

A necessary and sufficient condition for the existence of a fractional multiflow is given by theorem 6.7, introduced independently by Iri [IRI 71], and Onaga and Kakusho [ONA 71], and reformulated by Lomonosov [LOM 85] as follows.

THEOREM 6.7.– An instance of the multiflow problem has a fractional solution if and only if the following inequalities (called semi-metric inequalities) are satisfied: (c − g)^Td 0, ∀d ∈ MET_n.

The restriction of the semi-metric inequalities to the vectors din C_n, called the cut condition, is therefore a necessary, and sometimes sufficient, condition for the existence of a multiflow: this is notably the case if there is one single demand to satisfy (Ford–Fulkerson’s theorem [FOR 56]), as well as for certain special graphs, as is illustrated by proposition 6.1 [LOM 85, SEY 80]. (We say that Euler’s condition is satisfied when for given integer vectors c and g, the quantity is even for every vertex v ∈ V, where δ_E(v) and δ_R(v) refer to the cuts relative to v in the graphs G and H, respectively.)

PROPOSITION 6.1.– If the demand graph H = (T, R) is simple and has no isolated vertex then the following propositions are equivalent:

1) For every support graph G = (V, E), T ⊆ V, for every capacity vector , and for every demand vector , the cut condition implies the existence of a fractional multiflow.

2) For every support graph G = (V, E), T ⊆ V, and for every capacity vector and demand vector , the cut condition and Euler’s condition imply the existence of an integer multiflow;

3) H = K₄ or H = C₅ or H is the union of two stars.

Another result concerning the cut condition for mulitflow problems that makes use of the topology of the graph G + H (G + H = (V, E ∪ R) by taking into account the multiplicity of the edges, that is an edge of multiplicity m₁ in G and m₂ in H has a multiplicity of m₁ + m₂ in G + H) is given by the following proposition established by Seymour [SEY 81].

PROPOSITION 6.2.– A graph G = (V, E′) does not have K₅ as minor if and only if for every R ⊆ E′ and every the cut condition (taking the subgraph generated by E′\ R denoted by G[E′ \ R] as support graph and G[R] as demand graph) implies the existence of a multiflow. If, furthermore, the vector c is integer and Euler’s condition is satisfied then an integer multiflow exists.

For other results on multiflows making use of the cut condition, see Schrijver [SCH 03, chap. 70-75] and Deza et al. [DEZ 94], and Avis and Deza [AVI 91] for complementary elements on applications of the cut cone and cut polytope.

6.7. Approximation methods

The MAX-CUT problem being NP-hard, an alternative to an exact resolution consists of developing polynomial approximation methods. In what follows, an algorithm will be called a C-approximation algorithm for the maximum cut problem if for every instance of the problem it returns a cut of weight W which satisfies: .

Among the approximation methods developed for the MAX-CUT problem, we start with those that have performance guarantees, before dealing with those that do not.

6.7.1. Methods with performance guarantees

One of the first algorithms with a performance guarantee for the maximum cut problem seems to have been proposed by Sahni and Gonzalez [SAH 76]. It is a deterministic algorithm (greedy) that in fact solves the maximum k-multicut problem (which consists of partitioning the set of the vertices into k subsets in such a way that the sum of the weight of the edges between different elements of the partition is maximum) with an approximation ratio 1/k and therefore of for the MAX-CUT problem for the case where all costs on the edges are positive. (The maximum k-multicut problem will also be referred to in section 6.8.4.) (For the case where costs on the edges are unrestricted, this algorithm finds a cut of cost greater than or equal to . This approximation is identical to that in the procedure that consists of selecting randomly and independently, with a probability of , the vertices that define the cut returned. More recently, Goemans and Williamson [GOE 95] introduced an algorithm with an approximation ratio α ≈ 0.87856 (for the case of positive costs), presented in section 6.5.2 and to which we refer the reader for various developments in relation to this procedure. A common feature of the methods that we have just described is the fact that their approximation (or performance) ratio is constant. The methods that we will now cover have an approximation ratio that depends on a precision given as an input parameter.

As a complement to the notion of NP-completeness, various works have sought to better characterize the complexity of NP-hard problems in terms of approximation [ARO 98]. We start by presenting results concerning the inapproximability of MAX-CUT before introducing results concerning approximations carried out in polynomial time.

DEFINITION 6.1.– A polynomial time approximation scheme (PTAS) for a maximization problem is a family of algorithms such that for every ε > 0, A_ε is an (1 – ε)-approximation algorithm polynomial in the size of the input data for fixed ε.

MAX-CUT in the general case is a MAX-SNP-hard problem. In other words, no polynomial approximation scheme exists for solving this problem unless P = NP [ARO 92]. More exactly, Håstad [HÅS 01] shows that if P ≠ NP then, for every ε > 0, no polynomial -approximate algorithm exists for the MAX-CUT problem. For the special case of 3-regular graphs (that is the degree of each node has value 3), it is NP-hard to approximate MAX-CUT beyond an approximation ratio of 0.997 [BER 99].

We mention below families of instances of the MAX-CUT problem for which a polynomial approximation scheme exists. To do this, we start by introducing the notion of δ-dense graphs. A graph with n nodes is said to be δ-dense if its number of edges is greater than or equal to δn²/2, for fixed δ > 0. It is said to be δ-dense everywhere if its minimum degree is greater than or equal to δn. Let us note that the MAX-CUT problem restricted to the family of instances everywhere δ-dense remains NP-hard. Fernandez de la Vega [FER 96] proves the existence of a PTAS for solving the MAX-CUT problem in the case of all costs being of value 1 on the edges for everywhere δ-dense graphs. These studies have been extended by Arora et al. [ARO 99], proving the existence of a PTAS in the same case (that is uniform costs of value 1) for δ-dense graphs. In this last case, the method proposed consists of first randomly choosing a restricted set of vertices (with a cardinality in O(log(n))). All the possible configurations of these vertices in a cut (that is 2^O(log(n)) = n^O⁽¹⁾) are then considered. For each of them, a linear program (derived from a quadratic formulation of the maximum cut problem and taking into account the current configuration for the vertices chosen at the start) is then solved. Then a rounding procedure is applied to the fractional solution found.

Fernandez de la Vega and Karpinski [FER 00] have proved the existence of a PTAS for instances of the weighted MAX-CUT problem that satisify particular conditions concerning the distribution of the (positive) weights assigned to the edges of the graph, described as dense. Fernandez de la Vega and Kenyon [FER 01] present a polynomial approximation scheme for the “metric” MAX-CUT problem (by reducing such instances of MAX-CUT to dense weighted instances). This concerns a particular form of MAX-CUT instances where each vertex i of the (complete) graph may be associated with a point P_i in a Euclidean space. The cost of an edge ij corresponds to the distance between the points associated with its extremities P_i and P_j. Note, however, that we do not know whether the MAX-CUT problem in its “metric” version is NP-hard.

6.7.2. Methods with no guarantees

Finally we deal with methods of solving MAX-CUT that have no guarantees. Among such methods are various metaheuristics [DRÉ 03] such as simulated annealing, genetic algorithms, etc. For an evaluation of such approaches for the MAX-CUT problem see, for example, [DOL 99]. In particular, the authors compare Goemans– Williamson’s method [GOE 94, GOE 95] with different combinatorial and randomized procedures (including a genetic algorithm) on various instances of MAX-CUT with costs of value 1 on each edge. Their results highlight the fact that heuristic approaches can constitute an interesting alternative to semi-definite programming with regard to calculation times and the quality of the obtained solution. This last point of view is also illustrated by numerical experiments carried out with other randomized methods proposed by Festa et al. [FES 02], who compared it with a method based on semi-definite programming [BUR 01].

Two approximation algorithms based on rounding techniques were proposed in [NET 06].

6.8. Related problems

The MAX-CUT problem is closely related to several known problems in the literature. In this section, we discuss some of these problems.

6.8.1. Unconstrained 0–1 quadratic programming

Let us consider the following unconstrained 0 − −1 quadratic program:

[6.18] Equation 6.18

where c is a row n-vector line and Q an upper triangular n × n matrix with a zero diagonal. Note that problem [6.18] is of the same type as problem [6.3].

Problem [6.18] has been studied from a polyhedral point of view by Padberg in [PAD 89].

The quadratic terms x_ix_j can be linearized by considering a new variable yij ∈ {0, 1} and the constraints:

[6.19] Equation 6.19

for every 1 ≤ i < j ≤ n.

In fact, it is easy to see that y_ij = x_ix_j, x_i,x_j,y_ij ∈ {0,1} is equivalent to constraints [6.19]–[6.23]. Hence program [6.18] can be written as:

[6.24] Equation 6.24

Thus, problem [6.18] reduces to a 0 − −1 integer programming problem. Let PQⁿ be the convex hull of the solutions of [6.24]. Therefore problem [6.24] reduces to optimizing a linear function on the polytope PQⁿ. PQⁿ is called the Boolean quadric polytope. This polytope was introduced and studied by Padberg [PAD 89]. As was shown in De Simone [DES 90], this polytope can be obtained from the cut polytope using a simple affine transformation. To do this, let us consider the complete graph K_n₊₁ = (V, E), where V = {0, 1,…, n}, and the application φ that transforms a vector z = ((z_ij)0≤i<j≤n) into a vector y = ((y_ij)1≤i<j≤n) such that:

It is not hard to see that the solutions (x, y) of problem [6.24] are precisely the images of the incidence vectors of the cuts of K_n₊₁ using the application φ (after stating and . Application φ is a bijection that transforms the cut polytope in K_n₊₁ into the quadric Boolean polytope PQⁿ. Note that problem [6.4] is equivalent to problem [6.24] through the bijection φ. Consequently, every property related to the cut polytope can be transformed into an equivalent result for the quadric Boolean polytope and vice versa. For more details on the quadric Boolean polytope, see [DES 90, PAD 89].

6.8.2. The maximum even (odd) cut problem

In this section, we consider complete graphs. Let K_n be a complete graph over n vertices, and let {1,…, n} be the set of these vertices. For even n, given a subset of vertices S ⊆ {1,…, n}, the cut δ(S) is said to be even (or odd respectively) if S and {1,…, n} \ S are of even cardinality (or odd respectively), or, in an equivalent way, the cut δ(S) is of even cardinality (or odd respectively). Given weights on the edges, the maximum even (odd) cut problem consists of finding an even (odd) cut of maximum total weight. If n is odd, it is clear that every cut has an even cardinality, and the maximum even cut problem is none other than the MAX-CUT problem. In what follows, we assume that n is even.

The maximum even cut problem was considered by Deza and Laurent in [DEZ 93b]. In particular, they studied the relationship between the cut polytope, the even cut polytope, the odd cut polytope, and their cones. By using the switching operation given in section 6.4.1, we can see that the facets of the odd cut polytope are precisely the liftings using the switching operation with respect to an even cut of the facets of the even cut polytope, and vice versa. Consequently, the two even and odd cut polytopes are equivalent. Deza and Laurent [DEZ 93b] also show that the MAX-CUT problem can be reduced to the maximum even cut problem. This implies that this latter problem is NP-complete, and that it is as hard to study as the MAX-CUT problem. The maximum odd cut problem is also NP-complete using switching. Families of facets of the even cut polytope, related to those of the cut polytope, as well as lifting procedures, are also examined in [DEZ 93b].

6.8.3. The equipartition problem

Given a graph G = (V, E), a cut δ(S) in G is said to be an equicut if or , otherwise it is said to be inequicut. If G has weights on the edges, the equipartition problem is to establish an equicut of maximum (or minimum) weight. This problem also has applications in spin glass models in statistical physics. It is NP-complete in general. Conforti et al. present a facial study of the problem in [CON 90a] and [CON 90b]. They characterize the dimension of the associated polytope. They study the relationship between the facets of the cut polytope and those of the equicut polytope, and describe facets specific to this latter polytope. In [DEZ 93a], Deza et al. consider the inequicut cone of a complete graph K_n, that is the cone generated by the inequicuts of K_n. Since the inequicut polytope contains the origin (the cut δ({1, …, n}) is the zero vector), the facets of the inequicut cone are precisely the facets of the inequicut polytope that contain the origin. Deza et al. [DEZ 92c] discuss the relationship between the cut polytope, the equicut polytope, and the inequicut cone. They show in particular that facets of the equicut polytope and of the inequicut cone can be obtained from the cut cone using lifting operations. They also identify several families of facets of the inequicut cone. In [DEZ 92b], Deza and Laurent discuss the k-uniform cut cone of a complete graph K_n, where a k-uniform cut is a cut δ(S) such that |S| = k or n — k and |S|, n − |S| are even (odd). For further details on these polyhedra, see [DEZ 97].

Note that it is not hard to see that the weight of every cut is between and where λ₂ is the second eigenvalue of the Laplacian (introduced in section 6.5.1), and λ_max is its largest eigenvalue. The eigenvectors associated with these eigenvalues are often used heuristically to construct cuts of a given size.

6.8.4. Other problems

The maximum cut problem is also related to other combinatorial problems, for example the multicut problem. Given a graph G = (V, E) and a partition V₁,…, V_k of V (that is V_i ∩ Vj = ∅ for all 1 ≤ i < j ≤ k and , the set of edges uv, where u and v belong to different elements of the partition, is called a multicut. A multicut with k elements is said to be a k-multicut. The following problems, linked to multicuts, have been discussed in the literature:

1) the multicut problem (MP(G)): given weights on the edges, find a multicut of maximum weight;

2) the k^≤-multicut problem (MP(G, k^≤): given weights on the edges and an integer k ≥ 2, find an h-multicut of maximum weight such that h ≤ k;

3) the k^≥-multicut problem (MP(G, k^≥): given weights on the edges and an integer k ≥ 2, find an h-multicut of maximum weight such that h ≥ k;

4) the k-multicut problem (MP(G, k)): given weights on the edges and an integer k ≥ 2, find a k-multicut of maximum weight.

These problems have applications in various domains such as network design, VLSI circuits, and data analysis. They have been widely studied and their associated poly-topes in particular have received much attention.

The MP(G, 2^≤) problem is none other than the MAX-CUT problem. The MP(G, k) and MP(G, k^≤) problems have been studied by Chopra and Rao [CHO 93]. They have proposed formulations in the form of integer programs and have discussed the associated polytopes. The MP(G) problem has been considered by Grötschel and Wakabayashi [GRÖ 89b, GRÖ 90]. In fact Grötschel and Wakabayashi have studied the clique partitioning polytope. Given a complete graph K_n, a clique partitioning is the complementary of a multicut in K_n. The multicut polytope can therefore be obtained from the clique partitioning polytope through the transformation: x := 1 − x. In [GRÖ 90], the authors describe facets of the clique partitioning polytope, and in [GRÖ 89b], they develop a cutting plane algorithm for the problem. In [DEZ 92a], Deza et al. study the polytopes associated with MP(G, k^≤) and MP(G, k^≥). They describe facets for these polyhedra induced by structures called webs. Such inequalities have previously been introduced by Deza and Laurent for the cut cone [DEZ 92c, DEZ 92d].

The MP(G, k) problem has also been intensively studied in the last few years. It has been shown that this problem can be solved in polynomial time when k is fixed [GOL 94, KAR 96a], and is NP-hard when k is part of the data of the problem [GOL 94]. Several approximation algorithms have also been developed for the problem [GAR 97, SAR 95, VAZ 01].

A strong relationship also exists between the MAX-CUT problem and the stable set problem. See [GIA 06] for further details on this subject.

It is appropriate to recall that the maximum cut problem is a fundamental problem in combinatorial optimization that is related to several other problems. We have already mentioned the minimum cut problem. A variant on this problem is the minimum T-cut problem, where we need to find a cut δ(W) of minimum weight such that T ∩ W is of odd cardinality, given that T is a subset of even cardinality. This problem is also an easy problem to solve [PAD 82].

In certain cases, directed graphs are more appropriate for modeling practical situations. The maximum cut problem can then be transformed into a maximum directed cut problem, where a directed cut is a set of arcs of the form δ⁺(W) (the arcs having their initial extremity in W and their terminal extremity in its complementary). This problem, which is generally NP-hard, has also received much attention from the scientific community, and various algorithms have been proposed (cutting plane algorithms, semi-definite programming algorithms, etc.) [GOE 95, HÅS 01].

In another variant of the maximum directed cut problem, we can require that δ⁻(W) = ∅ in order to model certain practical situations. More precisely, we seek a cut δ⁺(W) of maximum weight that separates two given vertices r and s such that δ⁻(W) = ∅. This problem is polynomial in acyclic directed graphs such that each arc belongs to at least one path that links r and s with positive weights. The algorithm used to solve this problem comes from the minimum flow–maximum cut theorem, which is a an analog of the maximum flow–minimum cut theorem. In fact, if we consider the weights of the arcs w(e) as demands, it is not hard to see that the minimum flow that we must send from r towards s, in such a way that the value of the flow on each arc e is at least equal to w(e), is equal to the value of the maximum directed cut that separates r and s and satisfies the constraint δ−(W) = ∅ (see [SCH 03]).

Several other cut problems have been studied (a cut that minimizes the ratio of two weights [AUM 96], b-balanced cuts [SHM 97], etc.). We refer the reader to the scientific literature for further details on these various problems.

6.9. Conclusion

In this chapter, we have discussed the maximum cut problem. In particular, we looked at the algorithmic aspects of the problem and of its associated polytope. We presented certain applications of the problem to statistical physics and to unconstrained Boolean quadratic programming. We discussed certain branch-and-cut algorithms based on the linear relaxation of the problem. We presented some formulations of the maximum cut problem in terms of semi-definite programming, and discussed approaches that use interior point techniques. We also mentioned the relationship between the cut polytope and the cut cone, and described certain applications of the latter to multiflow problems and to other domains. Approximation methods with and without guarantees were also presented. Lastly, we discussed certain combinatorial optimization problems related to maximum cut problems.

With many applications in several scientific branches, the maximum cut problem and some of its variants belong to the problems that have driven the development of combinatorial optimization techniques. Polyhedral studies conducted on the maximum cut problem are part of the first studies that showed the advantages of these approaches. The use of semi-definite programming to develop algorithms with a performance guarantee also started with the maximum cut problem. In reality, most of the techniques used in combinatorial optimization have been used in one way or another to solve cut problems: randomized algorithms, approximation algorithms, linear programming, quadratic programming, SDP programming, study of special polynomial cases, including the planar graphs case, inapproximability results, Lagrangian relaxation, eigenvalue optimization, heuristics, etc.

We think that cut problems will continue to arouse interest in the scientific community because of their multiple applications and the new approaches that will have to be developed to solve larger instances.

6.10. Bibliography

[ALE 99] ALEVRAS D., “Small min cut polyhedra”, Mathematics of Operations Research, vol. 24, p. 35–49, 1999.

[ALO 02] ALON N., SUDAKOV B., ZWICK U., “Constructing worst case instances for semidefinite programming based approximation algorithms”, SIAM J. Discrete Mathematics, vol. 15, p. 58–72, 2002.

[ANJ 01] ANJOS M., WOLKOWICZ H., Geometry of semidefinite max-cut relaxations via ranks, Report, CORR 2001-39, University of Waterloo, 2001.

[ANJ 02] ANJOS M., WOLKOWICZ H., “Strengthened semidefinite relaxations via a second lifting for the max-cut problem”, Discrete Applied Mathematics, vol. 119, p. 79–106, 2002.

[APP 98] APPLEGATE D., BIXBY R., CHVÁTAL V., COOK W., “On the solution of traveling salesman problems”, Proceedings of the International Congress of Mathematicians, Berlin 1998-Volume III: Invited Lectures, Documenta Mathematica Extra Volume ICM 1998 III, Fischer G., Rehmann U. Eds., p. 645–656, 1998.

[ARO 92] ARORA S., LUND C., MOTWANI R., SUDAN M., SZEGEDY M., “Proof verification and hardness of approximation problems”, Proceedings of the 33rd IEEE Symposium on Foundations on Computer Science, p. 14–23, 1992.

[ARO 98] ARORA S., “The approximability of NP-hard problems”, Proceedings of the 30th ACM Symposium on Theory of Computing, p. 337–348, 1998.

[ARO 99] ARORA S., KARGER D., KARPINSKI M., “Polynomial time approximation schemes for dense instances of NP-hard problems”, Journal of Computer and System Sciences, vol. 58, p. 193–210, 1999.

[ASS 80] ASSOUAD P., “Plongements isométriques dans L′ : aspect analytique”, Séminaire d’initiation à l’analyse, vol. 14, p. 1–23, 1979-1980.

[AUM 96] AUMANN Y., RABANNI Y., “An O(logk) approximate min-cut = max-flow theorem and approximation algorithms”, SIAM Journal on Computing, vol. 27, p. 291–301, 1996.

[AVI 91] AVIS D., DEZA M., “The cut cone: L′-embeddability, complexity and multicommodity flows”, Networks, vol. 21, p. 595–617, 1991.

[AVI 93] AVIS D., GRISHUKHIN V., “A bound on the k-gonality of facets of the hypermetric cone and related complexity problems”, Computational Geometry: Theory and Applications, vol. 2, p. 241–254, 1993.

[BAR 81a] BARAHONA F., Balancing signed graphs of fixed genus in polynomial time, Tecnical Report, Departement of Mathematics, University of Chile, 1981.

[BAR 81b] BARAHONA F., Personal communication, 1981.

[BAR 83] BARAHONA F., “The max-cut problem on graphs not contractible to K₅”, Operations Research Letters, vol. 2, p. 107–111, 1983.

[BAR 85] BARAHONA F., GRÖTSCHEL M., MAHJOUB A. R., “Facets of the bipartite sub-graph polytope”, Mathematics of Operations Research, vol. 10, p. 340–358, 1985.

[BAR 86] BARAHONA F., MAHJOUB A. R., “On the cut polytope”, Mathematical Programming, vol. 36, p. 157–173, 1986.

[BAR 88] BARAHONA F., GRÖTSCHEL M., JÜNGER M., REINELT G., “An application of combinatorial optimization to statistical physics and circuit layout design”, Operations Research, vol. 36, p. 493–513, 1988.

[BAR 89] BARAHONA F., JÜNGER M., REINELT G., “Experiments in quadratic 0 - 1 programming”, Mathematical Programming, vol. 44, p. 127–137, 1989.

[BER 83] BERGE C., Graphes et hypergraphes, Dunod, Paris, 1983.

[BER 99] BERMAN P., KARPINSKI M., On Some Tighter Inapproximability Results, Report num. 99-23, DIMACS, 1999.

[BUR 01] BURER S., MONTEIRO R., ZHANG Y., “Rank-two relaxation heuristics for max-cut and other binary quadratic programs”, SIAM Journal on Optimization, vol. 12, p. 503–521, 2001.

[CHO 93] CHOPRA S., RAO M. R., “The partition problem”, Mathematical Programming, vol. 59, p. 87–115, 1993.

[CON 90a] CONFORTI M., RAO M. R., SASSANO A., “The equipartition polytope: part I”, Mathematical Programming, vol. 49, p. 49–70, 1990.

[CON 90b] CONFORTI M., RAO M. R., SASSANO A., “The equipartition polytope: part II”, Mathematical Programming, vol. 49, p. 71–91, 1990.

[CON 00] CONFORTI M., RINALDI G., WOLSEY L., On the Cut Polyhedron, Preprint, 2000.

[CON 04] CONFORTI M., RINALDI G., WOLSEY L., “On the cut polyhedron”, Discrete Mathematics, vol. 277, p. 279–285, 2004.

[COR 85] CORNUÉJOLS G., FONLUPT J., NADDEF D., “The traveling salesman on a graph and some related integer polyhedra”, Mathematical Programming, vol. 33, p. 1–27, 1985.

[DEL 93a] DELORME C., POLJAK S., “Combinatorial properties and the complexity of a max-cut approximation”, European Journal of Combinatorics, vol. 14, p. 313–333, 1993.

[DEL 93b] DELORME C., POLJAK S., “Laplacian eigenvalues and the maximum cut problem”, Mathematical Programming, vol. 62, p. 557–574, 1993.

[DES 90] DE SIMONE C., “Lifting facets of the cut polytope”, Operations Research Letters, vol. 9, p. 341–144, 1990.

[DES 94a] DE SIMONE C., RINALDI G., “A cutting plane algorithm for the max-cut problem”, Optimization Methods and Software, vol. 3, p. 195–214, 1994.

[DES 94b] DE SIMONE C. M. D., LAURENT M., “Collapsing and lifting for the cut cone”, Discrete Mathematics, vol. 127, p. 105–130, 1994.

[DES 95] DE SIMONE C., DIEHL M., JÜNGER M., MUTZEL P., REINELT G., RINALDI G., “Exact ground states in spin glasses: New experimental results with a branch-and-cut algorithm”, Journal of Statistical Physics, vol. 80, p. 487–496, 1995.

[DES 96] DE SIMONE C., DIEHL M., JÜNGER M., MUTZEL P., REINELT G., RINALDI G., “Exact ground states of 2D ±J Ising spin glasses”, Journal of Statistical Physics, vol. 84, p. 1363–1371, 1996.

[DES 90] DE SIMONE C., “The cut polytope and the boolean quadric polytope”, Discrete Mathematics, vol. 79, p. 71–75, 1989/90.

[DEZ 92a] DEZA M., GRÖTSCHEL M., LAURENT M., “Clique-web facets for multicut poly-topes”, Mathematics of Operations Research, vol. 17, p. 981–1000, 1992.

[DEZ 92b] DEZA M., LAURENT M., “Extension operations for cuts”, Discrete Mathematics, vol. 106, p. 163–179, 1992.

[DEZ 92c] DEZA M., LAURENT M., “Facets for the cut cone I”, Mathematical Programming, vol. 56, p. 121–160, 1992.

[DEZ 92d] DEZA M., LAURENT M., “Facets for the cut cone II: clique-web facets”, Mathematical Programming, vol. 56, p. 161–188, 1992.

[DEZ 93a] DEZA M., FUKUDA K., LAURENT M., “The inequicut cone”, Discrete Mathematics, vol. 119, p. 21–48, 1993.

[DEZ 93b] DEZA M., LAURENT M., “The even and odd cut polytopes”, Discrete Mathematics, vol. 119, p. 49–66, 1993.

[DEZ 94] DEZA M., LAURENT M., “Applications of cut polyhedra”, J. Comp. Appl. Math., vol. 55, p. 191–247, 1994.

[DEZ 97] DEZA M., LAURENT M., Geometry of Cuts and Metrics, Springer, Berlin, 1997.

[DOL 99] DOLEZAL O., HOFMEISTER T., LEFMANN H., A comparison of approximation algorithms for the MaxCut-problem, Report num. CI-/99, Dortmund University, Fachbereich Informatik, Dortmund, Germany, 1999.

[DRÉ 03] DRÉO J., PÉTROWSKI A., TAILLARD E., Métaheuristiques pour l’optimisation difficile, Eyrolles, Paris, 2003.

[FEI 01a] FEIGE U., LANGBERG M., “The RPR² rounding technique for semidefinite programs”, Lecture Notes in Computer Science; Vol.2076. Proceedings of the 28th International Colloquium on Automata, Languages and Programming, p. 213–224, 2001.

[FEI 01b] FEIGE U., SCHECHTMAN G., “On the integrality ratio of semidefinite relaxations of MAX CUT”, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, ACM, New York, p. 433–442, 2001.

[FER 96] FERNANDEZ DE LA VEGA W., “MAX-CUT has a randomized approximation scheme in dense graphs”, Random Structures and Algorithms, vol. 8, num. 3, p. 187–198, 1996.

[FER 00] FERNANDEZ DE LA VEGA W., KARPINSKI M., “Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT”, Random Structures and Algorithms, vol. 8, p. 314–332, 2000.

[FER 01] FERNANDEZ DE LA VEGA W., KENYON C., “A Randomized Approximation Scheme for Metric MAX-CUT”, Journal of Computer and System Sciences, vol. 63, p. 531– 534, 2001.

[FES 02] FESTA P., PARDALOS P., RESENDE M., RIBEIRO C., “Randomized heuristics for the MAX-CUT problem”, Optimization Methods and Software, vol. 7, p. 1033–1058, 2002.

[FIS 06] FISCHER I., GRUBER G., RENDL F., SOTIROV R., “Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition”, Mathematical Programming, vol. 105, p. 451–469, 2006.

[FON 92] FONLUPT J., MAHJOUB A. R., UHRY J. P., “Compositions in the bipartite sub-graph polytope”, Discrete Mathematics, vol. 105, p. 73–91, 1992.

[FOR 56] FORD L., FULKERSON D., “Maximal Flow through a network”, Canadian Journal of Mathematics, vol. 8, p. 399–404, 1956.

[FOU 05] FOUILHOUX P., Graphes k-partis et conception de circuits VLSI, PhD thesis, Blaise Pascal University, Clermont-Ferrand, 2005.

[FRA 05] FRANGIONI A., LODI A., RINALDI G., “New approaches for optimizing over the semimetric polytope”, Mathematical Programming, vol. 104, p. 375–388, 2005.

[FUL 71] FULKERSON D. R., “Blocking and antiblocking pairs of polyhedra”, Mathematical Programming, vol. 1, p. 168–194, 1971.

[GAL 01] GALLUCCIO A., LOEBL M., VONDRÁK J., “Optimization via enumeration: a new algorithm for the Max Cut Problem”, Mathematical Programming, vol. 90, p. 273–290, 2001.

[GAR 79] GAREY M. R., JOHNSON D. S., Computers and Intractability – A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

[GAR 97] GARG N., VAZIRANI V., YANNAKAKIS M., “Primal-dual approximation algo-rithms for integral flow and multi-cut in trees”, Algorithmica, vol. 18, p. 3–20, 1997.

[GER 85] GERARDS A. M. H., “Testing the odd-bicycle wheel inequalities for the bipartite subgraph polytope”, Mathematics of Operations Research, vol. 10, p. 359–360, 1985.

[GIA 06] GIANDOMENICO M., LETCHFORD A. N., “Exploring the relationship between max-cut and stable set relaxations”, Mathemmatical Programming, vol. 106, p. 159–175, 2006

[GOE 94] GOEMANS M., WILLIAMSON D., “0.878-approximation algorithms for MAX-CUT and MAX 2SAT”, Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, p. 422–431, 1994.

[GOE 95] GOEMANS M., WILLIAMSON D., “Improved Approximation Algorithms for Maximum Cut and Satisfiabiity Problems Using Semidefinite Programming”, Journal of the ACM, vol. 42, p. 1115–1145, 1995.

[GOL 94] GOLDSCHMIDT O., HOCHBAUM D., “A polynomial algorithm for the k-cut problem”, Mathematics of Operations Research, vol. 19, p. 24–37, 1994.

[GOM 61] GOMORY R. E., HU T. C., “Multi-terminal network flows”, SIAM J. on Applied Mathematics, vol. 9, p. 551–570, 1961.

[GRÖ 81a] GRÖTSCHEL M., LOVÁSZ L., SCHRIJVER A., “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, vol. 1, p. 70–89, 1981.

[GRÖ 81b] GRÖTSCHEL M., PULLEYBLANCK W. R., “Weakly bipartite graphs and the max-cut problem”, Operations Research Letters, vol. 1, num. 1, p. 23–27, 1981.

[GRÖ 84] GRÖTSCHEL M., NEMHAUSER G. L., “A polynomial algorithm for the max-cut problem on graphs without long odd cycles”, Mathematical Programming, vol. 29, p. 28– 40, 1984.

[GRÖ 88] GRÖTSCHEL M., LOVÁSZ L., A.SCHRIJVER, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988.

[GRÖ 89a] GRÖTSCHEL M., JÜNGER M., REINELT G., “Via minimization with pin preassignment and layer preference”, Zeitschrift für Angewandte Mathematik und Mechanik, vol. 69, p. 393–399, 1989.

[GRÖ 89b] GRÖTSCHEL M., WAKABAYASHI Y., “A cutting plane algorithm for a clustering problem”, Mathematical Programming, vol. 45B, p. 59–96, 1989.

[GRÖ 90] GRÖTSCHEL M., WAKABAYASHI Y., “Facets of the clique partitioning polytope”, Mathematical Programming, vol. 47, p. 367–387, 1990.

[GUE 01] GUENIN B., “A characterization of weakly bipartite graphs”, Journal of Combinatorial Theory, Series B, vol. 83, p. 112–168, 2001.

[HAD 75] HADLOCK F., “Finding a maximum cut of a planar graph in polynomial time”, SIAM Journal on Computing, vol. 4, p. 221–225, 1975.

[HAL 04] HALPERIN E., LIVNAT D., ZWICK U., “Max cut in cubic graphs”, Journal of Algorithms, vol. 53, p. 169–185, 2004.

[HAM 65] HAMMER P., “Some network flow problems solved with pseudo-Boolean programming”, Operations Research, vol. 32, p. 388–399, 1965.

[HÅS 01] HÅSTAD J., “Some optimal inapproximability results”, Journal of ACM, vol. 48, p. 798–859, 2001.

[HEL 97] HELMBERG C., RENDL F., A Spectral Bundle Method for Semidefinite Programming, Report, SC 97-37, ZIB, Berlin, 1997.

[HEL 01] HELMBERG C., A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations, Report, 01-26, ZIP, Berlin, 2001.

[IRI 71] IRI M., “On an extension of the maximum-flow minimum-cut theorem to multicommodity flows”, Journal of the Operations Research Society of Japan, vol. 13, p. 129– 135, 1971.

[IYE 04] IYENGAR G., PHILIPPS D., STEIN C., Primal-dual approximations of the Max Cut and graph coloring semidefinite program relaxations, Report, CORC TR-2004-06, Department of IEOR, Columbia University, New York, 2004.

[JÜN 98] JÜNGER M., RINALDI G., “Relaxation of the Max-Cut Problem and Computation of Spin Glass Ground States”, Operations Research Proceedings, P. KISCHKA, H. W. LORENZ, U. DERIGS, W. DOMSCHKE, P. KLEINSCHMIDH and R. MÖRING, Eds., Springer, Berlin, p. 74–83, 1998.

[KAR 72] KARP R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, R. E. MILLER and J. W. THATCHER Eds., Plenum Press, New York, p. 85–103, 1972.

[KAR 96a] KARGER D., STEIN C., “A new approach to the minimum cut problem”, Journal of the ACM, vol. 43, p. 601–640, 1996.

[KAR 96b] KARLOFF H., “How good is the Goemans-Williamson MAX CUT algorithm?”, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, p. 427–434, 1996.

[KLE 96] KLEIN P., LU H., “Efficient approximation algorithms for semidefinite programs arising from MAX-CUT and COLORING”, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, p. 338–347, 1996.

[KLE 98] KLEIN P., LU H., “Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs”, ISAAC: 9th International Symposium on Algorithms and Computation, 1998.

[KRI 01] KRISHNAN K., MITCHELL J., “Linear Programming Approaches to Semidefinite Programming Problems”, Weekly Optimization Seminar, 2001.

[KRI 04a] KRISHNAN K., MITCHELL J., Semidefinite cut-and-price approaches for the max-cut problem, Report num. 2004/3, AdvOL, Hamilton, Ontario, Canada, 2004.

[KRI 04b] KRISHNAN K., TERLAKY T., Interior point and semidefinite approaches in combinatorial optimization, Report num. 2004/2, McMaster University, Advanced Optimization Laboratory, Hamilton, Ontario, Canada, 2004.

[LAS 00] LASSERRE J., Optimality conditions and LMI relaxations for 0-1 programs, Report num. 00099, LAAS, Toulouse, France, 2000.

[LAU 01] LAURENT M., “Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijer lift-and-project procedure”, SIAM Journal on Optimization, vol. 12, p. 345–375, 2001.

[LAU 04] LAURENT M., “Semidefinite relaxations for max-cut”, The Sharpest Cut, p. 257– 290, 2004, The Impact of Manfred Padberg and His Work, M. Grötschel, ed., MPS-SIAM Series in Optimization 4, 2004.

[LEM 99] LEMARECHAL C., OUSTRY F., Semidefinite relaxation and Lagrangian duality with application to combinatorial optimization, Report num. 3710, INRIA, 1999.

[LEW 96] LEWIS A. S., OVERTON M. L., “Eigenvalue Optimization”, Acta Numerica, p. 149–190, Cambridge University Press, Cambridge, 1996.

[LEW 03] LEWIS A., “The mathematics of eigenvalue optimization”, Mathematical programming, vol. 97, p. 155–176, 2003.

[LIE 03a] LIERS F., JÜNGER M., REINELT G., RINALDI G., Computing Exact Ground States of Hard Ising Spin Glass by Branch-and-Cut, Preprint, 2003.

[LIE 03b] LIERS F., PALASSINI M., HARTMANN A. K., JÜNGER M., Ground State of the Bethe-lattice Spin Glass and Running Time of an Exact Optimization Algorithm, Preprint, 2003.

[LOM 85] LOMONOSOV M., “Combinatorial approaches to multiflow problems”, Discrete Applied Mathematics, vol. 11, p. 1–93, 1985.

[LOV 91] LOVÁSZ L., SCHRIJVER A., “Cones of matrices and set functions and 0-1 optimization”, SIAM Journal on Optimization, vol. 1, p. 166–190, 1991.

[MAH 99] MAHAJAN S., RAMESH H., “Derandomizing approximation algorithms based on semidefinite programming”, SIAM Journal on Computing, vol. 28, num. 5, p. 1641–1663, 1999.

[MCC 03] MCCORMICK S. T., RAO M. R., RINALDI G., “Easy and difficult objective functions for max cut”, Mathematical Programming, vol. 94, p. 459–466, 2003.

[NAG 92] NAGAMOCHI H., IBARAKI T., “Computing edge-connectivity in multigraphs and capacitated graphs”, SIAM J. on Discrete Mathematics, vol. 5, p. 54–66, 1992.

[NAG 94] NAGAMOCHI H., ONO T., IBARAKI T., “Implementing an efficient minimum capacity cut algorithm”, Mathematical Programming, vol. 67, p. 325–341, 1994.

[NES 97] NESTEROV Y., Quality of semidefinite relaxation for nonconvex quadratic optimization, CORE Discussion Paper 9179, Louvain-La-Neuve, Belgium, 1997.

[NET 06] NETO J., Développement d’algorithmes de génération de contraintes et extensions, PhD thesis, INT-Evry University, 2006.

[NGU 05] NGUYEN V. H., On the Linear Description of Cut Polyhedron, Preprint, 2005.

[ONA 71] ONAGA K., KAKUSHO O., “On feasibility conditions of multicommodity flows in networks”, Transactions on Circuit Theory, vol. 4, p. 425–429, 1971.

[ORL 72] ORLOVA G. I., DORFMAN Y. G., “Finding the maximum cut in a graph”, Cybernet, vol. 10, p. 502–506, 1972.

[PAD 82] PADBERG M., RAO M. R., “Odd minimum cut-sets and b-matchings”, Mathematics of Operations Research, vol. 7, p. 67–80, 1982.

[PAD 89] PADBERG M., “The boolean quadric polytope: some characteristics, facets and relatives”, Mathematical Programming B, vol. 45, p. 139–172, 1989.

[PAD 90] PADBERG M., RINALDI G., “An efficient algorithm for the minimum capacity cut problem”, Mathematical Programming, vol. 47, p. 19–36, 1990.

[PAD 91] PADBERG M., RINALDI G., “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems”, SIAM Review, vol. 33, p. 60–100, 1991.

[PAL 03] PALASSINI M., LIERS F., JÜNGER M., YOUNG A. P., Low Energy Excitations in Spin Glasses from Exact Ground States, Preprint, 2003.

[PIN 84] PINTER R. Y., “Optimal Layer Assignment for Interconnect”, J. VLSI Comput. Syst, vol. 1, p. 123–137, 1984.

[POL 95a] POLJAK S., RENDL F., “Nonpolyhedral relaxations of graph-bisection problems”, SIAM Journal on Optimization, vol. 5, num. 3, p. 467–487, 1995.

[POL 95b] POLJAK S., RENDL F., “Solving the max-cut problem using eigenvalues”, Discrete Applied Mathematics, vol. 62, p. 249–278, 1995.

[SAH 76] SAHNI S., GONZALEZ T., “P-complete Approximation Algorithms”, Journal of the Association for Computing Machinery, vol. 23, num. 3, p. 555–565, 1976.

[SAR 95] SARAN H., VAZIRANI V., “Finding k-cuts within twice the optimal”, SIAM J. on Computing, vol. 24, p. 101–108, 1995.

[SCH 88] SCHRAMM H., ZOWE J., “A combination of the bundle approach and the trust region concept”, Math. Research, vol. 45, p. 196–209, 1988.

[SCH 03] SCHRIJVER A., Combinatorial Optimization, Polyhedra and Efficiency, Springer, Berlin, 2003.

[SEY 80] SEYMOUR P., “Four-terminus flows”, Networks, vol. 10, p. 79–86, 1980.

[SEY 81] SEYMOUR P., “Matroids and multicommodity flows”, European Journal of Combinatorics, vol. 2, p. 257–290, 1981.

[SHM 97] SHMOYS D. B., “Cut problems and their application to divide-and-conquer”, Approximation Algorithms for NP-hard Problems, PWS Publishing company, Boston, p. 192– 235, 1997.

[TAM 91] TAMIR A., “On the core of network synthesis games”, Mathematical Programming, vol. 50, p. 123–135, 1991.

[TOD 01] TODD M., “Semidefinite optimization”, Acta Numerica, vol. 10, p. 515–560, 2001.

[VAN 96] VANDENBERGHE L., BOYD S., “Semidefinite Programming”, SIAM Review, vol. 38, num. 1, p. 49–95, 1996.

[VAZ 01] VAZIRANI V., Approximation Algorithms, Springer, Berlin, 2001.

[YAN 78] YANNAKAKIS M., “Node-and-edge deletion NP-complete problems”, Proceedings of the 10th Annual ACM Symposium on the Theory of Computing, p. 253–264, 1978.

[ZWI 99] ZWICK U., “Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems”, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, p. 679–687, 1999.

1 Chapter written by Walid BEN-AMEUR, Ali Ridha MAHJOUB and José NETO.

Chapter 6

The Maximum Cut Problem ¹

6.1. Introduction