ND13 MAXIMUM DIRECTED CUT

Next: ND14 MAXIMUM K-CUT Up: Cuts and Connectivity Previous: ND12 MINIMUM CROSSING

I NSTANCE : Directed graph .
S OLUTION : A partition of V into disjoint sets and .
M EASURE : The cardinality of the cut, i.e., the number of arcs with one end point in and one endpoint in .
Good News: Approximable within 1.165 [ 104 ].
Bad News: A PX -complete [ 284 ].
Comment: Not approximable within 1.083 [ 164 ]. Admits a PTAS if [ 24 ]. The weighted problem, where every arc is assigned a nonnegative weight and the objective is to maximize the total weight of the arcs in the cut is also approximable within 1.165 [ 104 ].

Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997