# Complexity status of the Edge Deletion problem to bounded degree graphs

I'm interested in the complexity status of the following problem.

Input: a graph $$G=(V,E)$$ and two natural numbers $$k$$ and $$d$$.

Output: Yes, if there exists a subset $$E' \subseteq E$$ of cardinality at most $$k$$ such that the maximum degree of $$G-E' = (V,E \setminus E')$$ is at most $$d$$. No, otherwise.

Equivalently, your problem may be stated as follows: You are looking for a subgraph, in which every vertex degree lies in the interval $$[0,d]$$ and that contains as many edges as possible.

This problem is well-known to be solvable in polynomial time.
For instance, it is discussed in Chapter 10 (and in particular in Exercise 10.1.4) of the book

M.D. Plummer and L. Lovász:
Matching Theory
Volume 29 of Annals of Discrete Mathematics, Elsevier, 1986.

• Thanks, Gamow! It is exactly what I was looking for. – Victor Mar 30 at 14:11
• Gamow, isn't Exercise 10.1.4 about (inclusion-wise) maximal subgraph $H$? How do we derive the desired result about a subgraph that contains as many edges as possible? – Victor Mar 30 at 19:07
• @Victor: No, no, no. Just study the chapter, and you will see that it discusses the max-cardinality version. (Finding an inclusion-wise maximal subgraph would be trivial, and far below the level of Lovasz and Plummer.) – Gamow Mar 30 at 20:11
• Gamow, indeed, finding an inclusion-wise maximal subgraph is trivial. I was just confused by the fact that the terms "maximal" and "minimal" are defined in the inclusion-wise sense in the book. – Victor Mar 30 at 21:23