Next: MINIMUM QUOTIENT CUT
Up: Cuts and Connectivity
Previous: MINIMUM B-BALANCED CUT
  Index
- 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].
Viggo Kann
1999-04-22