posted on 2025-05-13, 11:49authored byMichael Fellows, Michael Langston, Frances Rosamond, Peter Shaw
In the cluster editing problem, a graph is to be changed to a disjoint union of cliques by at most k operations of edge insertion or edge deletion. Improving on the best previously known quadratic-size polynomial-time kernelization, we describe how a crown-type structural reduction rule can be used to obtain a 24k kernelization bound (and possibly a 6k kernelization bound).