- 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 from for . - MEASURE:
The sum of the weight of the vertices in the cut, i.e.,
.

*Good News:*Approximable within [188].