TR03-056 Authors: Piotr Berman, Marek Karpinski

Publication: 29th July 2003 09:07

Downloads: 2836

Keywords:

We prove that the problems of minimum bisection on k-uniform

hypergraphs are almost exactly as hard to approximate,

up to the factor k/3, as the problem of minimum bisection

on graphs. On a positive side, our argument gives also the

first approximation algorithms for the problem of minimum

bisection on k-uniform hypergraphs, for every integer k, of

a comparable guarantee as for the minimum bisection on graphs.

Moreover, we prove that the problems of minimum bisection on

very sparse 2-regular k-uniform hypergraphs are precisely

as hard to approximate as the general minimum bisection problem

on arbitrary graphs for every integer k \geq 3.