The A-matching problem generalizes matching problems by stipulating that the degree of each vertex lies in a set Av 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 ½-integral linear relaxation for this case.
