Next: MINIMUM B-VERTEX SEPARATOR Up: Cuts and Connectivity Previous: MINIMUM RATIO-CUT Index

### MINIMUM B-BALANCED CUT

- INSTANCE: Graph , a vertex-weight function , an edge-cost function , and a rational b, .

- SOLUTION: A cut C, i.e., a subset , such that

  where w(V') denotes the sum of the weights of the vertices in V'.

- MEASURE: The weight of the cut, i.e.,

  where .

- Bad News: Not approximable within for any [85].

- Comment: Also called Minimum b-Edge Separator. There is a polynomial algorithm that finds a b-balanced cut within an factor of the optimal -balanced cut for [416]. Approximable within 2 for planar graphs for if the vertex weights are polynomially bounded [175]. Not approximable within for graphs of maximum degree 3 [85]. The unweighted problem admits a PTAS if every vertex has degree for [37]. MINIMUM K-MULTIWAY SEPARATOR, the variation in which the removal of the cut edges partitions the graph into at most k parts, where the sum of the vertex weights in each part is at most , is approximable within [136].

Next: MINIMUM B-VERTEX SEPARATOR Up: Cuts and Connectivity Previous: MINIMUM RATIO-CUT Index