4 The MQI lemma
There is a polynomial time algorithm that answers this decision problem exactly.
Proofs have appeared in at least the following:

Uriel Feige and Robert Krauthgamer, A polylogarithmic
approximation of the minimum bisection, FOCS2000.
 Chris Harrelson, Kirsten Hildrum, and Satish Rao,
A polynomialtime tree decomposition to minimize congestion, SPAA 2003.
The point of this paper is that the algorithm works very well in practice.