# Complexity of finding an edge set yielding specified vertex degrees

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?

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

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.

• Thanks. Your reference in the paper to Lovasz's work on the non-regular case was very helpful.
– Ari
Dec 15, 2019 at 1:26