Parameterized Local Search for Max c-Cut

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 problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max c -Cut where we are also given a vertex coloring and an integer k and the task is to find a better coloring that changes the color of at most k vertices, if such a coloring exists; otherwise, the given coloring is k -optimal. We show that, for all c≥ 2 c ≥ 2 , LS Max c -Cut presumably cannot be solved in f(k)· nO(1) f ( k ) · n O ( 1 ) time even on bipartite graphs. We then present an algorithm for LS Max c -Cut with running time O((3eΔ )ᵏ· c· k³· Δ · n) O ( ( 3 e Δ ) k · c · k 3 · Δ · n ) , where Δ Δ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max c -Cut . We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances.