increasing minimum graph degree by adding edges

Question

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!

Answer 1

By complementing the graph, this problem is a special case of the following problem:

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'$.

Polynomial-time algorithms for this problem (e.g. by reduction to maximum matching) are discussed in the paper "Another look at the degree constrained subgraph problem" by Yossi Shiloach, https://doi.org/10.1016/0020-0190(81)90009-0.