pith. sign in

arxiv: 1907.02053 · v1 · pith:55E75MGXnew · submitted 2019-07-03 · 💻 cs.DS

Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm

Lars Gottesb\"uren , Michael Hamann , Dorothea Wagner This is my paper

Pith reviewed 2026-05-25 09:22 UTC · model grok-4.3

classification 💻 cs.DS
keywords hypergraph bipartitioningflow-based refinementminimum cutsPareto optimizationmultilevel partitioningHyperFlowCutterPaToHbalanced partitioning
0
0 comments X

The pith

ReBaHFC refines an initial PaToH partition with flow-based HyperFlowCutter to improve hypergraph bipartition quality at modest extra cost.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces HyperFlowCutter, which generates a sequence of balanced hypergraph bipartitions by computing minimum S-T hyperedge cuts and maximum flows to optimize cut size and balance in the Pareto sense. It then defines ReBaHFC as the combination of a fast initial partition from the multilevel tool PaToH followed by HyperFlowCutter refinement. This combination produces partitions of substantially higher quality than PaToH alone while adding only small running time. The quality sits only slightly below the best existing tools KaHyPar and hMETIS, yet ReBaHFC runs roughly ten times faster, establishing a new operating point on the speed-quality curve for hypergraph bipartitioning tasks.

Core claim

HyperFlowCutter extends the graph FlowCutter algorithm to hypergraphs by supporting disconnected inputs, new S-T pair selection, and direct refinement of a given partition. ReBaHFC obtains an initial bipartition with PaToH and then applies HyperFlowCutter refinement. The result significantly improves solution quality over PaToH at little additional running time. Quality remains only marginally worse than that of KaHyPar and hMETIS while running one order of magnitude faster. For the special case of perfectly balanced bipartitioning, the slower plain HyperFlowCutter produces slightly better solutions than ReBaHFC, and only PaToH is faster than ReBaHFC.

What carries the argument

HyperFlowCutter, a flow-based algorithm that produces Pareto-optimal bipartitions by sequencing minimum S-T hyperedge cuts and maximum flows while handling hypergraph-specific features such as disconnected components and refinement.

If this is right

  • ReBaHFC supplies a new point on the time-quality trade-off curve for hypergraph bipartitioners.
  • For perfectly balanced bipartitioning the slower plain HyperFlowCutter yields slightly better solutions than ReBaHFC.
  • ReBaHFC can refine an arbitrary starting partition and handle disconnected hypergraphs.
  • Only PaToH finishes faster than ReBaHFC while producing noticeably worse partitions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same refinement technique could be paired with other fast multilevel partitioners besides PaToH to create additional hybrids.
  • Applications that must choose a specific cut-balance trade-off could directly inspect the Pareto sequence generated by HyperFlowCutter.
  • The flow-based refinement step may scale to larger hypergraphs if the underlying max-flow implementations are further optimized.

Load-bearing premise

The benchmark hypergraphs and quality metrics are representative of the instances and objectives that arise in the target applications, and the observed quality gains are produced by the HyperFlowCutter refinement step.

What would settle it

Run ReBaHFC, PaToH, KaHyPar and hMETIS on a fresh collection of hypergraphs drawn from an application domain absent from the original test set and measure whether the reported quality-time ordering is preserved.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proposes HyperFlowCutter, a flow-based algorithm for balanced hypergraph bipartitioning that computes a Pareto-optimal sequence of bipartitions trading cut size against balance, extending the graph FlowCutter method with handling for disconnected hypergraphs, new S,T pair selection, and a refinement procedure. The main contribution is ReBaHFC, which initializes a partition using the multilevel tool PaToH and refines it with HyperFlowCutter. The central empirical claim is that ReBaHFC substantially improves solution quality over PaToH at little extra runtime cost, achieves quality only marginally worse than KaHyPar and hMETIS while being an order of magnitude faster, and for the perfectly balanced case is only slightly worse than plain HyperFlowCutter while faster than it.

Significance. If the reported time-quality trade-offs hold on the evaluated instances, the work supplies a practical new point in the spectrum of hypergraph bipartitioning algorithms that may be attractive for applications requiring fast, reasonably high-quality partitions. The algorithmic extensions (disconnected-component handling, S,T initialization, and refinement) constitute a clear technical contribution building on prior flow-based graph partitioning, and the manuscript supplies the experimental protocol, benchmark collection, and timing breakdowns needed to support reproducibility of the performance deltas.

minor comments (2)
  1. [Abstract] Abstract: the quantitative claims ('significantly improve', 'one order of magnitude faster', 'marginally worse') would be more informative if accompanied by a brief reference to the specific tables or average improvement percentages that support them.
  2. [Evaluation] Evaluation section: while the protocol and benchmark collection are supplied, a short explicit statement of the selection criteria for the hypergraph instances (e.g., size, density, application origin) would help readers assess representativeness without altering the central claims.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on HyperFlowCutter and ReBaHFC, including recognition of the algorithmic extensions and the practical time-quality trade-off demonstrated in the experiments. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No circularity; empirical claims rest on external benchmarks

full rationale

The paper is an empirical evaluation of ReBaHFC (PaToH initialization followed by HyperFlowCutter refinement) against independent external tools (PaToH, KaHyPar, hMETIS). No equations, predictions, or first-principles derivations appear in the provided text; the central claims are measured runtime-quality deltas on benchmark instances. Self-reference to the prior FlowCutter graph algorithm is not load-bearing for the reported improvements, which are validated by direct comparison to third-party partitioners rather than by internal redefinition or fitted-parameter renaming. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on the correctness of standard max-flow algorithms and on the behavior of the preexisting PaToH multilevel partitioner; no new free parameters, ad-hoc axioms, or postulated entities are introduced in the abstract.

axioms (1)
  • standard math Maximum-flow minimum-cut duality holds for the hypergraph cut model employed by HyperFlowCutter.
    Invoked as the foundation for locating balanced cuts via flow computations.

pith-pipeline@v0.9.0 · 5781 in / 1324 out tokens · 28284 ms · 2026-05-25T09:22:25.910117+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    3 Charles J

    doi: 10.1137/1.9781611974768.3. 3 Charles J. Alpert. The ISPD98 Circuit Benchmark Suite. InProceedings of the 1998 Interna- tional Symposium on Physical Design, pages 80–85, 1998.doi:10.1145/274535.274546. 4 Charles J. Alpert, Jen-Hsin Huang, and Andrew B. Kahng. Multilevel Circuit Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Cir...

    work page doi:10.1137/1.9781611974768.3 1998

  2. [2]

    6 Robin Andre, Sebastian Schlag, and Christian Schulz

    doi:10.1016/0167-9260(95)00008-4. 6 Robin Andre, Sebastian Schlag, and Christian Schulz. Memetic Multilevel Hypergraph Partitioning. InProceedings of the Genetic and Evolutionary Computation Conference, pages 347–354. ACM Press, July 2018.doi:10.1145/3205455.3205475. 7 David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner.Graph Partition-...

    work page doi:10.1016/0167-9260(95)00008-4 2018

  3. [3]

    8 Anton Belov, Daniel Diepold, Marijn JH Heule, and Matti Järvisalo

    American Mathematical Society, 2013.doi:10.1090/conm/588. 8 Anton Belov, Daniel Diepold, Marijn JH Heule, and Matti Järvisalo. The SAT Competition 2014,

    work page doi:10.1090/conm/588 2013

  4. [4]

    9 Una Benlic and Jin-Kao Hao

    URL: http://www.satcompetition.org/2014/. 9 Una Benlic and Jin-Kao Hao. An Effective Multilevel Memetic Algorithm for Balanced Graph Partitioning. InIEEE International Conference on Tools with Artificial Intelligence, pages 121–128. IEEE Computer Society, 2010.doi:10.1109/ICTAI.2010.25. 10 Una Benlic and Jin-Kao Hao. A Multilevel Memetic Approach for Improv...

    work page doi:10.1109/ictai.2010.25 2014

  5. [5]

    11 Una Benlic and Jin-Kao Hao

    doi:10.1109/TEVC.2011.2136346. 11 Una Benlic and Jin-Kao Hao. An Effective Multilevel Tabu Search Approach for Balanced Graph Partitioning. Computers & Operations Research, 38(7):1066–1075, July

    work page doi:10.1109/tevc.2011.2136346 2011

  6. [6]

    12 Thang Nguyen Bui and Curt Jones

    doi: 10.1016/j.cor.2010.10.007. 12 Thang Nguyen Bui and Curt Jones. Finding good approximate vertex and edge partitions is NP-hard. Information Processing Letters, 42(3):153–159,

    work page doi:10.1016/j.cor.2010.10.007 2010

  7. [7]

    13 Umit Catalyurek and Cevdet Aykanat

    doi:10.1016/0020-0190(92) 90140-Q. 13 Umit Catalyurek and Cevdet Aykanat. Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication.IEEE Transactions on Parallel and Distributed Systems, 10(7):673–693,

    work page doi:10.1016/0020-0190(92

  8. [8]

    14 Pierre Chardaire, Musbah Barake, and Geoff P

    doi:10.1109/71.780863. 14 Pierre Chardaire, Musbah Barake, and Geoff P. McKeown. A PROBE-Based Heuristic for Graph Partitioning. IEEE Transactions on Computers, 56(12):1707–1720,

    work page doi:10.1109/71.780863

  9. [9]

    15 Thomas H

    doi: 10.1109/TC.2007.70760. 15 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms. MIT Press, second edition,

    work page doi:10.1109/tc.2007.70760 2007

  10. [10]

    17 Timothy A

    doi: 10.1177/1536867X1101100112. 17 Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection.ACM Transactions on Mathematical Software, 38(1),

    work page doi:10.1177/1536867x1101100112

  11. [11]

    10 Almut Demel, Dominik Dürrschnabel, Tamara Mchedlidze, Marcel Radermacher, and Lasse Wulf

    doi:10.1145/2049662.2049663. 18 Daniel Delling and Renato F. Werneck. Better Bounds for Graph Bisection. In Leah Epstein and Paolo Ferragina, editors,Proceedings of the 20th Annual European Symposium on Algorithms (ESA’12), volume 7501 ofLecture Notes in Computer Science, pages 407–418. Springer,

    work page doi:10.1145/2049662.2049663

  12. [12]

    19 Karen Devine, Erik Boman, Robert Heaphy, Rob Bisseling, and Umit Catalyurek

    doi:10.1007/978-3-642-33090-2_36. 19 Karen Devine, Erik Boman, Robert Heaphy, Rob Bisseling, and Umit Catalyurek. Par- allel Hypergraph Partitioning for Scientific Computing. In 20th International Parallel and Distributed Processing Symposium (IPDPS’06). IEEE Computer Society,

    work page doi:10.1007/978-3-642-33090-2_36

  13. [13]

    20 Julian Dibbelt, Ben Strasser, and Dorothea Wagner

    doi: 10.1109/IPDPS.2006.1639359. 20 Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 21(1):1.5:1–1.5:49, April

    work page doi:10.1109/ipdps.2006.1639359 2006

  14. [14]

    22 Jack Edmonds and Richard M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.Journal of the ACM, 19(2):248–264, April 1972.doi:10.1145/ 321694.321699. 16 Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm 23 Charles M. Fiduccia and Robert M. Mattheyses. A linear-time heuristic for improving network partitions...

    work page arXiv 1972

  15. [15]

    24 Lester R

    doi:10.1145/800263.809204. 24 Lester R. Ford, Jr. and Delbert R. Fulkerson. Maximal flow through a network.Canadian Journal of Mathematics, 8:399–404,

    work page doi:10.1145/800263.809204

  16. [16]

    26 Michael Hamann and Ben Strasser

    doi:10.1145/48014.61051. 26 Michael Hamann and Ben Strasser. Graph Bisection with Pareto Optimization.ACM Journal of Experimental Algorithmics, 23(1):1.2:1–1.2:34,

    work page doi:10.1145/48014.61051

  17. [17]

    27 Bruce Hendrickson and Robert Leland

    doi:10.1145/3173045. 27 Bruce Hendrickson and Robert Leland. A Multilevel Algorithm for Partitioning Graphs. In Proceedings of the 1995 ACM/IEEE conference on Supercomputing (SC’05), page

    work page doi:10.1145/3173045 1995

  18. [18]

    28 Tobias Heuer, Peter Sanders, and Sebastian Schlag

    doi:10.1145/224170.224228. 28 Tobias Heuer, Peter Sanders, and Sebastian Schlag. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning. InProceedings of the 17th International Symposium on Experimental Algorithms (SEA’18), Leibniz International Proceedings in Informatics, pages 1–19,

    work page doi:10.1145/224170.224228

  19. [19]

    29 TobiasHeuerandSebastianSchlag

    doi:10.4230/LIPIcs.SEA.2018.1. 29 TobiasHeuerandSebastianSchlag. ImprovingCoarseningSchemesforHypergraphPartitioning by Exploiting Community Structure. In Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman, editors,Proceedings of the 16th International Symposium on Experimental Algorithms (SEA’17), volume 75 ofLeibniz International ...

    work page doi:10.4230/lipics.sea.2018.1 2018

  20. [20]

    30 George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar

    doi:10.4230/LIPIcs.SEA.2017.21. 30 George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel Hypergraph Partitioning: ApplicationsinVLSIDomain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69–79,

    work page doi:10.4230/lipics.sea.2017.21 2017

  21. [21]

    31 George Karypis and Vipin Kumar

    doi:10.1109/92.748202. 31 George Karypis and Vipin Kumar. Multilevel K-Way Hypergraph Partitioning. InProceedings of the 36th Annual ACM/IEEE Design Automation Conference,

    work page doi:10.1109/92.748202

  22. [22]

    doi:10.1145/309847. 309954. 32 Brian W. Kernighan and Shen Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49(2):291–307, February

    work page doi:10.1145/309847

  23. [23]

    1970.tb01770.x

    doi:10.1002/j.1538-7305. 1970.tb01770.x. 33 Eugene L. Lawler. Cutsets and Partitions of hypergraphs. Networks, 3:275–285,

    work page doi:10.1002/j.1538-7305 1970

  24. [24]

    34 Thomas Lengauer

    doi:10.1002/net.3230030306. 34 Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley,

    work page doi:10.1002/net.3230030306

  25. [25]

    35 Jianmin Li, John Lillis, and C.K. Cheng. Linear decomposition algorithm for VLSI design applications. In Proceedings of the 1995 IEEE/ACM International Conference on Computer- Aided Design, pages 223–228. IEEE Computer Society,

    work page 1995

  26. [26]

    doi:10.1109/ICCAD.1995. 480016. 36 Huiqun Liu and D.F. Wong. Network-Flow-Based Multiway Partitioning with Area and Pin Constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(1):50–59,

    work page doi:10.1109/iccad.1995 1995

  27. [27]

    37 Henning Meyerhenke, Burkhard Monien, and Thomas Sauerwald

    doi:10.1109/43.673632. 37 Henning Meyerhenke, Burkhard Monien, and Thomas Sauerwald. A new diffusion-based multilevel algorithm for computing graph partitions.Journal of Parallel and Distributed Computing, 69(9):750–761,

    work page doi:10.1109/43.673632

  28. [28]

    38 Viswanath Nagarajan, Charles J

    doi:10.1016/j.jpdc.2009.04.005. 38 Viswanath Nagarajan, Charles J. Alpert, Cliff Sze, Zhuo Li, and Yaoguang Wei. The DAC 2012 Routability-driven Placement Contest and Benchmark Suite. InProceedings of the 49th Annual Design Automation Conference,

    work page doi:10.1016/j.jpdc.2009.04.005 2009

  29. [29]

    39 David A

    doi:10.1145/2228360.2228500. 39 David A. Papa and Igor L. Markov. Hypergraph Partitioning and Clustering. In Teofilo F. Gonzalez, editor,Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC,

    work page doi:10.1145/2228360.2228500

  30. [30]

    40 Jean-Claude Picard and Maurice Queyranne

    doi:10.1201/9781420010749. 40 Jean-Claude Picard and Maurice Queyranne. On the Structure of All Minimum Cuts in a Network and Applications.Mathematical Programming, Series A, 22(1):121, December

    work page doi:10.1201/9781420010749

  31. [31]

    doi:10.1007/BF01581031. L. Gottesbüren, M. Hamann, D.Wagner 17 41 Joachim Pistorius and Michel Minoux. An Improved Direct Labeling Method for the Max–Flow Min–Cut Computation in Large Hypergraphs and Applications.International Transactions in Operational Research, 10(1):1–11,

    work page doi:10.1007/bf01581031

  32. [32]

    42 Peter Sanders and Christian Schulz

    doi:10.1111/1475-3995.00389. 42 Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA’11), volume 6942 ofLecture Notes in Computer Science, pages 469–480. Springer,

    work page doi:10.1111/1475-3995.00389

  33. [33]

    44 Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Chris- tian Schulz

    doi:10.1007/978-3-642-38527-8_16. 44 Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Chris- tian Schulz. k-way Hypergraph Partitioning via n-Level Recursive Bisection. InProceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX’16), pages 53–67. SIAM,

    work page doi:10.1007/978-3-642-38527-8_16

  34. [34]

    45 Ruslan Shaydulin, Jie Chen, and Ilya Safro

    doi:10.1137/1.9781611974317.5. 45 Ruslan Shaydulin, Jie Chen, and Ilya Safro. Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning. Multiscale Modeling and Simulation, 17(1):482–506,

    work page doi:10.1137/1.9781611974317.5

  35. [35]

    doi: 10.1137/17M1152735. 46 A. J. Soper, Chris Walshaw, and Mark Cross. The Graph Partitioning Archive,

    work page doi:10.1137/17m1152735

  36. [36]

    48 Brendan Vastenhouw and Rob Bisseling

    doi:10.1016/j.jpdc.2007.11.002. 48 Brendan Vastenhouw and Rob Bisseling. A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication. SIAM Review, 47(1):67–95,

    work page doi:10.1016/j.jpdc.2007.11.002 2007

  37. [37]

    49 Chris Walshaw

    doi: 10.1137/S0036144502409019. 49 Chris Walshaw. Multilevel Refinement for Combinatorial Optimisation Problems.Annals of Operations Research, 131(1):325–372, October 2004.doi:10.1023/B:ANOR.0000039525.80601

    work page doi:10.1137/s0036144502409019 2004

  38. [38]

    18 Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm A ReBaHFC Parameter Discussion In this section we discuss our parameter choices for ReBaHFC

    doi:10.1007/978-1-4615-0292-0_41. 18 Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm A ReBaHFC Parameter Discussion In this section we discuss our parameter choices for ReBaHFC. We use PaToH to obtain initial partitions for ReBaHFC, because it is between one and two orders of magnitude faster than KaHyPar and hMETIS, depending on whether th...

    work page doi:10.1007/978-1-4615-0292-0_41