- INSTANCE:
Graph
and a rational
*b*, . - SOLUTION:
A partition of
*V*into disjoint sets*A, B*, and*C*, such that and no edge has one endpoint in*A*and one in*B*. - MEASURE:
The size of the separator, i.e., .

*Bad News:*Not approximable within for any , even for graphs of maximum degree 3 [93].*Comment:*For planar graphs a separator of size can be found in polynomial time [361]. An -approximation algorithm is also a algorithm for MINIMUM*B*-BALANCED CUT [93].