Next: MAXIMUM K-CUT Up: Cuts and Connectivity Previous: MINIMUM CROSSING NUMBER Index

### MAXIMUM DIRECTED CUT

- INSTANCE: Directed graph .

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

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

- Good News: Approximable within 1.165 [143].

- Bad News: APX-complete [371].

- Comment: Not approximable within 1.083 [226]. Admits a PTAS if [37]. 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].