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 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\\ge 2$$ c ≥ 2 , LS Max c -Cut presumably cannot be solved in $$f(k)\\cdot n^{\\mathcal {O}(1)}$$ f ( k ) · n O ( 1 ) time even on bipartite graphs. We then present an algorithm for LS Max c -Cut with running time $$\\mathcal {O}((3e\\Delta )^k\\cdot c\\cdot k^3\\cdot \\Delta \\cdot n)$$ O ( ( 3 e Δ ) k · c · k 3 · Δ · n ) , where $$\\Delta $$ Δ 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.