Explainable selection of algorithms for graph partitioning: reproducible benchmarking for fair comparison between multilevel solvers and meta-heuristics

The choice of partitioning algorithm directly influences the cost of communication, the balance between blocks and the use of computational resources in graph-based applications. This work develops a reproducible benchmarking framework to compare, under a common protocol, multilevel solvers such as METIS and KaHIP and meta-heuristics such as Simulated Annealing, Tabu Search, Iterated Local Search and GRASP. The study adopts the same real-time budget of execution per instance, execution on a single thread, common definition of balancing, seed control and independent validation of the partitions produced. The experimental panel combines synthetic and real graphs, organized into morphological regimes, and supports analyses under different time budgets and implementation maturity ablations. Finally, the results feed CART models for explainable selection by instance, converting benchmarking into interpretable rules to support algorithmic choice and allowing to analyze under which conditions each approach tends to present better relative performance, based on structural characteristics of the graphs and the behavior observed throughout the executions.