MINIMUM B-BALANCED CUT

• INSTANCE: Graph $G=\left(V,E\right)$, a vertex-weight function $w:V\rightarrow N$, an edge-cost function $c : E \rightarrow N$, and a rational b, $0<b\le 1/2$.

• SOLUTION: A cut C, i.e., a subset $C \subseteq V$, such that
  
  $$\min\{w(C),w(V-C)\}\ge b\cdot w(V),$$
  
  
  where w(V') denotes the sum of the weights of the vertices in V'.

• MEASURE: The weight of the cut, i.e.,
  
  $$\displaystyle\sum_{e\in\delta(C)} c(e)$$
  
  
  where $\delta(C)=\{e=\{v_1,v_2\}: e\in E, v_1\in C, v_2\in V-C\}$.

  
  

• Bad News: Not approximable within $1+\vert V\vert^{2-\varepsilon }/\mbox{\sl opt}$ for any $\varepsilon >0$ [93].

• Comment: Also called Minimum b-Edge Separator. There is a polynomial algorithm that finds a b-balanced cut within an $O(\log \vert V\vert)$ factor of the optimal $b+\varepsilon$-balanced cut for $b\le 1/3$ [439]. Approximable within 2 for planar graphs for $b\le 1/3$ if the vertex weights are polynomially bounded [187]. Not approximable within $1+\vert V\vert^{1/2-\varepsilon }/\mbox{\sl opt}$ for graphs of maximum degree 3 [93]. The unweighted problem admits a PTAS if every vertex has degree $\Theta(\vert V\vert)$ for $b\le 1/3$ [39]. MINIMUM K-MULTIWAY SEPARATOR, the variation in which the removal of the cut edges partitions the graph into at most k parts, where the sum of the vertex weights in each part is at most $2\sum_{v\in V} w(v)/k$, is approximable within $(2+o(1))\ln \vert V\vert$ [147].