MINIMUM B-VERTEX SEPARATOR

• INSTANCE: Graph $G=\left(V,E\right)$ and a rational b, $0<b\le 1/2$.

• SOLUTION: A partition of V into disjoint sets A, B, and C, such that $\max\{\vert A\vert ,\vert B\vert\}\le b\cdot \vert V\vert$ and no edge has one endpoint in A and one in B.

• MEASURE: The size of the separator, i.e., $\vert C\vert$.

  
  

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

• Comment: For planar graphs a separator of size $O(\sqrt{\vert V\vert})$ can be found in polynomial time [361]. An $f(\vert V\vert)$-approximation algorithm is also a $f(16\vert V\vert^5)$ algorithm for MINIMUM B-BALANCED CUT [93].