Before revision:  In this work, we resolve the problem for general graphs, by showing that for any fixed k \geq 2, the Karger-Stein algorithm outputs any fixed k-cut of weight \alpha \lambda_k with probability at least O _k(n^{-\alpha k}), where \lambda_k denotes the minimum k-cut size.
After revision:  In this work, we resolve the problem for general graphs, by showing that the Contraction Algorithm of Karger outputs any fixed k-cut of weight \alpha \lambda_k with probability at least O _k(n^{-\alpha k}), where \lambda_k denotes the minimum k-cut size.