KaHyPar swMATH ID: 20718 Software Authors: Sebastian Schlag, Peter Sanders, Tobias Heuer Description: KaHyPar - Karlsruhe Hypergraph Partitioning. KaHyPar is a multilevel hypergraph partitioning framework for optimizing the cut- and the (λ − 1)-metric. It supports both recursive bisection and direct k-way partitioning. As a multilevel algorithm, it consist of three phases: In the coarsening phase, the hypergraph is coarsened to obtain a hierarchy of smaller hypergraphs. After applying an initial partitioning algorithm to the smallest hypergraph in the second phase, coarsening is undone and, at each level, a local search method is used to improve the partition induced by the coarser level. KaHyPar instantiates the multilevel approach in its most extreme version, removing only a single vertex in every level of the hierarchy. By using this very fine grained n-level approach combined with strong local search heuristics, it computes solutions of very high quality. Its algorithms and detailed experimental results are presented in several research publications. Homepage: https://github.com/SebastianSchlag/kahypar Source Code: https://github.com/SebastianSchlag/kahypar Keywords: multilevel hypergraph partitioning; algorithm engineering; fm local search; partitioning algorithms; Hypergraph partitioning; HGP Related Software: Zoltan; SparseMatrix; PaToH; DIMACS; UMPa; KaFFPa; Trilinos; MathOptInterface.jl; PowerModels.jl; DISROPT; StochasticPrograms.jl; EAGO.jl; GLPK; Modelica; HYPE; HyperX; Gravity; PSMG; SMS++; PETSc/TS Cited in: 9 Publications all top 5 Cited by 19 Authors 4 Heuer, Tobias 4 Sanders, Peter 4 Schlag, Sebastian 2 Gottesbüren, Lars 2 Safro, Ilya 2 Shaydulin, Ruslan 1 Akhremtsev, Yaroslav 1 Benson, Austin R. 1 Chen, Jie 1 Hamann, Michael 1 Henne, Vitali 1 Jalving, Jordan 1 Kleinberg, Jon Michael 1 Meyerhenke, Henning 1 Schulz, Christian 1 Shin, Sungho 1 Veldt, Nate 1 Wagner, Dorothea 1 Zavala, Victor M. Cited in 3 Serials 1 SIAM Review 1 Multiscale Modeling & Simulation 1 Mathematical Programming Computation Cited in 4 Fields 7 Computer science (68-XX) 6 Combinatorics (05-XX) 3 Operations research, mathematical programming (90-XX) 1 Numerical analysis (65-XX) Citations by Year