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?

  • $\begingroup$ 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 $\endgroup$ – Chandra Chekuri Sep 1 '11 at 21:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Sep 1 '11 at 21:19
  • $\begingroup$ Are you aware of any reference that proves hardness for the class of problems solvable in quasi-polynomial time? $\endgroup$ – Mohammad Al-Turkistany Sep 1 '11 at 23:07
  • $\begingroup$ @Mohammad, no, if there were such results then SAT would be solvable in quasipolynoial time. $\endgroup$ – Kaveh Sep 1 '11 at 23:37
  • $\begingroup$ @Kaveh, Do you have a reference? $\endgroup$ – Mohammad Al-Turkistany Sep 2 '11 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.