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.

  • 1
    $\begingroup$ Hello! We discourage posts that simply state a homework problem, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. You may also want to check out these hints. $\endgroup$ Nov 16 at 20:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.