Perfect Matching Under Precedence Constraints

ABSTRACT In this article, we motivate and define variants of perfect matching under precedence constraints where a perfect matching is built incrementally and precedence constraints ensure that an edge may only be added to the matching if the edge's predecessor vertices have already been covered. We study the complexity of the problem and particularly consider ‐canonical precedence constraints where only edges that are “close” to the current matching may be added to the matching. For the ‐hard perfect matching under 1‐canonical precedence constraints, we identify polynomial‐time solvable cases.