I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\subset\,E$ such that in the graph $G'=(V,E')$ the degree of each vertex $v_i\in\,V$ is $d_i$?
Q2: Given a graph $G=(V,E)$ and integers $x_i,\,y_i,\,1\leq\,i\leq\,|V|$, does there exist a subset $E'\subset\,E$ such that in the graph $G'=(V,E')$ for every $v_i\in\,V$ we have $x_i\leq\deg(v_i)\leq\,y_i$?
I know already that certain restrictions of Q1 are known to be in P.
- If all of the $d_i=1$ then the problem is finding a perfect matching
- If all of the $d_i=2$ then the problem is finding a vertex cycle cover.
- If $G$ is a complete bipartite graph then the problem can be solved by the Gale-Ryser theorem.
However, I haven't found an efficient algorithm for Q1 in general and nothing specific for Q2. Is anything else known?