Next: MINIMUM CROSSING NUMBER Up: Cuts and Connectivity Previous: Cuts and Connectivity Index

### MAXIMUM CUT

- INSTANCE: Graph .

- SOLUTION: A partition of V into disjoint sets V1 and V2.

- MEASURE: The cardinality of the cut, i.e., the number of edges with one end point in V1 and one endpoint in V2.

- Good News: Approximable within 1.1383 [186].

- Bad News: APX-complete [371].

- Comment: Not approximable within 1.0624 [226]. Admits a PTAS if [37]. Variation in which the degree of G is bounded by a constant B for is still APX-complete [371] and [9]. Variation in which each edge has a nonnegative weight and the objective is to maximize the total weight of the cut is as hard to approximate as the original problem [120] and admits a PTAS for dense instances [150] and for metric weights [151]. Variation in which some pairs of vertices are restricted to be on the same side (or on different sides) is still approximable within 1.138 [186].

  MAXIMUM BISECTION, the weighted problem with the additional constraint that the partition must cut the graph into halves of the same size, is approximable within 1.54 [164] and [347].

  MINIMUM BISECTION, the problem where the partition must cut the graph into halves of the same size and the number of edges between them is to be minimized, admits a PTAS if the degree of each vertex is [37].

- Garey and Johnson: ND16

Next: MINIMUM CROSSING NUMBER Up: Cuts and Connectivity Previous: Cuts and Connectivity Index