Graph factors of maximum weight
The case where all gaps have the same parity was solved by Jácint Szabó.

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