<p>Wagner and Wagner, in "<a href="http://dx.doi.org/10.1007/3-540-57182-5_65" rel="noreferrer">Between min cut and graph bisection</a>" (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.</p>

<blockquote>
  <p>Has anyone setteled the complexity of $\log n $ balanced graph partition?</p>
</blockquote>

CC BY-SA 3.0
2011-09-01T21:12:22.423Z
I misunderstood the problem and wrote an incorrect comment. Nevertheless, a paper of Papadimitriou and Yannakakis may be relevant. http://www.sciencedirect.com/science/article/pii/S0022000096900586
Chandra Chekuri
CC BY-SA 3.0
2011-09-01T21:19:46.530Z
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
CC BY-SA 3.0
2011-09-01T23:07:11.947Z
Are you aware of any reference that proves hardness for the class of problems solvable in quasi-polynomial time?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-01T23:37:13.170Z
@Mohammad, no, if there were such results then SAT would be solvable in quasipolynoial time.
Kaveh
CC BY-SA 3.0
2011-09-02T05:04:04.413Z
@Kaveh, Do you have a reference?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-09-09T17:04:23.327Z
@ChandraChekuri Please convert you comment into an answer.
Mohammad Al-Turkistany
<cc.complexity-theory><open-problem>
Complexity of balanced graph partition problem
Mohammad Al-Turkistany
# Complexity of balanced graph partition problem

(Asked by: username_0 on 2011-09-01)

Wagner and Wagner, in "[Between min cut and graph bisection](http://dx.doi.org/10.1007/3-540-57182-5_65)" (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?

**Tags:** cc.complexity-theory, open-problem

> **Comments:**
> **username_1**: I misunderstood the problem and wrote an incorrect comment. Nevertheless, a paper of Papadimitriou and Yannakakis may be relevant. http://www.sciencedirect.com/science/article/pii/S0022000096900586  
> **username_1**: 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.  
> **username_0**: Are you aware of any reference that proves hardness for the class of problems solvable in quasi-polynomial time?  
> **username_2**: @Mohammad, no, if there were such results then SAT would be solvable in quasipolynoial time.  
> **username_0**: @username_2, Do you have a reference?  
> **username_0**: @ChandraChekuri Please convert you comment into an answer.  

---

## 0 answers

