Trees for vertex cuts, hypergraph cuts and minimum hypergraph bisection

In the Minimum Hypergraph Bisection problem, the vertex set of a hypergraph has to be partitioned into two parts of equal size so that the number of hyperedges intersecting both parts is minimized. This problem is a natural generalization of the well-studied Minimum Bisection problem in graphs. In this paper we present a sharp distinction between Minimum Bisection in hypergraphs and graphs. Whereas it is well-known that all bi-criteria approximation algorithms for Minimum Bisection in graphs can be extended to hypergraphs with the exact same guarantees, in this paper we prove that this is not the case when considering true (i.e., non bi-criteria) approximation algorithms. Specifically, we show that Minimum Bisection in Hypergraphs admits an Õ (n) approximation algorithm (and highlight several special cases where a better approximation ratio is possible). Additionally, we show that the problem is at least as hard as the Densest k-Subgraph problem. Assuming the Dense vs. Random Conjecture [4], no approximation ratio better than O (n¹/4−^ε ) is possible. In particular, Minimum Hypergraph Bisection is much harder to approximate than Minimum Bisection in graphs, for which a logarithmic approximation algorithms exist [17]. We also consider the problem of constructing trees that are cut sparsifiers for hypergraph and vertex cuts. While similar trees lie at the heart of powerful algorithms for Minimum Bisection in graphs, we prove that this is not the case for hypergraphs. We give upper and lower bounds to the quality of such trees. Our bounds show that this tree cut sparsifying approach cannot improve the general approximation ratio of Minimum Hypergraph Bisection and Minimum Vertex Bisection.