# A Parameterized Algorithm for Bounded-Degree Vertex Deletion

arXiv: https://arxiv.org/abs/1601.00163 · HTML: https://mlsanity.com/paper/1601.00163/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jan 2016.

## Built on by (most cited first, 1 of 1)

- [Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gaps](https://mlsanity.com/paper/2306.13258/) (2023)

## Abstract (arXiv)

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).