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?


1 Answer 1


The case where all gaps have the same parity was solved by Jácint Szabó.

There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They claimed to have solved the problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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