## Abstract

We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter ν ≤1, no component contains more than ν • n/k of the graph vertices. For k = 2 and ν = 1 this problem is equivalent to the well-known Minimum Bisection problem for which an approximation algorithm with a polylogarithmic approximation guarantee has been presented in [FK]. For arbitrary k and ν ≤ 2 a bicriteria approximation ratio of O(log n) was obtained by Even et al. [ENRS1] using the spreading metrics technique. We present a bicriteria approximation algorithm that for any constant ν > 1 runs in polynomial time and guarantees an approximation ratio of O(log^{1.5}n) (for a precise statement of the main result see Theorem 6). For ν = 1 and k ≤ 3 we show that no polynomial time approximation algorithm can guarantee a finite approximation ratio unless P = NP.

Original language | English |
---|---|

Pages (from-to) | 929-939 |

Number of pages | 11 |

Journal | Theory of Computing Systems |

Volume | 39 |

Issue number | 6 |

DOIs | |

State | Published - Nov 2006 |

Externally published | Yes |