<p>The case where all gaps have the same parity was <a href="http://www.sciencedirect.com/science/article/pii/S0095895608001032" rel="nofollow noreferrer">solved by Jácint Szabó</a>.</p>

<p>There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They <a href="https://arxiv.org/pdf/1706.07418.pdf" rel="nofollow noreferrer">claimed to have solved the problem</a>.</p>

CC BY-SA 3.0
2017-06-25T06:49:12.577Z
2017-06-25T06:49:12.577Z
Chao Xu
<p>I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one.  The unweighted version of the problem can be defined as follows.</p>

<p>We are given a graph $G = (V, E)$ and a set of integers $B(v)$ associated to each vertex.  The goal is to find a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph (V, F) is one of the integers in the associated set $B(v)$.  </p>

<p>The problem is known to be solvable in polynomial time if $B(v)$ does not have gaps of length greater than one for any $v$.  For example the set $B(v) = \{5, 7, 8\}$ is OK (the gap between 5 and 7 is of length 1) but the set $B(v) = \{5, 8\}$ is not OK (the gap between 5 and 8 is of length 2).</p>

<p>My question is whether there are any known results for the weighted version of this problem.  So far I found a 1995 survey (Pulleyblank, "Matchings and Extensions") saying that the weighted version has not been solved: "Recently Cornuejols(1988) developed a polynomially bounded extension of the blossom algorithm for this problem when no gap of size greater than one is permitted. However, the corresponding weighted problem has not yet been solved." (p. 212 of "Handbook of combinatorics" vol. 1) </p>

<p>Has this problem been solved since?</p>

<ds.algorithms><graph-theory><graph-algorithms><matching>
Graph factors of maximum weight
George Octavian Rabanca
# Graph factors of maximum weight

(Asked by: username_0 on 2015-07-06)

I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one. The unweighted version of the problem can be defined as follows.

We are given a graph $G = (V, E)$ and a set of integers $B(v)$ associated to each vertex. The goal is to find a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph (V, F) is one of the integers in the associated set $B(v)$.

The problem is known to be solvable in polynomial time if $B(v)$ does not have gaps of length greater than one for any $v$. For example the set $B(v) = \{5, 7, 8\}$ is OK (the gap between 5 and 7 is of length 1) but the set $B(v) = \{5, 8\}$ is not OK (the gap between 5 and 8 is of length 2).

My question is whether there are any known results for the weighted version of this problem. So far I found a 1995 survey (Pulleyblank, "Matchings and Extensions") saying that the weighted version has not been solved: "Recently Cornuejols(1988) developed a polynomially bounded extension of the blossom algorithm for this problem when no gap of size greater than one is permitted. However, the corresponding weighted problem has not yet been solved." (p. 212 of "Handbook of combinatorics" vol. 1)

Has this problem been solved since?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, matching

---

## 1 answers

### Answer by username_1 on 2017-06-25. Score: 4

The case where all gaps have the same parity was [solved by Jácint Szabó](http://www.sciencedirect.com/science/article/pii/S0095895608001032).

There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They [claimed to have solved the problem](https://arxiv.org/pdf/1706.07418.pdf).


---

