Jaroslav Garvardt

Parameterized Local Search for Max c-Cut

Abstract 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 with distinctly colored endpoints is maximal. The case with $$c=2$$ c = 2 is the famous Max Cut probl...