Complexity of finding an edge set yielding specified vertex degrees

Question

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?

Answer 1

What you look for in question Q1 is known as an $f$-factor of the graph. Here $f$ is a non-negative integer valued function on the vertices, $f(v)$ specifying the degree we want in the subgraph at vertex $v$.

Q2 is looking for a so called $(g,f)$ factor, where $g(v)$ is a lower bound and $f(v)$ is an upper bound on the degree of the sought subgraph at each vertex $v$.

Both problems can be solved in polynomial time, see https://www.sciencedirect.com/science/article/pii/S0012365X06005486

Answer 2

I recently worked on a research paper that answers your questions - specifically, if we have a $k$-regular graph $G$ (each vertex in $G$ has degree $k$), and a set $S \subseteq \{1, ..., k\}$, what is the complexity of finding a subset of edges of $G$ such that each vertex in $G$ has degree in $S$? More formally, what is the complexity of finding an $S$-factor of a $k$-regular graph? The paper is linked here, I hope you find it useful.

https://eccc.weizmann.ac.il/author/019917/

It was accepted to the FSTTCS conference on Theoretical Computer Science in September 2019.