Next: MINIMUM MULTIWAY CUT Up: Cuts and Connectivity Previous: MINIMUM K-CUT Index

### MINIMUM VERTEX K-CUT

- INSTANCE: Graph , a set of special vertices, and a weight function , and an integer k.

- SOLUTION: A vertex k-cut, i.e., a subset of vertices such that their deletion from G disconnects each si from ti for .

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

- Good News: Approximable within [176].