When clusters meet partitions: new density-based methods for circuit decomposition

Top-down partitioning has focused on minimum cut or ratio cut objectives, while bottom-up clustering has focused on density-based objectives. In seeking a more unified perspective, we propose a new sum of densities measure for multi-way circuit decomposition, where the density of a subhypergraph is the ratio of the number of edges to the number of nodes in the subhypergraph. Finding a k-way partition that maximizes the sum of k subhypergraph densities is NP-hard, but an efficient flow-based method can find the optimal (maximum-density) subhypergraph in a given hypergraph. Based on this method, we develop a heuristic which in practice has less than 10% error from an optimal sum of densities decomposition. Other results suggest that density-based heuristics can capture cut-based objectives, whereas the converse would seem difficult