Seleção explicável de algoritmos para particionamento de grafos: benchmarking reprodutível para comparação justa entre solvers multinível e meta-heurísticas

A escolha do algoritmo de particionamento influencia diretamente o custo de comunicação, o equilíbrio entre blocos e o aproveitamento dos recursos computacionais em aplicações baseadas em grafos. Este trabalho desenvolve um framework de benchmarking reprodutível para comparar, sob um protocolo comum, solvers multinível como METIS e KaHIP e meta-heurísticas como Simulated Annealing, Tabu Search, Iterated Local Search e GRASP. O estudo adota o mesmo orçamento de tempo real de execução por instância, execução em uma única thread, definição comum de balanceamento, controle de sementes e validação independente das partições produzidas. O painel experimental combina grafos sintéticos e reais, organizados em regimes morfológicos, e sustenta análises sob diferentes orçamentos de tempo e ablações de maturidade de implementação. Por fim, os resultados alimentam modelos CART para seleção explicável por instância, convertendo benchmarking em regras interpretáveis de apoio à escolha algorítmica e permitindo analisar em que condições cada abordagem tende a apresentar melhor desempenho relativo, com base em características estruturais dos grafos e no comportamento observado ao longo das execuções.