Parameterized Local Search for Max c-Cut
Open Access
- 17 September 2026
- journal article
- research article
- Published by Springer Nature in Annals of Operations Research
- Vol. 365 (2-3) , 523-563
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$$ 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$$ , LS Max c -Cut presumably cannot be solved in $$f(k)\cdot n^{\mathcal {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)$$ , 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.
Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (KO 3669/5-1)
This publication has 35 references indexed in Scilit:
- Turbocharging Treewidth HeuristicsAlgorithmica, 2018
- A multiple search operator heuristic for the max-k-cut problemAnnals of Operations Research, 2016
- Teams of Global Equilibrium Search Algorithms for Solving the Weighted Maximum Cut Problem in ParallelCybernetics and Systems Analysis, 2015
- Parameterized Algorithms2015
- Fundamentals of Parameterized Complexity2013
- The Parameterized Complexity of Local Search for TSP, More RefinedAlgorithmica, 2012
- On Some Tighter Inapproximability Results (Extended Abstract)1999
- Some Afterthoughts on Hopfield NetworksLecture Notes in Computer Science, 1999
- Improved approximation algorithms for MAXk-CUT and MAX BISECTIONAlgorithmica, 1997
- Reducibility among Combinatorial Problems1972