Multilevel Partitioning (hMETIS)

The idea

Flat refinement sees only one move at a time; good cuts on big graphs require moving whole regions. The multilevel paradigm gets there in three phases. Coarsen: repeatedly merge strongly connected vertex clusters (heavy-edge matching and its hypergraph analogues), producing a hierarchy of ever-smaller graphs that preserve the original's cut structure. Initial partition: split the smallest graph, where even expensive methods are cheap. Uncoarsen and refine: project the partition back level by level, running Fiduccia-Mattheyses refinement at each, so single-vertex moves at a coarse level correspond to bulk region moves in the original.

The result is better cuts and near-linear total runtime, because most refinement happens on small graphs and each level starts from an already-good projection. hMETIS packaged the idea for hypergraphs with careful matching schemes and V-cycle iteration and set benchmark records that stood for years.

Where you meet it today

Everywhere netlists get cut: min-cut placement (Capo's bisection engine), physical hierarchy generation and clustering before macro placement, multi-die and multi-FPGA (Field-Programmable Gate Array) system partitioning, parallel simulation load balancing. The multilevel V-cycle also escaped partitioning entirely: multilevel placement (the mPL page) and multigrid-flavored solvers in analytical placement are the same instinct applied to different objectives.