ComPart integrates community detection into post-coarsening phases of hypergraph partitioning and generalizes locally-dense decomposition to hypergraphs, yielding higher-quality partitions on benchmarks than prior methods.
Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning. It is based on minimum S-T hyperedge cuts and maximum flows. It computes a sequence of bipartitions that optimize cut size and balance in the Pareto sense, being able to trade one for the other. HyperFlowCutter builds on the FlowCutter algorithm for partitioning graphs. We propose additional features, such as handling disconnected hypergraphs, novel methods for obtaining starting S,T pairs as well as an approach to refine a given partition with HyperFlowCutter. Our main contribution is ReBaHFC, a new algorithm which obtains an initial partition with the fast multilevel hypergraph partitioner PaToH and then improves it using HyperFlowCutter as a refinement algorithm. ReBaHFC is able to significantly improve the solution quality of PaToH at little additional running time. The solution quality is only marginally worse than that of the best-performing hypergraph partitioners KaHyPar and hMETIS, while being one order of magnitude faster. Thus ReBaHFC offers a new time-quality trade-off in the current spectrum of hypergraph partitioners. For the special case of perfectly balanced bipartitioning, only the much slower plain HyperFlowCutter yields slightly better solutions than ReBaHFC, while only PaToH is faster than ReBaHFC.
fields
cs.AR 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
IMPart integrates memetic recombination and mutation directly into the multi-level uncoarsening phase to improve quality for large-k hypergraph partitioning.
citing papers explorer
-
ComPart: Community-Guided Post-Coarsening for High-Quality Hypergraph Partitioning
ComPart integrates community detection into post-coarsening phases of hypergraph partitioning and generalizes locally-dense decomposition to hypergraphs, yielding higher-quality partitions on benchmarks than prior methods.
-
IMPart: Integration of Memetic Operations into Multi-Level Framework for Large-k-Way Hypergraph Partitioning
IMPart integrates memetic recombination and mutation directly into the multi-level uncoarsening phase to improve quality for large-k hypergraph partitioning.