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!
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityBy 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.