Most balanced minimum cuts

We consider the problem of finding most balanced cuts among minimum stst-edge cuts and minimum stst-vertex cuts, for given vertices ss and tt, according to different balance criteria. For edge cuts [S,S¯] we seek to maximize min{|S|,|S¯|}. For vertex cuts CC of GG we consider the objectives of (i) maximizing min{|S|,|T|}min{|S|,|T|}, where {S,T}{S,T} is a partition of V(G)∖CV(G)∖C with s∈Ss∈S, t∈Tt∈T and [S,T]=0̸[S,T]=0̸, (ii) minimizing the order of the largest component of G−CG−C, and (iii) maximizing the order of the smallest component of G−CG−C.All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP.To prove these results we show that we can partition the vertices of GG, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum stst-cuts of GG. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances.