Document Open Access Logo

Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm

Authors Lars Gottesbüren, Michael Hamann, Dorothea Wagner

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.52.pdf
  • Filesize: 1.24 MB
  • 17 pages

Document Identifiers

Author Details

Lars Gottesbüren
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Michael Hamann
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany

Funding

This work was supported by the DFG under grants WA654/19-2 and WA654/22-2. The authors acknowledge support by the state of Baden-Württemberg through bwHPC.

Acknowledgements

We thank Ben Strasser, Tim Zeitz and Lukas Barth for helpful discussions.

Cite AsGet BibTex

Lars Gottesbüren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.52

Abstract

In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning that 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Hypergraph Partitioning
  • Maximum Flows
  • Algorithm Engineering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. Google Scholar
  2. Yaroslav Akhremtsev, Tobias Heuer, Sebastian Schlag, and Peter Sanders. Engineering a direct k-way Hypergraph Partitioning Algorithm. In Proceedings of the 19th Meeting on Algorithm Engineering and Experiments (ALENEX'17), pages 28-42. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974768.3.
  3. Charles J. Alpert. The ISPD98 Circuit Benchmark Suite. In Proceedings of the 1998 International Symposium on Physical Design, pages 80-85, 1998. URL: https://doi.org/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 Circuits and Systems, 17(8):655-667, August 1998. URL: https://doi.org/10.1109/43.712098.
  5. Charles J. Alpert and Andrew B. Kahng. Recent Directions in Netlist Partitioning: A Survey. Integration: The VLSI Journal, 19(1-2):1-81, 1995. URL: https://doi.org/10.1016/0167-9260(95)00008-4.
  6. Robin Andre, Sebastian Schlag, and Christian Schulz. Memetic Multilevel Hypergraph Partitioning. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 347-354. ACM Press, July 2018. URL: https://doi.org/10.1145/3205455.3205475.
  7. David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. Graph Partitioning and Graph Clustering: 10th DIMACS Implementation Challenge, volume 588. American Mathematical Society, 2013. URL: https://doi.org/10.1090/conm/588.
  8. Anton Belov, Daniel Diepold, Marijn JH Heule, and Matti Järvisalo. The SAT Competition 2014, 2014. URL: http://www.satcompetition.org/2014/.
  9. Una Benlic and Jin-Kao Hao. An Effective Multilevel Memetic Algorithm for Balanced Graph Partitioning. In IEEE International Conference on Tools with Artificial Intelligence, pages 121-128. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/ICTAI.2010.25.
  10. Una Benlic and Jin-Kao Hao. A Multilevel Memetic Approach for Improving Graph k-Partitions. IEEE Transactions on Evolutionary Computation, 15(5):624-642, October 2011. URL: https://doi.org/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 2011. URL: https://doi.org/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, 1992. URL: https://doi.org/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, 1999. URL: https://doi.org/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, 2007. URL: https://doi.org/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, 2001. Google Scholar
  16. Nicholas J. Cox. Stata Tip 96: Cube Roots. The Stata Journal, 11(1):149-154, 2011. URL: https://doi.org/10.1177/1536867X1101100112.
  17. Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1), 2011. URL: https://doi.org/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 of Lecture Notes in Computer Science, pages 407-418. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_36.
  19. Karen Devine, Erik Boman, Robert Heaphy, Rob Bisseling, and Umit Catalyurek. Parallel Hypergraph Partitioning for Scientific Computing. In 20th International Parallel and Distributed Processing Symposium (IPDPS'06). IEEE Computer Society, 2006. URL: https://doi.org/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 2016. URL: https://doi.org/10.1145/2886843.
  21. Yefim Dinitz. Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Mathematics-Doklady, 11(5):1277-1280, September 1970. Google Scholar
  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. URL: https://doi.org/10.1145/321694.321699.
  23. Charles M. Fiduccia and Robert M. Mattheyses. A linear-time heuristic for improving network partitions. In Proceedings of the 19th ACM/IEEE Conference on Design Automation, pages 175-181, 1982. URL: https://doi.org/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, 1956. Google Scholar
  25. Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  26. Lars Gottesbüren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. Technical report, Institute for Theoretical Informatics, Karlsruhe Institute of Technology, 2019. URL: http://arxiv.org/abs/1907.02053.
  27. Michael Hamann and Ben Strasser. Graph Bisection with Pareto Optimization. ACM Journal of Experimental Algorithmics, 23(1):1.2:1-1.2:34, 2018. URL: https://doi.org/10.1145/3173045.
  28. Bruce Hendrickson and Robert Leland. A Multilevel Algorithm for Partitioning Graphs. In Proceedings of the 1995 ACM/IEEE conference on Supercomputing (SC'05), page 28. ACM Press, 1995. URL: https://doi.org/10.1145/224170.224228.
  29. Tobias Heuer, Peter Sanders, and Sebastian Schlag. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning. In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA'18), Leibniz International Proceedings in Informatics, pages 1-19, 2018. URL: https://doi.org/10.4230/LIPIcs.SEA.2018.1.
  30. Tobias Heuer and Sebastian Schlag. Improving Coarsening Schemes for Hypergraph Partitioning 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 of Leibniz International Proceedings in Informatics, 2017. URL: https://doi.org/10.4230/LIPIcs.SEA.2017.21.
  31. George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel Hypergraph Partitioning: Applications in VLSI Domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69-79, 1999. URL: https://doi.org/10.1109/92.748202.
  32. George Karypis and Vipin Kumar. Multilevel K-Way Hypergraph Partitioning. In Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, 1999. URL: https://doi.org/10.1145/309847.309954.
  33. Brian W. Kernighan and Shen Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49(2):291-307, February 1970. URL: https://doi.org/10.1002/j.1538-7305.1970.tb01770.x.
  34. Eugene L. Lawler. Cutsets and Partitions of hypergraphs. Networks, 3:275-285, 1973. URL: https://doi.org/10.1002/net.3230030306.
  35. Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990. Google Scholar
  36. 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, 1995. URL: https://doi.org/10.1109/ICCAD.1995.480016.
  37. 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, 1998. URL: https://doi.org/10.1109/43.673632.
  38. 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, 2009. URL: https://doi.org/10.1016/j.jpdc.2009.04.005.
  39. Viswanath Nagarajan, Charles J. Alpert, Cliff Sze, Zhuo Li, and Yaoguang Wei. The DAC 2012 Routability-driven Placement Contest and Benchmark Suite. In Proceedings of the 49th Annual Design Automation Conference, 2012. URL: https://doi.org/10.1145/2228360.2228500.
  40. 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, 2007. URL: https://doi.org/10.1201/9781420010749.
  41. 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 1982. URL: https://doi.org/10.1007/BF01581031.
  42. 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, 2003. URL: https://doi.org/10.1111/1475-3995.00389.
  43. Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA'11), volume 6942 of Lecture Notes in Computer Science, pages 469-480. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_40.
  44. Peter Sanders and Christian Schulz. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 164-175. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_16.
  45. Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Christian Schulz. k-way Hypergraph Partitioning via n-Level Recursive Bisection. In Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX'16), pages 53-67. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974317.5.
  46. Ruslan Shaydulin, Jie Chen, and Ilya Safro. Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning. Multiscale Modeling and Simulation, 17(1):482-506, 2019. URL: https://doi.org/10.1137/17M1152735.
  47. A. J. Soper, Chris Walshaw, and Mark Cross. The Graph Partitioning Archive, 2004. URL: http://chriswalshaw.co.uk/partition/.
  48. Aleksandar Trifunovic and William J. Knottenbelt. Parallel Multilevel Algorithms for Hypergraph Partitioning. Journal of Parallel and Distributed Computing, 68(5):563-581, 2008. URL: https://doi.org/10.1016/j.jpdc.2007.11.002.
  49. Brendan Vastenhouw and Rob Bisseling. A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication. SIAM Review, 47(1):67-95, 2005. URL: https://doi.org/10.1137/S0036144502409019.
  50. Chris Walshaw. Multilevel Refinement for Combinatorial Optimisation Problems. Annals of Operations Research, 131(1):325-372, October 2004. URL: https://doi.org/10.1023/B:ANOR.0000039525.80601.15.
  51. Hannah Honghua Yang and D.F. Wong. Efficient Network Flow Based Min-Cut Balanced Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1533-1540, 1996. URL: https://doi.org/10.1007/978-1-4615-0292-0_41.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact