Safe hypergraph shrinking methods keep best solutions intact

Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

Data Structures and Algorithms

Summary

Finding the best way to split complex circuits into parts is tricky, especially when trying to simplify the problem by grouping parts together. The authors developed a way to safely combine parts without accidentally losing the best possible split. Their method checks if the merging keeps the optimal solution feasible by verifying certain safety conditions. Tests show this approach works well on circuits and helps find better splits overall.

What this means in practice

Authors

Yu Deng, Xinyi Yang, Keren Zhu

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.