Minimum number of edges to remove to have low degree

Question

I have the following problem, where $k$ is a fixed integer.

Input: Graph $G$.

Output: Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$.

Do you know the complexity of this problem?

Answer 1

If you also insist that the bounded-degree subgraph is connected, then your problem is NP-Hard, since it includes the Longest Path problem when $k=2$.

On the other hand, without the connectivity constraint, your problem can be solved in polynomial-time using standard techniques from matching theory. See this paper of Amini, Peleg, Pérennes, Sau and Saurabh, where they give the book Matching Theory by Lovász and Plummer as one reference to the polynomial result.