<p>What you look for in question Q1 is known as an <span class="math-container">$f$</span>-factor of the graph. Here <span class="math-container">$f$</span> is a non-negative integer valued function on the vertices, <span class="math-container">$f(v)$</span> specifying the degree we want in the subgraph at vertex <span class="math-container">$v$</span>.</p>

<p>Q2 is looking for a so called <span class="math-container">$(g,f)$</span> factor, where <span class="math-container">$g(v)$</span> is a lower bound and <span class="math-container">$f(v)$</span> is an upper bound on the degree of the sought subgraph at each vertex <span class="math-container">$v$</span>.</p>

<p>Both problems can be solved in polynomial time, see <a href="https://www.sciencedirect.com/science/article/pii/S0012365X06005486" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S0012365X06005486</a></p>

CC BY-SA 4.0
2019-12-12T04:25:08.767Z
2019-12-12T04:25:08.767Z
Andras Farago
<p>I recently worked on a research paper that answers your questions - specifically, if we have a <span class="math-container">$k$</span>-regular graph <span class="math-container">$G$</span> (each vertex in <span class="math-container">$G$</span> has degree <span class="math-container">$k$</span>), and a set <span class="math-container">$S \subseteq \{1, ..., k\}$</span>, what is the complexity of finding a subset of edges of <span class="math-container">$G$</span> such that each vertex in <span class="math-container">$G$</span> has degree in <span class="math-container">$S$</span>? More formally, what is the complexity of finding an <span class="math-container">$S$</span>-factor of a <span class="math-container">$k$</span>-regular graph? The paper is linked here, I hope you find it useful. </p>

<p><a href="https://eccc.weizmann.ac.il/author/019917/" rel="nofollow noreferrer">https://eccc.weizmann.ac.il/author/019917/</a></p>

<p>It was accepted to the FSTTCS conference on Theoretical Computer Science in September 2019. </p>

CC BY-SA 4.0
2019-12-15T01:26:25.403Z
Thanks. Your reference in the paper to Lovasz's work on the non-regular case was very helpful.
Ari
CC BY-SA 4.0
2019-12-14T02:27:31.810Z
2019-12-14T02:27:31.810Z
user55551
<p>I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:</p>
<blockquote>
<p><strong>Q1:</strong> Given a graph <span class="math-container">$G=(V,E)$</span> and integers <span class="math-container">$d_i,\,1\leq\,i\leq|V|$</span>, does there exist a subset <span class="math-container">$E'\subset\,E$</span> such that in the graph <span class="math-container">$G'=(V,E')$</span> the degree of each vertex <span class="math-container">$v_i\in\,V$</span> is <span class="math-container">$d_i$</span>?</p>
<p><strong>Q2:</strong> Given a graph <span class="math-container">$G=(V,E)$</span> and integers <span class="math-container">$x_i,\,y_i,\,1\leq\,i\leq\,|V|$</span>, does there exist a subset <span class="math-container">$E'\subset\,E$</span> such that in the graph <span class="math-container">$G'=(V,E')$</span> for every <span class="math-container">$v_i\in\,V$</span> we have <span class="math-container">$x_i\leq\deg(v_i)\leq\,y_i$</span>?</p>
</blockquote>
<p>I know already that certain restrictions of <strong>Q1</strong> are known to be in P.</p>
<ul>
<li>If all of the <span class="math-container">$d_i=1$</span> then the problem is finding a perfect matching</li>
<li>If all of the <span class="math-container">$d_i=2$</span> then the problem is finding a vertex cycle cover.</li>
<li>If <span class="math-container">$G$</span> is a complete bipartite graph then the problem can be solved by the Gale-Ryser theorem.</li>
</ul>
<p>However, I haven't found an efficient algorithm for <strong>Q1</strong> in general and nothing specific for <strong>Q2</strong>. Is anything else known?</p>

CC BY-SA 4.0
2019-12-11T17:49:33.197Z
Q1 seems related to the [degree sequence problem](https://en.wikipedia.org/wiki/Degree_(graph_theory)#Degree_sequence) or [graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem); have you tried checking whether the techniques for those problems might prove useful for attacking your Q1?
D.W.
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness>
Complexity of finding an edge set yielding specified vertex degrees
Ari
# Complexity of finding an edge set yielding specified vertex degrees

(Asked by: username_0 on 2019-12-11)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: Q1 seems related to the [degree sequence problem](https://en.wikipedia.org/wiki/Degree_(graph_theory)#Degree_sequence) or [graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem); have you tried checking whether the techniques for those problems might prove useful for attacking your Q1?  

---

## 2 answers

### Answer by username_2 on 2019-12-12. Score: 8 | Accepted answer

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 by username_3 on 2019-12-14. Score: 3

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.

> **Comments:**
> **username_0**: Thanks. Your reference in the paper to Lovasz's work on the non-regular case was very helpful.  

---

