Algorithms for the Bi-Objective Balanced Multiway Cut Problem

This article addresses the Bi-Objective Balanced Multiway Cut Problem, an NP-hard variation of the classic Minimum Cut problem, in which the goal is to find a set of edges that, when removed, partition the graph into several components, each with exactly one terminal. We seek solutions that minimize both the cost of the removed edge set and the size of the largest component. Since these objectives often conflict, we aim to find a collection of non-dominated solutions. To this end, we use exact and heuristic approaches, employing the CPLEX solver and the evolutionary metaheuristic Non-dominated Sorting Biased Random-Key Genetic Algorithm, respectively. Computational experiments on instances from the literature show that the exact approach obtains non-dominated fronts for some instances, but is outperformed by most heuristics. Among the heuristics, vertex coloring-based strategies achieve the best results.