Fast Hypergraph Partition

We present a new O(n²) heuristic for hypergraph min-cut bipartitioning, an important problem in circuit placement. Fastest previous methods for this problem are O(n² log n). Our approach is based on the intersection graph G dual to the input hypergraph. Paths in G are used to construct partial bipartitions which can be completed optimally. The method is provably good and, in particular, obtains optimum results for "difficult" inputs, i.e., hypergraphs with smaller than expected minimum cutsize. Computational results for a wide range of inputs are also discussed.