# increasing minimum graph degree by adding edges

My problem: Given a graph $$G=(V, E)$$ and an integer $$\ell$$,add a minimum number of edges to $$G$$ so that in the resulting graph every vertex has degree at least $$\ell$$.

Is there a polynomial-time algorithm for this? Is it NP-complete?

Thanks!

Given a graph $$G=(V, E)$$ and a desired degree $$d_v$$ for each vertex $$v\in V$$, find a maximum-size subset $$E'$$ of $$E$$ such that each vertex $$v\in V$$ has at most $$d_v$$ edges in $$E'$$.