- INSTANCE:
Directed graph
.
- SOLUTION:
A partition of
*V*into disjoint sets and . - MEASURE:
The cardinality of the cut, i.e., the number of arcs with start point
in
and endpoint in .

*Good News:*Approximable within 1.165 [154].*Bad News:*APX-complete [393].*Comment:*Not approximable within 1.083 [242]. Admits a PTAS if [39]. 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].