Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2003 Copyright 2003 University of Bonn, Department of Computer Science, Abt. V
85254

29.07.2003

Approximability of Hypergraph Minimum Bisection
Piotr Berman and Marek Karpinski
[Download PostScript] [Download PDF]

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 >= 3.

Last Change: 11/05/14 at 10:26:56
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V