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 wants 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 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 f and an integer k and the task is to find a better coloring f ' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-optimal. We show that, for all c >= 2, LS MAX c-CUT presumably cannot be solved in g(k) center dot n(O(1)) time even on bipartite graphs. We then show an algorithm for LS MAX c-CUT with running time O((3e Delta)(k) center dot c center dot k(3) center dot Delta center dot 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 state-of-the-art heuristics for MAX c-CUT. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.