You are given a Graph G and an integer k.

The question is: Does G contain a vertex set X of size at most k such that deleting X results in a graph of degree at most 1?

Design an FPT (or a kernelization) algorithm for this problem and argue why it is correct.

Hint: Observe that vertices of higher degree must be "dealt with" somehow.

I do not exactly know where to start. I suppose that some reduction rules can be applied first, but not so sure what those can be (probably something that "deals with" vertices of higher degree.

Any ideas?


1 Answer 1


I'm not sure about the FPT algorithm, but I have an idea for the kernelization.

All vertices with degree > k + 1 must be in X, since otherwise you would have to pick all but one of its neighbours which would make |X| > k. So you can delete a vertex with degree > k + 1 and rerun the algorithm with the remaining graph and k = k - 1.

You can also delete any vertices with degree 0, as their deletion doesn't change the degree of any other vertices.

  • $\begingroup$ Yes, you are right about that. You can delete vertices with zero degree and vertices with degree > k +1. What I cannot argue is "after the deletion of X, graph has a degree of at most 1". Do you have any idea @PelicanFive? $\endgroup$ Commented Nov 21, 2017 at 20:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.