A graph G is a cluster graph if every connected component of G is a clique. In the Cluster Editing problem, we are given as input a graph G and an integer k, and the objective is to check whether one can edit (add or delete) at most k edges in G to obtain a cluster graph. . It can be shown that a graph is a cluster graph if and only if it does not have a P3 (sequence of three vertices u, v, w such that uv and vw are edges and uw is not).
Consider the following three reduction rules for a kernelization algorithm:
- Delete a vertex that is not a part of any P3.
- If an edge uv is contained in at least k + 1 different P3, then delete uv and decrement k by one.
- If a non-edge uv is contained in at least k + 1 different P3, then add uv and decrement k by one.
Task: Find a kernel for cluster editing with O(k^2) vertices. To this end, show that after exhaustive application of the above three rules, every yes-instance has O(k^2) vertices.