×

Evaluation of a flow-based hypergraph bipartitioning algorithm. (English) Zbl 07525489

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 52, 17 p. (2019).
Summary: 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.
For the entire collection see [Zbl 1423.68016].

MSC:

68Wxx Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. · Zbl 1201.90001
[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. doi: 10.1137/1.9781611974768.3. · Zbl 1429.68162 · doi:10.1137/1.9781611974768.3
[3] Charles J. Alpert. The ISPD98 Circuit Benchmark Suite. In Proceedings of the 1998 Interna-tional Symposium on Physical Design, pages 80-85, 1998. doi:10.1145/274535.274546. · 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 Circuits and Systems, 17(8):655-667, August 1998. doi:10.1109/43.712098. 52:15 · doi: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. doi:10.1016/0167-9260(95)00008-4. · Zbl 0876.94063 · doi: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. doi:10.1145/3205455.3205475. · doi:10.1145/3205455.3205475
[7] David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. Graph Partition-ing and Graph Clustering: 10th DIMACS Implementation Challenge, volume 588. American Mathematical Society, 2013. doi:10.1090/conm/588. · Zbl 1262.05001 · doi: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. doi:10.1109/ICTAI.2010.25. · doi: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. doi:10.1109/TEVC.2011.2136346. · 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 2011. doi: 10.1016/j.cor.2010.10.007. · Zbl 1205.90286 · 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, 1992. doi:10.1016/0020-0190(92) 90140-Q. · Zbl 0764.68061 · 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, 1999. doi:10.1109/71.780863. · 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, 2007. doi: 10.1109/TC.2007.70760. · Zbl 1390.90547 · 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, 2001. · Zbl 1047.68161
[16] Nicholas J. Cox. Stata Tip 96: Cube Roots. The Stata Journal, 11(1):149-154, 2011. doi:10.1177/1536867X1101100112. · 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), 2011. doi:10.1145/2049662.2049663. · Zbl 1365.65123 · 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 of Lecture Notes in Computer Science, pages 407-418. Springer, 2012. doi:10.1007/978-3-642-33090-2_36. · Zbl 1365.68458 · 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, 2006. doi: 10.1109/IPDPS.2006.1639359. · 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 2016. doi:10.1145/ 2886843. · Zbl 1365.68353 · doi: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. · Zbl 0219.90046
[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. · Zbl 0318.90024 · doi:10.1145/321694.321699
[23] E S A 2 0 1 9 52:16 Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
[24] 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. doi:10.1145/800263.809204. · doi:10.1145/800263.809204
[25] Lester R. Ford, Jr. and Delbert R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-404, 1956. · Zbl 0073.40203
[26] Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. doi:10.1145/48014.61051. · Zbl 0661.90031 · doi:10.1145/48014.61051
[27] 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. arXiv:1907.02053.
[28] Michael Hamann and Ben Strasser. Graph Bisection with Pareto Optimization. ACM Journal of Experimental Algorithmics, 23(1):1.2:1-1.2:34, 2018. doi:10.1145/3173045. · Zbl 1414.68141 · doi:10.1145/3173045
[29] 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. doi:10.1145/224170.224228. · Zbl 0816.68093 · doi:10.1145/224170.224228
[30] 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. doi:10.4230/LIPIcs.SEA.2018.1. · Zbl 1492.68105 · doi:10.4230/LIPIcs.SEA.2018.1
[31] 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. doi:10.4230/LIPIcs.SEA.2017.21. · Zbl 1433.68298 · doi:10.4230/LIPIcs.SEA.2017.21
[32] 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. doi:10.1109/92.748202. · doi:10.1109/92.748202
[33] George Karypis and Vipin Kumar. Multilevel K-Way Hypergraph Partitioning. In Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, 1999. doi:10.1145/309847. 309954. · Zbl 0918.68073 · doi:10.1145/309847.309954
[34] Brian W. Kernighan and Shen Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49(2):291-307, February 1970. doi:10.1002/j.1538-7305. 1970.tb01770.x. · Zbl 0333.05001 · doi:10.1002/j.1538-7305.1970.tb01770.x
[35] Eugene L. Lawler. Cutsets and Partitions of hypergraphs. Networks, 3:275-285, 1973. doi:10.1002/net.3230030306. · Zbl 0262.05126 · doi:10.1002/net.3230030306
[36] Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990. · Zbl 0709.68039
[37] 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. doi:10.1109/ICCAD.1995. 480016. · doi:10.1109/ICCAD.1995.480016
[38] 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. doi:10.1109/43.673632. · doi:10.1109/43.673632
[39] 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. doi:10.1016/j.jpdc.2009.04.005. · doi:10.1016/j.jpdc.2009.04.005
[40] 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. doi:10.1145/2228360.2228500. · doi:10.1145/2228360.2228500
[41] 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. doi:10.1201/9781420010749. 52:17 · Zbl 1138.90001 · doi:10.1201/9781420010749
[42] 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. doi:10.1007/BF01581031. · doi:10.1007/BF01581031
[43] 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. doi:10.1111/1475-3995.00389. · Zbl 1031.90070 · doi:10.1111/1475-3995.00389
[44] 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. doi:10.1007/ 978-3-642-23719-5_40. · Zbl 1346.05288 · doi:10.1007/978-3-642-23719-5_40
[45] 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. doi:10.1007/978-3-642-38527-8_16. · doi:10.1007/978-3-642-38527-8_16
[46] Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Chris-tian 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. doi:10.1137/1.9781611974317.5. · Zbl 1430.68239 · doi:10.1137/1.9781611974317.5
[47] Ruslan Shaydulin, Jie Chen, and Ilya Safro. Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning. Multiscale Modeling and Simulation, 17(1):482-506, 2019. doi: 10.1137/17M1152735. · Zbl 1419.05160 · doi:10.1137/17M1152735
[48] A. J. Soper, Chris Walshaw, and Mark Cross. The Graph Partitioning Archive, 2004. URL: http://chriswalshaw.co.uk/partition/.
[49] Aleksandar Trifunovic and William J. Knottenbelt. Parallel Multilevel Algorithms for Hy-pergraph Partitioning. Journal of Parallel and Distributed Computing, 68(5):563-581, 2008. doi:10.1016/j.jpdc.2007.11.002. · Zbl 1243.68318 · doi:10.1016/j.jpdc.2007.11.002
[50] Brendan Vastenhouw and Rob Bisseling. A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication. SIAM Review, 47(1):67-95, 2005. doi: 10.1137/S0036144502409019. · Zbl 1083.65044 · doi:10.1137/S0036144502409019
[51] 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. 15. · Zbl 1067.90145 · doi:10.1023/B:ANOR.0000039525.80601.15
[52] 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. doi:10.1007/978-1-4615-0292-0_41. · doi:10.1007/978-1-4615-0292-0_41
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.