Next: MINIMUM QUOTIENT CUT Up: Cuts and Connectivity Previous: MINIMUM B-BALANCED CUT Index

### MINIMUM B-VERTEX SEPARATOR

- INSTANCE: Graph and a rational b, .

- SOLUTION: A partition of V into disjoint sets A, B, and C, such that and no edge has one endpoint in A and one in B.

- MEASURE: The size of the separator, i.e., |C|.

- Bad News: Not approximable within for any , even for graphs of maximum degree 3 [85].

- Comment: For planar graphs a separator of size can be found in polynomial time [342]. An f(|V|)-approximation algorithm is also a f(16|V|5) algorithm for MINIMUM B-BALANCED CUT [85].