Multiple Decoders to Solve Multiway Cut Problem with MP-BRKGA Meta-Heuristic

In the Multiway Cut Problem (MCP), we aim to find a minimum-cost cut that separates k terminals. This problem is an NP-Hard version of the classic minimum cut problem and arises in applications such as distributed computing and image segmentation. In this work, we present a variety of decoders that use different approaches with the MP-BRKGA metaheuristic to find good solutions for the MCP. These decoders can be adapted to other metaheuristics or used independently. We conducted a detailed experimental analysis of our decoders, demonstrating that two of them can achieve solutions very close to the optimal value quickly and consistently.