Parameterized Local Search for Max c-Cut

Jaroslav Garvardt

doi:10.1007/s10479-026-07426-0

2026-09-17

Jaroslav Garvardt

Niels Grüttemeier

Christian Komusiewicz

Nils Morawietz *

DOI：10.1007/s10479-026-07426-0

原文链接

原文求助

摘要

En 中文

在NP难的Max c-Cut问题中，给定一个无向边加权图G，目标是用c种颜色为G的顶点着色，使得两端点颜色不同的边的总权重最大。c=2的情况是著名的Max Cut问题。为处理该问题的NP难性，我们研究了参数化局部搜索算法。更具体地，我们研究LS Max c-Cut，其中给定一个顶点着色和一个整数k，任务是寻找一个更好的着色方案，该方案最多改变k个顶点的颜色（如果存在这样的着色）；否则，给定着色即为k最优的。我们证明，对于所有c≥2，LS Max c-Cut即使在二分图上，也极不可能在f(k)·n^O(1)时间内求解。然后，我们提出一个LS Max c-Cut算法，其运行时间为O((3eΔ)^k·c·k^3·Δ·n)，其中Δ是输入图的最大度。最后，我们评估将该算法作为Max c-Cut现有最佳启发式算法的后处理进行爬山优化时的实际性能。我们表明，通过参数化局部搜索，可以在一组标准基准实例上进一步改进现有最佳启发式算法的结果。

Keyword:

Generalized graph coloring

Permissive local search

Post-processing heuristic

Partitioning problems