A 12-integral relaxation for the A-matching problem

The A  -matching problem generalizes matching problems by stipulating that the degree of each vertex lies in a set AvAv of admissible values. If these sets have no large “gaps”, the decision problem is in P  , while the complexity of the optimization version is open. We present a polynomial time solvable 12-integral linear relaxation for this case.