- INSTANCE:
Graph
.
- SOLUTION:
A partition of
*V*into disjoint sets and . - MEASURE:
The cardinality of the cut, i.e., the number of edges with one end point
in
and one endpoint in .

*Good News:*Approximable within 1.1383 [198].*Bad News:*APX-complete [393].*Comment:*Not approximable within 1.0624 [242]. Admits a PTAS if [39]. Variation in which the degree of*G*is bounded by a constant*B*for is still APX-complete [393] 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 [128] and admits a PTAS for dense instances [162] and for metric weights [164]. 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 [198].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.431 [472]. Admits a PTAS for some classes of weighted dense instances of MAXIMUM BISECTION [162].

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 [39].

*Garey and Johnson:*ND16