I am doing a problem on fixed parameter tractability where in we are given a graph G=(V,E), and an integer k, and the k-clique edit problem asks whether there exists a set U i.e a subset of V such that G-U is a clique and I need to show that the k-clique edit problem is FPT.

Now as far as I could think of , this problem can be solved using vertex cover.First I try for k=1,and thus X a subset of V is a clique. Now if I take the compliment graph G' and try for k=1, then V-X is a vertex cover. Now the problem is how do i go about phrasing the answer. I know the concept behind the problem, but I am struggling with writing it properly.

  • 1
    $\begingroup$ Your definition of "the k-clique edit problem" does not involve k. ​ ​ $\endgroup$ – user12859 Dec 16 '15 at 6:06
  • $\begingroup$ @RickyDemer Presumably we require $|U|\leq k$. (The problem would be trivial with $|U|\geq k$ -- just delete all but one of the vertices.) $\endgroup$ – David Richerby Jul 31 '16 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.