Parameterized Local Search for Max $c$-Cut

Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz +1

In the NP-hard Max $c$-Cut problem, one is given an undirected edge-weighted graph $G$ and aims to color the vertices of $G$ with $c$ colors such that the total weight of edges wit…