Next: MINIMUM VERTEX K-CUT Up: Cuts and Connectivity Previous: MINIMUM NETWORK INHIBITION ON Index

### MINIMUM K-CUT

- INSTANCE: Graph , a weight function , and an integer .

- SOLUTION: A partition of V into k disjoint sets .

- MEASURE: The sum of the weight of the edges between the disjoint sets, i.e.,

- Good News: Approximable within [405].

- Comment: Solvable in polynomial time O(|V|k2) for fixed k [189]. If the sets in the partition are restricted to be of equal size, the problem is approximable within [405]. If the sets in the partition are restricted to be of specified sizes and the weight function satisfies the triangle inequality, the problem is approximable within 3 for any fixed k [201]. The unweighted problem admits a PTAS if every vertex has degree [37].