Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

Abstract

Multilevel partitioners shrink circuit hypergraphs through vertex contractions, yet a contraction that satisfies block capacity can still eliminate every optimal balanced bipartition. We develop certified safe coarsening (CSC) to identify contractions that preserve an optimum without computing that optimum. CSC certifies a repair for any feasible partition that splits a candidate group: the repair must respect the fixed block capacities and must not increase the cut-net objective. Its bounds exclude hyperedges that capacity constraints force to be cut. A pair certificate checks individual merges, while a directed minimum-cut test certifies groups whose savings emerge only when vertices move together. We prove that certified disjoint batches and successive rounds with recertification retain at least one globally optimal feasible partition for hypergraphs with positive integer vertex and net weights. Experiments on exactly solvable instances confirm optimum preservation for every tested configuration; integration with KaHyPar lowers the sum of per-instance best cuts on circuit benchmarks, with additional runtime.