# Complexity of balanced graph partition problem

Wagner and Wagner, in "Between min cut and graph bisection" (MFCS 1993), studied a variant of minimum bisection problem where we seek a cut with minimum size such that each partition has at least $\log n$ verticies. They stated that the complexity of this variant is an open problem since they did not find an efficient algorithm nor NP-hardness proof.

Has anyone setteled the complexity of $\log n$ balanced graph partition?

• I misunderstood the problem and wrote an incorrect comment. Nevertheless, a paper of Papadimitriou and Yannakakis may be relevant. sciencedirect.com/science/article/pii/S0022000096900586 – Chandra Chekuri Sep 1 '11 at 21:12
• The problem can be solved in $n^{O(\log n)}$ time by guessing $\log n$ vertices on each side of an optimum partition so it is unlikely to be NP-Hard. The above mentioned paper of Papadimitriou and Yannakakis addresses these types of problems though it is not clear whether the specific problem here is complete for any of those classes. – Chandra Chekuri Sep 1 '11 at 21:19
• Are you aware of any reference that proves hardness for the class of problems solvable in quasi-polynomial time? – Mohammad Al-Turkistany Sep 1 '11 at 23:07
• @Mohammad, no, if there were such results then SAT would be solvable in quasipolynoial time. – Kaveh Sep 1 '11 at 23:37
• @Kaveh, Do you have a reference? – Mohammad Al-Turkistany Sep 2 '11 at 5:04