On cutting a few vertices from a graph ?
We consider the problem of finding in an undirected graph a minimum cut that separates exactly a given number k of vertices. For general k (i.e. k is part of the input and may depend on n) this problem is NP-hard. We present for this problem a randomized approximation algorithm, which is useful when k is relatively small. In particular, for we obtain a polynomial time approximation scheme, and for we obtain an approximation ratio .
approximation algorithms graph partitioning random edge contraction dynamic programming