9
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.