A Parameterized Algorithm for Bounded-Degree Vertex Deletion

The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the (d+2)-hitting set problem and generates the famous vertex cover problem. The d-bounded-degree vertex deletion problem is NP-hard for each fixed d≥ 0. In terms of parameterized complexity, the problem parameterized by k is W[2]-hard for unbounded d and fixed-parameter tractable for each fixed d≥ 0. Previously, (randomized) parameterized algorithms for this problem with running time bound O^*((d+1)k) are only known for d≤2. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in O^*((d+1)k) time for each d≥ 3. Note that it is an open problem whether the d'-hitting set problem can be solved in O^*((d'-1)k) time for d'≥ 3. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of O^*(3.0645k) for the case that d=2, improving the previous deterministic bound of O^*(3.24k).