Parameterized Local Search for Max -Cut

In the NP-hard problem, one is given an undirected edge-weighted graph  and aims to color the vertices of  with  colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $$c=2$$ is the famous problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study where we are also given a vertex coloring and an integer  and the task is to find a better coloring that changes the color of at most  vertices, if such a coloring exists; otherwise, the given coloring is -optimal. We show that, for all $$c\ge 2$$, presumably cannot be solved in $$f(k)\cdot n^{\mathcal {O}(1)}$$ time even on bipartite graphs. We then present an algorithm for with running time $$\mathcal {O}((3e\Delta )^k\cdot c\cdot k^3\cdot \Delta \cdot 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  . 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.Max -CutMax CutLS Max-CutLS Max -CutLS Max -CutMax -CutcGGcckkkccc