Maximum cuts and large bipartite subgraphs.

*(English)*Zbl 0834.05001
Cook, William (ed.) et al., Combinatorial optimization. Papers from the DIMACS special year. Papers from workshops held at DIMACS at Rutgers University, New Brunswick, NJ, USA, Sept. 1992-Aug. 1993. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 20, 181-244 (1995).

A partition \(V= (S, V\backslash S)\) of the vertex set \(V\) of the graph \(G= (V, E)\) determines the cut \(\delta(S)= \{(i, j)\in E\mid i\in S\) and \(j\in V\backslash S\}\). Given a weight function \(c: E\to \mathbb{R}\), the cut weight is
\[
c(\delta(S))= \sum_{{\begin{smallmatrix} i\in S\\ j\in V\backslash S \end{smallmatrix}}} c_{ij}
\]
and the MAX-CUT problem (MCP) asks for the determination of \(\text{mc}(G, C)= \max_{S\subset V} c(\delta(S))\). The SIMPLE MAX-CUT problem (SMCP) arises when all edge-weights are 1 and asks for the maximum size \(\text{mc}(G)\) of a bipartite subgraph of \(G\). This paper is an extensive survey of the wide range of results available concerning these problems.

The first section discusses several bounds for these parameters and the complexity of these problems. The Edward’s bound for connected graphs \(\text{mc}(G)\geq {1\over 2} m+ {1\over 4} (n- 1)\), computable in \(O(m)\) steps, is shown to be extendable to a similar bound for \(\text{mc}(G)\). The Erdös bound for \(k\)-chromatic graphs and bounds for triangle-free graphs and random graphs are presented. A new reduction to prove MCP is NP-complete as also the SMCP is given. It is also shown that the MCP itself is polynomially solvable on planar graphs.

The second section deals with the polyhedral theory of the MCP. The cut polytope \(P^{\text{cut}}(G)\) is defined as the convex hull of the characteristic vectors of the cut subsets \(S\). It is shown to be full dimensional, and its facets and its valid inequalities determining them are discussed. These include the triangle inequalities, clique inequalities, hypermetric inequalities, gap inequalities and the circulant inequalities. The metric polytope \(P_n^{\text{met}}\) of \(K_n\) is defined by the triangle inequalities and their switchings. The metric polytope \(P^{\text{met}}(G)\) for any graph \(G\) is defined as a natural extension and its relation to \(P^{\text{cut}}(G)\) is discussed. The Chvátal rank of \(P_n^{\text{met}}\) is discussed as also the shape of \(P_n^{\text{cut}}\) through the notions of width and diameter. The polytope \(P^{\text{bip}}(G)\) corresponding to SMCP is also discussed.

The eigenvalue bound \[ \phi(G)= {n\over 4}\inf\Biggl\{\lambda_{\max}(L(G, c)+ \text{diag}(u))\mid u\in \mathbb{R}^n\text{ and }\sum^n_{i= 1} u_i= 0\Biggr\} \] is introduced in section 3. Here \(L(G, c)\), the Laplacian is defined by \(L= (\ell_{ij})\), where \(\ell_{ij}= - c_{ij}\) if \(i\neq j\), and \(\ell_{ij}= \sum^n_{k= 1} c_{ij}\) if \(i= j\). An equivalent of this, called edge-relaxation, and the effect of several combinatorial operations on \(G\), like edge-deletion, amalgamation, etc. on \(\phi(G)\) are also discussed.

In the first part of section 4, sharper bounds for \(\text{mc}(G)\) for special classes of graphs are presented. These include triangle-free graphs and graphs with maximum degree 3. In the latter part the polynomial complexity of SMCP for several recursively defined graphs like cographs, bounded tree width graphs and \(k\)-NLC graphs is discussed. Also considered are geometric graphs, Kneser graphs, circulant graphs and line graphs.

Section 5 introduces the concept of local optimum, polynomial time local search (PLS), PLS-completion and P-completion. Cubic graphs are specially discussed. Several applications like Ising models for spin glasses, VLSI design, signed graphs, \((+ 1, -1)\)-quadratic programming, digital-analog converters, cryptograms, etc. are briefly discussed in section 6. In section 7 is presented the computational experience of several people with the algorithms, as also a discussion of relative errors of the polyhedral relaxation and the eigenvalue bound and the problem of approximation of the MCP.

For the entire collection see [Zbl 0819.00048].

The first section discusses several bounds for these parameters and the complexity of these problems. The Edward’s bound for connected graphs \(\text{mc}(G)\geq {1\over 2} m+ {1\over 4} (n- 1)\), computable in \(O(m)\) steps, is shown to be extendable to a similar bound for \(\text{mc}(G)\). The Erdös bound for \(k\)-chromatic graphs and bounds for triangle-free graphs and random graphs are presented. A new reduction to prove MCP is NP-complete as also the SMCP is given. It is also shown that the MCP itself is polynomially solvable on planar graphs.

The second section deals with the polyhedral theory of the MCP. The cut polytope \(P^{\text{cut}}(G)\) is defined as the convex hull of the characteristic vectors of the cut subsets \(S\). It is shown to be full dimensional, and its facets and its valid inequalities determining them are discussed. These include the triangle inequalities, clique inequalities, hypermetric inequalities, gap inequalities and the circulant inequalities. The metric polytope \(P_n^{\text{met}}\) of \(K_n\) is defined by the triangle inequalities and their switchings. The metric polytope \(P^{\text{met}}(G)\) for any graph \(G\) is defined as a natural extension and its relation to \(P^{\text{cut}}(G)\) is discussed. The Chvátal rank of \(P_n^{\text{met}}\) is discussed as also the shape of \(P_n^{\text{cut}}\) through the notions of width and diameter. The polytope \(P^{\text{bip}}(G)\) corresponding to SMCP is also discussed.

The eigenvalue bound \[ \phi(G)= {n\over 4}\inf\Biggl\{\lambda_{\max}(L(G, c)+ \text{diag}(u))\mid u\in \mathbb{R}^n\text{ and }\sum^n_{i= 1} u_i= 0\Biggr\} \] is introduced in section 3. Here \(L(G, c)\), the Laplacian is defined by \(L= (\ell_{ij})\), where \(\ell_{ij}= - c_{ij}\) if \(i\neq j\), and \(\ell_{ij}= \sum^n_{k= 1} c_{ij}\) if \(i= j\). An equivalent of this, called edge-relaxation, and the effect of several combinatorial operations on \(G\), like edge-deletion, amalgamation, etc. on \(\phi(G)\) are also discussed.

In the first part of section 4, sharper bounds for \(\text{mc}(G)\) for special classes of graphs are presented. These include triangle-free graphs and graphs with maximum degree 3. In the latter part the polynomial complexity of SMCP for several recursively defined graphs like cographs, bounded tree width graphs and \(k\)-NLC graphs is discussed. Also considered are geometric graphs, Kneser graphs, circulant graphs and line graphs.

Section 5 introduces the concept of local optimum, polynomial time local search (PLS), PLS-completion and P-completion. Cubic graphs are specially discussed. Several applications like Ising models for spin glasses, VLSI design, signed graphs, \((+ 1, -1)\)-quadratic programming, digital-analog converters, cryptograms, etc. are briefly discussed in section 6. In section 7 is presented the computational experience of several people with the algorithms, as also a discussion of relative errors of the polyhedral relaxation and the eigenvalue bound and the problem of approximation of the MCP.

For the entire collection see [Zbl 0819.00048].

Reviewer: K.R.Parthasarathy (Narayanapuram)

##### MSC:

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

05C85 | Graph algorithms (graph-theoretic aspects) |

52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |

05C35 | Extremal problems in graph theory |

90C27 | Combinatorial optimization |

05C40 | Connectivity |

05C90 | Applications of graph theory |

68R10 | Graph theory (including graph drawing) in computer science |