Graph matching problems and the NP-hardness of sortedness constraints

In this paper, we formulate one of these problems as a marriage scheduling problem, which is a special perfect matching problem in a bipartite graph. We show that the marriage scheduling problem is NP-complete, and we explain the relationships between this graph problem and the sortedness constraints. As a consequence, we deduce that the sort(U,V) constraint (Older et al., 1995), the sort(U,V,P) constraint (Zhou, 1996) and the recently introduced keysorting(U,V,Keys,P) constraint (Carlsson et al., 2014) are intractable (assuming P ≠ NP) for integer variables whose domains are not limited to intervals.